View unanswered posts  View active topics

Page 1 of 1

[ 40 posts ] 

Author 
Message 
NType3

Post subject: Fastest method highest prime factor? Posted: Sat Aug 13, 2011 1:22 am 

Joined: Mon Oct 18, 2010 10:48 am

I was talking with a friend today about a program to find the highest prime factor of x.
I postulated that one of the fastest methods is to create a for loop
[pseudocode] While I is less than x Add one to I if x is divisible by I, set x to x/I and repeat this check.
Simple program; I typed it out and it's reasonably fast. But is there a faster way? (Assume no table of primes. No precalculation allowed)
_________________ Noah
I don't know half of you half as well as I should like and I like less than half of you half as well as you deserve.


Top 


Brandon Enright

Post subject: Re: Fastest method highest prime factor? Posted: Sat Aug 13, 2011 5:39 pm 

Joined: Thu Dec 31, 2009 8:54 pm Location: Bay Area, California

NType3 wrote: I was talking with a friend today about a program to find the highest prime factor of x.
I postulated that one of the fastest methods is to create a for loop
[pseudocode] While I is less than x Add one to I if x is divisible by I, set x to x/I and repeat this check.
Simple program; I typed it out and it's reasonably fast. But is there a faster way? (Assume no table of primes. No precalculation allowed) For small values of x it doesn't really matter but your existing for loop can be improved. For one, you don't need to check from i to x but from i to sqrt(x). Second, check for the value of 2 in a special case and then start at 3 and instead of adding 1 to i each iteration, add two. For very large x the algorithms to factor a number (or to find the largest factor) get quite complicated. Currently the fastest known algorithm is general number field sieve (GNFS).
_________________ Prior to using my real name I posted under the account named bmenrigh.


Top 


NType3

Post subject: Re: Fastest method highest prime factor? Posted: Sat Aug 13, 2011 6:10 pm 

Joined: Mon Oct 18, 2010 10:48 am

In lua, the code I came up with yesterday is as follows: Code: function getHighPrime(x) q = 0; while x%2==0 do x=x/2; q = q + 1; end
print("2 was factored out "..q.." time(s) to leave a starting # of: "..x..".");
for i=3,x,2 do if x%i == 0 then while x%i == 0 do if(x==i) then break end x=x/i; print("The new max search is: "..x,"After factoring out: "..i); end end end
print("The highest prime factor is: "..x); end
_________________ Noah
I don't know half of you half as well as I should like and I like less than half of you half as well as you deserve.


Top 


Brandon Enright

Post subject: Re: Fastest method highest prime factor? Posted: Sat Aug 13, 2011 6:23 pm 

Joined: Thu Dec 31, 2009 8:54 pm Location: Bay Area, California

NType3 wrote: In lua, the code I came up with yesterday is as follows: What has you coding in Lua? It's a good language to be comfortable with because it is embedded so many places.
_________________ Prior to using my real name I posted under the account named bmenrigh.


Top 


NType3

Post subject: Re: Fastest method highest prime factor? Posted: Sat Aug 13, 2011 6:36 pm 

Joined: Mon Oct 18, 2010 10:48 am

Lua is actually one of my favorite programming languages, believe it or not. The way data is stored makes it much more fluid in my mind. Second for me is C++, and third is Java.
To be fair, Lua doesn't have the best error descriptions (to say the least).
_________________ Noah
I don't know half of you half as well as I should like and I like less than half of you half as well as you deserve.


Top 


TomZ

Post subject: Re: Fastest method highest prime factor? Posted: Sun Aug 14, 2011 2:38 am 

Joined: Fri Feb 08, 2008 1:47 am Location: near Utrecht, Netherlands

Very cool solution. A few pointers:
You don't need the if around the while All primes are of the form 3k+1 or 3k1 so you could use that to make it faster You could skip the if x==i bit if you let it stop the for loop when x==1 and then print the value of i, or better yet, use while x=/=1 and manually increment i. Unlike previously suggested using sqrt(x) will not make your code any fastern since it would never check values of i above sqrt(x) anyway.
All these are only constant time optimalizations, your code runs in O(sqrt(x)). I think there may be a faster solution but I don't know if it's even been invented yet.
_________________ Tom's Shapeways Puzzle Shop  your order from my shop includes free stickers! Tom's Puzzle Website
Buy my mass produced puzzles at Mefferts:  4x4x6 Cuboid for just $38  Curvy Copter for just $18  3x4x5 Cuboid for just $34


Top 


NType3

Post subject: Re: Fastest method highest prime factor? Posted: Sun Aug 14, 2011 12:26 pm 

Joined: Mon Oct 18, 2010 10:48 am

Here's the revised version: Code: function getHighPrime(x) q = 0 while x%2==0 do x=x/2 q = q + 1 end
print("2 was factored out "..q.." time(s) to leave a starting # of: "..x..".")
for i=3,x,2 do while x%i == 0 do x=x/i print("The new max search is: "..x,"After factoring out: "..i) end if(x==1) then print("The highest prime factor is: "..i); break end end end
_________________ Noah
I don't know half of you half as well as I should like and I like less than half of you half as well as you deserve.


Top 


GuiltyBystander

Post subject: Re: Fastest method highest prime factor? Posted: Sun Aug 14, 2011 10:19 pm 

Joined: Wed May 13, 2009 4:58 pm Location: Vancouver, Washington

bmenrigh wrote: Second, check for the value of 2 in a special case. NType3 wrote: Code: while x%2==0 do x=x/2; q = q + 1; end
If you have bitwise operators, this should be faster if the compiler doesn't already do this replacement. Code: while(x & 1 == 0){ x = x>>1; q = q + 1; }
TomZ wrote: All primes are of the form 3k+1 or 3k1 so you could use that to make it faster I presume you mean to do this in addition to checking if it's odd. Checking for oddness lets you only test 50% of the numbers. Using only your 3k+1 test, you have to test 66.67% of the numbers. One quick way to combine the two without a bunch of ifs and tests is to just start i=5 and alternate between incrementing i by 2,4. You would have to hard code tests for 2,3,5. Here you only test 33.33% of the numbers. You can take this idea further to eliminate factors of 5 by starting i=7, then using (4,2,4,2,4,6,2,6) to increment i. You'd only be saving testing about 26.67% If you tried this for 7s, your list would be 4050 integers summing to 210. Haven't done the math on how much would be tested, but I'm kind of doubting it would save you much. TomZ wrote: or better yet, use while x=/=1 and manually increment i. I'm not familiar with the =/= operator (or lua that much). What does it do? TomZ wrote: Unlike previously suggested using sqrt(x) will not make your code any faster since it would never check values of i above sqrt(x) anyway. Of course it would speed it up. If you're testing 37 (prime) you should only check 26. You can skip 737. Even if you test 74 (2*37), you still only need to test 26. If you do use this shortcut, be sure to do i*i<x instead of i<sqrt(x). A multiplication is much faster than sqrt(). I'm not sure if 3 additions are faster than 1 multiplication. If they are, keep a 2nd variable ii to represent i*i. When you increment i, do (ii += i + i + 1).
_________________ Real name: Landon Kryger
Last edited by GuiltyBystander on Sun Aug 14, 2011 11:32 pm, edited 2 times in total.


Top 


NType3

Post subject: Re: Fastest method highest prime factor? Posted: Sun Aug 14, 2011 10:41 pm 

Joined: Mon Oct 18, 2010 10:48 am

I increment by two after testing directly for 2. The code effectively does the same thing as checking 2,3,5, then starting at 7 with an increment of two. As for =/=, I gathered Tom meant to say 'not equal'. The not equal command in lua is ~=. As for checking from I to sqrt(x), I would have to recalculate the square root of x every time the code iterates (or rather, calculate i*i>x) and this may (or may not, in some worstcase scenarios) slow the program down. In a worstcase scenario where the input is prime, checking the sqrt(x) would certainly increase the speed. I did add the square root check (as i*i>x) and found that the program can process instantaneously the number 2293874894389493928384 (a random number generated by pounding the keypad), whereas the old program took minutes to process. In lua,  is a comment. Code: function getHighPrime(x) j = 0 while x%2==0 do x=x/2 j = j + 1 end
print("2 was factored out "..j.." time(s) to leave a starting # of: "..x..".")
for i=3,x,2 do while x%i == 0 do x=x/i print("The new max search is: "..x,"After factoring out: "..i) end
if(i*i>x) then break end if(i==x) then break end end
print("The highest prime factor is: "..x); end
_________________ Noah
I don't know half of you half as well as I should like and I like less than half of you half as well as you deserve.


Top 


Brandon Enright

Post subject: Re: Fastest method highest prime factor? Posted: Mon Aug 15, 2011 3:23 pm 

Joined: Thu Dec 31, 2009 8:54 pm Location: Bay Area, California

NType3 wrote: I did add the square root check (as i*i>x) and found that the program can process instantaneously the number 2293874894389493928384 (a random number generated by pounding the keypad), whereas the old program took minutes to process. Hi Noah, I would expect the square root to give you a big speedup but for your example number of 2293874894389493928384, the largest prime factor is 3982421691648426959 and square root / counting by 2 / whatever is not going to ever be really fast on a number such as 3982421691648426959. How does your program know 3982421691648426959 is prime? Even the square root of it is nearly 2 billion. It should take your program quite a while.
_________________ Prior to using my real name I posted under the account named bmenrigh.


Top 


NType3

Post subject: Re: Fastest method highest prime factor? Posted: Mon Aug 15, 2011 11:59 pm 

Joined: Mon Oct 18, 2010 10:48 am

I believe you are mistaken in that assumption, but please correct me if I'm wrong. If I am, I'm curious where my error lies. 3982421691648426959 > 2293874894389493928384. 2293874894389493928384 factors: 2293874894389493928384: 2^19*17*1451*177371352157. Quote: 2 was factored out 19 time(s) to leave a starting # of: 4.3752191436567e+015. The new max search is: 2.5736583197981e+014 After factoring out: 17 The new max search is: 177371352157 After factoring out: 1451 The highest prime factor is: 177371352157 Edit: 3982421691648426959 isn't even a prime number: Quote: > getHighPrime(3982421691648426959) 2 was factored out 10 time(s) to leave a starting # of: 3.8890836832504e+015. The new max search is: 1.2963612277501e+015 After factoring out: 3 The new max search is: 30147935529073 After factoring out: 43 The highest prime factor is: 30147935529073
_________________ Noah
I don't know half of you half as well as I should like and I like less than half of you half as well as you deserve.


Top 


Brandon Enright

Post subject: Re: Fastest method highest prime factor? Posted: Tue Aug 16, 2011 12:20 am 

Joined: Thu Dec 31, 2009 8:54 pm Location: Bay Area, California

NType3 wrote: I believe you are mistaken in that assumption, but please correct me if I'm wrong. If I am, I'm curious where my error lies. 3982421691648426959 > 2293874894389493928384. 2293874894389493928384 factors: 2293874894389493928384: 2^19*17*1451*177371352157. Quote: 2 was factored out 19 time(s) to leave a starting # of: 4.3752191436567e+015. The new max search is: 2.5736583197981e+014 After factoring out: 17 The new max search is: 177371352157 After factoring out: 1451 The highest prime factor is: 177371352157 Edit: 3982421691648426959 isn't even a prime number: Quote: > getHighPrime(3982421691648426959) 2 was factored out 10 time(s) to leave a starting # of: 3.8890836832504e+015. The new max search is: 1.2963612277501e+015 After factoring out: 3 The new max search is: 30147935529073 After factoring out: 43 The highest prime factor is: 30147935529073 Welcome to the wonderful world of floating point error. In Lua, everything is backed by the C "double" type which is 64 bits. 52 of those bits are mantissa bits. The number that you provided (2293874894389493928384) needs 71 bits to represent it. Because a double doesn't have 71 mantissa bits available you can not represent 2293874894389493928384 in Lua. The number 2293874894389493928384 factors into: 2^6 * 3^2 * 3982421691648426959 The factors you got (2^19*17*1451*177371352157) result in 2293874894389493891072 Note that 2293874894389493928384 != 2293874894389493891072 The number you factored is off from the number you wrote by 37312 because of double precision error.
_________________ Prior to using my real name I posted under the account named bmenrigh.


Top 


NType3

Post subject: Re: Fastest method highest prime factor? Posted: Tue Aug 16, 2011 12:56 am 

Joined: Mon Oct 18, 2010 10:48 am

Gah! Is there a way to correct this? In cpp, I would simply use a long unsigned int, but what about lua?
_________________ Noah
I don't know half of you half as well as I should like and I like less than half of you half as well as you deserve.


Top 


Brandon Enright

Post subject: Re: Fastest method highest prime factor? Posted: Tue Aug 16, 2011 9:24 am 

Joined: Thu Dec 31, 2009 8:54 pm Location: Bay Area, California

NType3 wrote: Gah! Is there a way to correct this? In cpp, I would simply use a long unsigned int, but what about lua? The widths of the int types in C are mostly up to the compiler. For most compilers on 32 bit platforms both longs and ints are both 32 bits. On 64bit platforms longs are often 64 bits. Even a long long is generally only 64 bits. The number you are trying to crunch needs an 80 bit or even a 128 bit int. GCC supports a nonstandard '__int128' type but it requires that the hardware support for 128 bit integers. What you want is arbitrary precision integers. The typical way to do this in most languages is to use bindings to OpenSSL or to GMP. I have more experience with OpenSSL but from what I know, GMP is probably a better library to use. Nmap uses Lua for the "Nmap Scripting Engine" (NSE) and we went with OpenSSL bindings. It looks like somebody has written a bigint library in purely Lua here: https://bitbucket.org/tedu/bigintlua/src/tip/bigint.luaFor what it's worth, Python's integer data types are arbitrary precision so you don't have to worry about these sorts of things. This is one of the reasons why Python is a bit slow.
_________________ Prior to using my real name I posted under the account named bmenrigh.


Top 


NType3

Post subject: Re: Fastest method highest prime factor? Posted: Tue Aug 16, 2011 9:54 am 

Joined: Mon Oct 18, 2010 10:48 am

I feel like that's going to be obscenely slow, though.
_________________ Noah
I don't know half of you half as well as I should like and I like less than half of you half as well as you deserve.


Top 


GuiltyBystander

Post subject: Re: Fastest method highest prime factor? Posted: Tue Aug 16, 2011 10:56 am 

Joined: Wed May 13, 2009 4:58 pm Location: Vancouver, Washington

If you ever want to verify the accuracy of your program, I highly recommend using Wolfram Alpha.
_________________ Real name: Landon Kryger


Top 


Brandon Enright

Post subject: Re: Fastest method highest prime factor? Posted: Tue Aug 16, 2011 1:32 pm 

Joined: Thu Dec 31, 2009 8:54 pm Location: Bay Area, California

NType3 wrote: I feel like that's going to be obscenely slow, though. The number "1125902456980891" is a 51 bit composite that should be very close to the maximally inefficient composite for your program to factor using your current strategy and still fit into just the mantissa of a double. You should be able to benchmark improvements to your program with this number. Testing using GP/PARI on my system show it can be factored in less than 1 ms. The strategy GP/PARI uses though is quite complicated.
_________________ Prior to using my real name I posted under the account named bmenrigh.


Top 


wwwmwww

Post subject: Re: Fastest method highest prime factor? Posted: Tue Aug 16, 2011 2:53 pm 

Joined: Thu Dec 02, 2004 12:09 pm Location: Missouri

GuiltyBystander wrote: If you ever want to verify the accuracy of your program, I highly recommend using Wolfram Alpha. Interesting little program... While playing with it just now I found these 10 consecutive 11 digit numbers. 81680880640 = 2^10 * 5 * 313 * 50969 81680880641 = 41 * 1992216601 (near prime) 81680880642 = 2 * 3 * 19 * 79 * 467 * 19421 81680880643 = 81680880643 (prime) 81680880644 = 2^2 * 11 * 9967 * 186253 81680880645 = 3^2 * 5 * 7 * 13 * 17^2 * 69019 81680880646 = 2 * 40840440323 (near prime) 81680880647 = 81680880647 (prime) 81680880648 = 2^3 * 3 * 223 * 15261749 81680880649 = 81680880649 (prime) So out of 10 numbers I found 3 primes and 2 near primes (the product of 2 primes). I must say I was very surprised. Are the primes much more dense that I thought or did I just get very very lucky. Asked another way. Consider the set of all possible sets of 10 consecutive 11 digit numbers. No leading zeros... so we are talking about numbers between 10000000000 and 99999999999. What percentage of those sets are half or more made up of primes or near primes? Is there any set that contains more then 5 total primes and near primes? Can you give an example like I did above? Are there any sets containing 4 or more primes? I think I can prove 4 is the max possible. 5 of the 10 must be even and 1 of the remaining 5 I think must be divisable by 3. Maybe these questions are something you could test out your programs on... assuming I'm proposing a problem that can be solved in a reasonable amount of cpu time. Carl
_________________ 
Last edited by wwwmwww on Tue Aug 16, 2011 5:06 pm, edited 1 time in total.


Top 


Brandon Enright

Post subject: Re: Fastest method highest prime factor? Posted: Tue Aug 16, 2011 3:09 pm 

Joined: Thu Dec 31, 2009 8:54 pm Location: Bay Area, California

wwwmwww wrote: GuiltyBystander wrote: If you ever want to verify the accuracy of your program, I highly recommend using Wolfram Alpha. Interesting little program... While playing with it just now I found these 10 consecutive 11 digit numbers. 81680880640 = 2^10 * 5 * 313 * 50969 81680880641 = 41 * 1992216601 (near prime) 81680880642 = 2 * 3 * 19 * 79 * 467 * 19421 81680880643 = 81680880643 (prime) 81680880644 = 2^2 * 11 * 9967 * 186253 81680880645 = 3^2 * 5 * 7 * 13 * 17^2 * 69019 81680880646 = 2 * 40840440323 (near prime) 81680880647 = 81680880647 (prime) 81680880648 = 2^3 * 3 * 223 * 15261749 81680880649 = 81680880649 (prime) So out of 10 numbers I found 3 primes and 2 near primes (the product of 2 primes). I must say I was very surprised. Are the primes much more dense that I thought or did I just get very very lucky. Asked another way. Consider the set of all possible sets of 10 consecutive 11 digit numbers. No leading zeros... so we are talking about numbers between 10000000000 and 99999999999. What percentage of those sets are half or more made up of primes or near primes? Is there any set that contains more then 5 total primes and near primes? Can you give an example like I did above? Are there any sets containing 4 or more primes? I think I can prove 4 is the max possible. 5 of the 10 must be even and 1 of the remaining 5 I think must be divisable by 3. Maybe these questions are something you could test out your programs on... assuming I'm proposing a problem that can be solved in a reasonable about of cpu time. Carl Hi Carl, thanks for taking this to the next level I think we can answer your question statistically using a prime counting function pi(x) approximation. As for the max of 4, I think the max might possibly be 3. 5 of the 10 must be even but 1 of the remaining 5 must be divisible 5 and 1 of the remaining 5 should be divisible by 3. It could be the same remaining number that is divisible by both 3 and 5 but I'm not sure what implications that would have on the others being divisible by 3 or by 7. Only a range of 90 billion needs to be checked for an exact solution which should be computationally tractable. Probably beyond what you'd want to do on your laptop though. Edit: the first such sequence of ten 11digit numbers that contains 4 primes is 10000057420 to 10000057429: 10000057420: 2 2 5 500002871 10000057421: 10000057421 10000057422: 2 3 12391 134507 10000057423: 10000057423 10000057424: 2 2 2 2 7 17 73 71947 10000057425: 3 5 5 43 1013 3061 10000057426: 2 49081 101873 10000057427: 10000057427 10000057428: 2 2 3 3 19 2687 5441 10000057429: 10000057429 This does not seem to be an uncommon property: Got 4 primes at 10000057420 to 10000057429 Got 4 primes at 10000057421 to 10000057430 Got 4 primes at 10000057930 to 10000057939 Got 4 primes at 10000057931 to 10000057940 Got 4 primes at 10000067920 to 10000067929 Got 4 primes at 10000067921 to 10000067930 Got 4 primes at 10000195810 to 10000195819 Got 4 primes at 10000195811 to 10000195820 Got 4 primes at 10000236220 to 10000236229 Got 4 primes at 10000236221 to 10000236230 Got 4 primes at 10000333330 to 10000333339 Got 4 primes at 10000333331 to 10000333340 Got 4 primes at 10000339750 to 10000339759 Got 4 primes at 10000339751 to 10000339760 Got 4 primes at 10000347100 to 10000347109 Got 4 primes at 10000347101 to 10000347110 [...]
_________________ Prior to using my real name I posted under the account named bmenrigh.


Top 


NType3

Post subject: Re: Fastest method highest prime factor? Posted: Tue Aug 16, 2011 3:44 pm 

Joined: Mon Oct 18, 2010 10:48 am

I'll give this a try later! We shall see the estimated probability.
_________________ Noah
I don't know half of you half as well as I should like and I like less than half of you half as well as you deserve.


Top 


wwwmwww

Post subject: Re: Fastest method highest prime factor? Posted: Tue Aug 16, 2011 5:18 pm 

Joined: Thu Dec 02, 2004 12:09 pm Location: Missouri

bmenrigh wrote: This does not seem to be an uncommon property:
Got 4 primes at 10000057420 to 10000057429 Got 4 primes at 10000057421 to 10000057430 Got 4 primes at 10000057930 to 10000057939 Got 4 primes at 10000057931 to 10000057940 Got 4 primes at 10000067920 to 10000067929 Got 4 primes at 10000067921 to 10000067930 Got 4 primes at 10000195810 to 10000195819 Got 4 primes at 10000195811 to 10000195820 Got 4 primes at 10000236220 to 10000236229 Got 4 primes at 10000236221 to 10000236230 Got 4 primes at 10000333330 to 10000333339 Got 4 primes at 10000333331 to 10000333340 Got 4 primes at 10000339750 to 10000339759 Got 4 primes at 10000339751 to 10000339760 Got 4 primes at 10000347100 to 10000347109 Got 4 primes at 10000347101 to 10000347110 [...] 1 in ~ 57420 is still rather rare if that is what this comes to. I also notice if we are just looking for primes we probably should limit the search to sets of 9 consecutive numbers or each set of 4 is counted twice. It also appears that of all the sets found so far the last digit of the first prime is always "1"... any exceptions to this? And if you include the near primes what is the most you can find (primes and near primes) within ten consective 11digit numbers? Carl
_________________ 


Top 


NType3

Post subject: Re: Fastest method highest prime factor? Posted: Tue Aug 16, 2011 5:21 pm 

Joined: Mon Oct 18, 2010 10:48 am

Adding this (most inefficient) block of code: Code: function seriesTenConsec(pause) testCount = 0; positiveCountOne = 0; positiveCountTwo = 0; positiveCountThree = 0; positiveCountFour = 0; numOfDiscoveredPrimes = 0;
for i=10000000000,99999999999,1 do seriesCounter = 0
for j=i,i+10,1 do print(j,getHPDecider(j,true)) if(j == getHPDecider(j,true)) then seriesCounter = seriesCounter + 1 print("THIS IS PRIME.") end print("\n") numOfDiscoveredPrimes = numOfDiscoveredPrimes + seriesCounter end
if(seriesCounter == 1) then positiveCountOne = positiveCountOne + 1 elseif(seriesCounter == 2) then positiveCountTwo = positiveCountTwo + 1 elseif(seriesCounter == 3) then positiveCountThree = positiveCountThree + 1 elseif(seriesCounter == 4) then positiveCountFour = positiveCountFour + 1 else end
testCount = testCount + 1
print("Stats 1: "..positiveCountOne.."/"..testCount.."\t\t\t"..roundOne((positiveCountOne/testCount)*100)) print("Stats 2: "..positiveCountTwo.."/"..testCount.."\t\t\t"..roundOne((positiveCountTwo/testCount)*100)) print("Stats 3: "..positiveCountThree.."/"..testCount.."\t\t\t"..roundOne((positiveCountThree/testCount)*100)) print("Stats 4: "..positiveCountFour.."/"..testCount.."\t\t\t"..roundOne((positiveCountFour/testCount)*100)) print(seriesCounter.." discovered primes the "..testCount.."th iteration.")
if(pause) then os.execute[[pause]] end end end I wasn't sure how to approach it other than brute force (help in efficiency would be appreciated, though the program works). For those of you with the Lua console, the pastebin is here (and yes, you'll notice yet another inefficiency). For clarity, getHPDecider is a function which runs either a muted or unmuted getHighPrime function. The output is rather interesting. It seems, Carl, that you were *extremely* lucky. 1 prime: 34% occurrence rate. 2 primes: 6% occurrence rate. 3 primes: 0% occurrence rate. 4 primes: 0% occurrence rate. *results after 60,000 iterations I'll modify it to show five significant digits, and post new results shortly.
_________________ Noah
I don't know half of you half as well as I should like and I like less than half of you half as well as you deserve.


Top 


NType3

Post subject: Re: Fastest method highest prime factor? Posted: Tue Aug 16, 2011 5:32 pm 

Joined: Mon Oct 18, 2010 10:48 am

bmenrigh wrote: Hi Carl, thanks for taking this to the next level I think we can answer your question statistically using a prime counting function pi(x) approximation. As for the max of 4, I think the max might possibly be 3. 5 of the 10 must be even but 1 of the remaining 5 must be divisible 5 and 1 of the remaining 5 should be divisible by 3. It could be the same remaining number that is divisible by both 3 and 5 but I'm not sure what implications that would have on the others being divisible by 3 or by 7. Only a range of 90 billion needs to be checked for an exact solution which should be computationally tractable. Probably beyond what you'd want to do on your laptop though. Edit: the first such sequence of ten 11digit numbers that contains 4 primes is 10000057420 to 10000057429: 10000057420: 2 2 5 500002871 10000057421: 10000057421 10000057422: 2 3 12391 134507 10000057423: 10000057423 10000057424: 2 2 2 2 7 17 73 71947 10000057425: 3 5 5 43 1013 3061 10000057426: 2 49081 101873 10000057427: 10000057427 10000057428: 2 2 3 3 19 2687 5441 10000057429: 10000057429 This does not seem to be an uncommon property: Got 4 primes at 10000057420 to 10000057429 Got 4 primes at 10000057421 to 10000057430 Got 4 primes at 10000057930 to 10000057939 Got 4 primes at 10000057931 to 10000057940 Got 4 primes at 10000067920 to 10000067929 Got 4 primes at 10000067921 to 10000067930 Got 4 primes at 10000195810 to 10000195819 Got 4 primes at 10000195811 to 10000195820 Got 4 primes at 10000236220 to 10000236229 Got 4 primes at 10000236221 to 10000236230 Got 4 primes at 10000333330 to 10000333339 Got 4 primes at 10000333331 to 10000333340 Got 4 primes at 10000339750 to 10000339759 Got 4 primes at 10000339751 to 10000339760 Got 4 primes at 10000347100 to 10000347109 Got 4 primes at 10000347101 to 10000347110 [...] I apologize for the double post. Because of this output, is it safe to assume that the digit in the ones' place alternates between a zero and a one? If so, why is this?
_________________ Noah
I don't know half of you half as well as I should like and I like less than half of you half as well as you deserve.


Top 


wwwmwww

Post subject: Re: Fastest method highest prime factor? Posted: Tue Aug 16, 2011 5:49 pm 

Joined: Thu Dec 02, 2004 12:09 pm Location: Missouri

NType3 wrote: Because of this output, is it safe to assume that the digit in the ones' place alternates between a zero and a one? If so, why is this? I can answer part of that... Because I was including nearprimes in my original question I was looking at sets of 10 consecutive numbers. This means either the first or the last number is even. So if you find 4 primes in a set as bmenrigh has then you know they are actually within a set of 9 consecutive numbers. Now when bmenrigh checked the next set of 10 consecutive numbers he actually found these same 4 primes again. So there are actually half as many sets in that list as there appears to be. And of the sets found the last digit of the first prime was "1". Is that always the case? I don't know... that's what I asked above as well. If it is... the question as to why does become very interesting. Carl
_________________ 
Last edited by wwwmwww on Tue Aug 16, 2011 5:51 pm, edited 1 time in total.


Top 


GuiltyBystander

Post subject: Re: Fastest method highest prime factor? Posted: Tue Aug 16, 2011 5:51 pm 

Joined: Wed May 13, 2009 4:58 pm Location: Vancouver, Washington

The property you're talking about is Prime Quadruplet. Formally they are of the form (p, p+2, p+6, p+8). Because it has to avoid certain primes like 2,3,5, they all are of the form (30 n + 11, 30 n + 13, 30 n + 17, 30 n + 19). This is why all of bmenrigh's ranges are 09 or 110. The one exception to this is (5,7,11,13), but obviously the 5 keeps anything else from doing this again. According to Sloane's A050258, there are 180529 of them between 10^11 and 10^11. This reminds me of the twin prime conjecture that predicts that there are an infinite number of twin prime (p, p+2). So far it hasn't been proven to be true. More good reading on this at Mathworld. Another good topic worth reading is Prime Gaps.
_________________ Real name: Landon Kryger


Top 


NType3

Post subject: Re: Fastest method highest prime factor? Posted: Tue Aug 16, 2011 5:56 pm 

Joined: Mon Oct 18, 2010 10:48 am

wwwmwww wrote: NType3 wrote: Because of this output, is it safe to assume that the digit in the ones' place alternates between a zero and a one? If so, why is this? I can answer part of that... Because I was including nearprimes in my original question I was looking at sets of 10 consecutive numbers. This means either the first or the last number is even. So if you find 4 primes in a set as bmenrigh has then you know they are actually within a set of 9 consecutive numbers. Now when bmenrigh checked the next set of 10 consecutive numbers he actually found these same 4 primes again. So there are actually half as many sets in that list as there appears to be. And of the sets found the last digit of the first prime was "1". Is that always the case? I don't know... that's what I asked above as well. If it is... the question as to why does become very interesting. Carl Oh, I gathered from your statement that one should test ALL possible sets of ten. This includes (if we were starting at one) 110, 211, 312, etc. however, if it's actually 110, 1120, 2130, then I need to restructure my code significantly. Both, however, should theoretically produce the same results, no? @GuiltyBystander: That's interesting! So you're saying that even with my orignal method, I'm likely to find the same result? (I'm not sure I understand entirely, but I gave it my best shot).
_________________ Noah
I don't know half of you half as well as I should like and I like less than half of you half as well as you deserve.


Top 


wwwmwww

Post subject: Re: Fastest method highest prime factor? Posted: Tue Aug 16, 2011 6:06 pm 

Joined: Thu Dec 02, 2004 12:09 pm Location: Missouri

NType3 wrote: Oh, I gathered from your statement that one should test ALL possible sets of ten. This includes (if we were starting at one) 110, 211, 312, etc. Yes this is what I meant. NType3 wrote: however, if it's actually 110, 1120, 2130, then I need to restructure my code significantly. Both, however, should theoretically produce the same results, no? Based on what GuiltyBystander shows above then yes I'd say you should get the same result if you are just looking for primes. However I'm not sure that would be the case if you included the nearprimes. Carl
_________________ 


Top 


NType3

Post subject: Re: Fastest method highest prime factor? Posted: Tue Aug 16, 2011 6:13 pm 

Joined: Mon Oct 18, 2010 10:48 am

I believe, given enough samples, it wouldn't make a statistical difference. Given the test is 'emulating' selecting a random number and going up ten from there (my random numbers have an algorithm of n+1), the results should be similar.
In other words, go from the probability backwards.
Assume there's a 50% chance of X happening. If a person starts from 1 and goes by increment of 1 to 100, the results should theoretically be the same as starting at 1 and going to 1000 by increment of ten, given there's a 50% chance at each starting digit.
_________________ Noah
I don't know half of you half as well as I should like and I like less than half of you half as well as you deserve.


Top 


wwwmwww

Post subject: Re: Fastest method highest prime factor? Posted: Tue Aug 16, 2011 6:24 pm 

Joined: Thu Dec 02, 2004 12:09 pm Location: Missouri

GuiltyBystander wrote: According to Sloane's A050258, there are 180529 of them between 10^11 and 10^11. If I understand that list correctly shouldn't that be: 1209318180529 or 1028789 prime quadruples between 10^10 and 10^11 So between 10000000000 and 99999999999 we have 9 billion nonoverlaping sets of the form: xxxxxxxxxx0 to xxxxxxxxxx9 Of those 9 billion sets 1028789 of them contain a prime quadruple, or about 0.0114% of them. Interesting. If you considered all possible sets of 10 consecutive numbers you'd have 90 billion sets to check and each prime quadruple would show up in 2 sets so your odds drop to: 0.0114%*2/10 or about 0.00229% How do your odds improve for finding a set with just 3 primes? Carl
_________________ 


Top 


GuiltyBystander

Post subject: Re: Fastest method highest prime factor? Posted: Tue Aug 16, 2011 6:39 pm 

Joined: Wed May 13, 2009 4:58 pm Location: Vancouver, Washington

wwwmwww wrote: GuiltyBystander wrote: According to Sloane's A050258, there are 180529 of them between 10^11 and 10^11. If I understand that list correctly shouldn't that be: 1209318180529 or 1028789 prime quadruples between 10^10 and 10^11 Oops, you're right. NType3 wrote: I believe, given enough samples, it wouldn't make a statistical difference. Given the test is 'emulating' selecting a random number and going up ten from there (my random numbers have an algorithm of n+1), the results should be similar. Except the probability of a number being prime isn't uniform. If you look at the occurrence of each digit in primes, you'll find that the digit 1 occurs in prime numbers more often than any other number. This is because prime numbers become rarer and rarer so there will be more primes between 100199 than there will be between 200299. Similarly, I don't think you can assume 09 will be statistically different from 110. Although, you should imediatly discount digits ending in 0 anyways for being near misses because they're guaranteed to have 2,5 as factors.
_________________ Real name: Landon Kryger


Top 


NType3

Post subject: Re: Fastest method highest prime factor? Posted: Tue Aug 16, 2011 6:46 pm 

Joined: Mon Oct 18, 2010 10:48 am

Stats for 1 prime: 33.962% Stats for 2 primes: 6.236% Stats for 3 primes: 0.397% Stats for 4 primes: 0.0162%
That's my results so far.
_________________ Noah
I don't know half of you half as well as I should like and I like less than half of you half as well as you deserve.


Top 


Brandon Enright

Post subject: Re: Fastest method highest prime factor? Posted: Tue Aug 16, 2011 7:08 pm 

Joined: Thu Dec 31, 2009 8:54 pm Location: Bay Area, California

NType3 wrote: Assume there's a 50% chance of X happening. If a person starts from 1 and goes by increment of 1 to 100, the results should theoretically be the same as starting at 1 and going to 1000 by increment of ten, given there's a 50% chance at each starting digit. This is assuming a uniform distribution of primes (which implies a uniform distribution of quadprimes). Because the small primes such as 2, 3, 5, have significant impact on what numbers can be prime for a given range of 10 the distribution is not uniform. As GuiltyBystander / MathWorld points out, quadprimes must be of the form (30n + 11, 30n + 13, 30n + 17, 30n + 19), incrementing your check by range window by 1 versus 10 would give significantly different answers.
_________________ Prior to using my real name I posted under the account named bmenrigh.


Top 


NType3

Post subject: Re: Fastest method highest prime factor? Posted: Tue Aug 16, 2011 7:48 pm 

Joined: Mon Oct 18, 2010 10:48 am

Given a large enough sample size, would it make a statistically significant difference?
For example, at the 1.49 millionth iteration, the percentages are now: 1: 33.999% 2: 6.237% 3: .3964% 4: .00908%
The only significantly different number is the search for 4, and that, occurring in the rarity it does, I believe requires a larger sample size to definitively decide. It has only occurred 136 times as opposed to 514110 times for one prime.
Please correct me if I'm wrong though; I'm very interested in all of this.
_________________ Noah
I don't know half of you half as well as I should like and I like less than half of you half as well as you deserve.


Top 


GuiltyBystander

Post subject: Re: Fastest method highest prime factor? Posted: Tue Aug 16, 2011 9:17 pm 

Joined: Wed May 13, 2009 4:58 pm Location: Vancouver, Washington

wwwmwww wrote: Asked another way. Consider the set of all possible sets of 10 consecutive 11 digit numbers. No leading zeros... so we are talking about numbers between 10000000000 and 99999999999. What percentage of those sets are half or more made up of primes or near primes? Is there any set that contains more then 5 total primes and near primes? Can you give an example like I did above?
Are there any sets containing 4 or more primes? I think I can prove 4 is the max possible. 5 of the 10 must be even and 1 of the remaining 5 I think must be divisable by 3. I'm been doing some math and found you can never have more then 2 near primes within a prime quadruplet. Clearly, numbers ending in 0,2,4,6,0 will have 2 as a factor. Again, numbers ending in 0,5,0 will have 5 as a factor. Using the formula about them being 30n + {11,13,17,19} shows us that 2,5,8 are divisible by 3. With these three facts, we can eliminate 0,2,5,8,0 as being near primes because they have at lease 2 factors in them already. This leaves 4 and 6 to be the candidates for being near primes which would require that 15n + {7,8} are prime. If we consider 7's, we can see that we can put more restrictions on this. If we know that 1,3,7,9 aren't divisible by 7, we also know that 0,2,8,0 can't be divisible by 7 either. This leaves 4,5,6 to have 7 as a factor. Since 4,6 already have a factor, 5 must be divisible by 7. This means that at least 2/3 of all prime quadruplets can't have 2 near primes (assuming even distribution which we already know to be false, but it should be somewhat close). Using the quadruplet formula, (15n + 15) must be divisible by 7 meaning (n + 1) must be divisible by 7. I'm trying to run a program to find some. So far I haven't found anything with n<100000000. I'll keep it running for a while though. I'm a tad surprised, but I guess not really if there's only 4768 prime quadruplets. I wonder if there's something about...nvmd. I just realized that 15n+7 and 15n+8 can't both be prime. So you can have a max of 4 primes and 1 near prime. First example is (11,13,7*2,17,19). Next is (101, 103, 53*2, 107, 109)
_________________ Real name: Landon Kryger


Top 


wwwmwww

Post subject: Re: Fastest method highest prime factor? Posted: Wed Aug 17, 2011 9:26 am 

Joined: Thu Dec 02, 2004 12:09 pm Location: Missouri

GuiltyBystander wrote: So you can have a max of 4 primes and 1 near prime. First example is (11,13,7*2,17,19). Next is (101, 103, 53*2, 107, 109) Ok... so in my first example I showed a string of 10 numbers which contained 3 primes and 2 near primes. Is that also a max? If you force yourself to include a quadprime then you know the last digit of the first prime is "1" and since the number before it and the one at the end of the string both end in "0" you are really looking at just a string of 9 numbers. I'm curious if the added flexability gained by only requiring 3 primes would allow for 3 or more near primes to be found in a string of 10 consecutive 11digit numbers? What about if there were just 2 primes? Is 5 really the max possible of prime + near prime in such a string? Carl
_________________ 


Top 


GuiltyBystander

Post subject: Re: Fastest method highest prime factor? Posted: Wed Aug 17, 2011 2:13 pm 

Joined: Wed May 13, 2009 4:58 pm Location: Vancouver, Washington

wwwmwww wrote: GuiltyBystander wrote: So you can have a max of 4 primes and 1 near prime. First example is (11,13,7*2,17,19). Next is (101, 103, 53*2, 107, 109) Ok... so in my first example I showed a string of 10 numbers which contained 3 primes and 2 near primes. Is that also a max? If you force yourself to include a quadprime then you know the last digit of the first prime is "1" and since the number before it and the one at the end of the string both end in "0" you are really looking at just a string of 9 numbers. I'm curious if the added flexability gained by only requiring 3 primes would allow for 3 or more near primes to be found in a string of 10 consecutive 11digit numbers? What about if there were just 2 primes? Is 5 really the max possible of prime + near prime in such a string? I sent my computer on a search and found that It seems you can have prime + near prime > 5. Here's a few examples. There more with prime + near prime = 6, but I thought these were more impressive. prime + 6 near7 near7 nearHere's a short list of the 10th number of a set of 10 and how many primes + near primes are in the set. Fair warning, I used Java's BigInteger.isProbablePrime(100) to test for primeness so it's not guaranteed 100% to be accurate, but there's a 1 1/2^100 chance that they are. Code: 10000000711 6 10000012351 6 10000028587 6 10000029387 6 10000046146 6 10000048658 6 10000058906 6 10000058907 6 10000058909 6 10000058911 7 10000074391 6 10000081915 6 10000082054 6 10000089602 6 10000096838 6 10000096963 6 10000097546 6 10000107487 6 10000139885 6 10000139887 7 10000139889 6 10000144538 6 10000153243 6 10000163006 6 10000174286 6 10000174287 6 10000174289 6 10000174291 6 10000180123 6 10000184491 6 10000184494 6 10000184767 6 10000190971 6 10000210951 6 10000210954 6 10000222322 6 10000229546 6 10000246106 6 10000256846 6 10000262455 6 10000263151 6 10000263423 6 10000267423 6 10000272286 6 10000272523 6 10000284062 6 10000296242 6 10000296305 6 10000296307 7 10000296309 6 10000296311 6 10000302161 6 10000302163 6 10000304558 6 10000312961 6 10000317803 6 10000329982 6 10000374305 6 10000378963 6 10000384943 6 10000384945 6 10000390766 6 10000397146 6 10000397147 6 10000402466 6 10000402471 6 10000405747 6 10000407122 6 10000408706 6 10000414735 6 10000421345 6
_________________ Real name: Landon Kryger


Top 


wwwmwww

Post subject: Re: Fastest method highest prime factor? Posted: Wed Aug 17, 2011 4:05 pm 

Joined: Thu Dec 02, 2004 12:09 pm Location: Missouri

GuiltyBystander wrote: There more with prime + near prime = 6, but I thought these were more impressive. prime + 6 near7 near7 nearNICE!!! So is it possible to prove 7 is the max possible without doing a full search? If a full search is needed and someone does it (that's probably not reasonable) I'm curious... of the sets which contain 7 prime or near primes what is the maximum number of primes in such a set? Carl
_________________ 


Top 


GuiltyBystander

Post subject: Re: Fastest method highest prime factor? Posted: Wed Aug 17, 2011 6:03 pm 

Joined: Wed May 13, 2009 4:58 pm Location: Vancouver, Washington

wwwmwww wrote: So is it possible to prove 7 is the max possible without doing a full search? This is actually pretty easy and you just need to consider how they're relatively prime to 2 and 3. First lets look at the even numbers. In a consecutive set of 10 numbers, 5 are going to be even. Of the 5, either 2/3 of them will be divisible by 4. Here's the two options. Code: 42424 Here we already have 3 non (prime+near primes) 24242 Therefore this must be the option Next we consider the overlap of 3's with 2's. Code: 11311 13113 31131 And together with 24242 Code: 2 4 6 4 2 2 12 2 4 6 6 4 2 12 2 In every case, there are at least 3 cases of non (prime + near prime). wwwmwww wrote: If a full search is needed and someone does it (that's probably not reasonable) I'm curious... of the sets which contain 7 prime or near primes what is the maximum number of primes in such a set? I'm sure there's some more math to do here, but I haven't thought about it at all. Sent my computer searching. Gonna have to revise that earlier list. It has a few bugs in it.
_________________ Real name: Landon Kryger


Top 


GuiltyBystander

Post subject: Re: Fastest method highest prime factor? Posted: Fri Aug 19, 2011 5:56 pm 

Joined: Wed May 13, 2009 4:58 pm Location: Vancouver, Washington

GuiltyBystander wrote: wwwmwww wrote: If a full search is needed and someone does it (that's probably not reasonable) I'm curious... of the sets which contain 7 prime or near primes what is the maximum number of primes in such a set? I'm sure there's some more math to do here, but I haven't thought about it at all. Sent my computer searching. Was going to post results yesterday, but I'm glad I didn't. I let it keep running and found some better results. To answer your question. You can have 3 primes + 4 near primes. Proof by example. So far I've searched 10000000000  10026548143 and found 3766 examples where prime + nears >= 6. Here's the total counts if you're interested in the rarity. Code: Prime Near Count 3 4 1 2 5 6 1 6 26 0 7 30 3 3 52 2 4 488 1 5 1608 0 6 1555
_________________ Real name: Landon Kryger


Top 


wwwmwww

Post subject: Re: Fastest method highest prime factor? Posted: Fri Aug 19, 2011 6:27 pm 

Joined: Thu Dec 02, 2004 12:09 pm Location: Missouri

GuiltyBystander wrote: To answer your question. You can have 3 primes + 4 near primes. Proof by example. Nice!!! Thanks... I think I'm finally out of questions. Carl
_________________ 


Top 



Page 1 of 1

[ 40 posts ] 

Who is online 
Users browsing this forum: Exabot [Bot] and 3 guests 

You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot post attachments in this forum


