Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum
 It is currently Wed Apr 23, 2014 1:04 pm

 All times are UTC - 5 hours

 Page 1 of 1 [ 40 posts ]
 Print view Previous topic | Next topic
Author Message
 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

 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

 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

 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

 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

 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 3k-1 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:

Top

 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

 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 3k-1 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 40-50 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 2-6. You can skip 7-37. Even if you test 74 (2*37), you still only need to test 2-6.
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

 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 worst-case scenarios) slow the program down. In a worst-case 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

 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

 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

 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

 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

 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 non-standard '__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.lua

For 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

 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

 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

 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

 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

 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 11-digit 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

 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

 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 11-digit numbers?

Carl

_________________
-

Top

 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

 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 11-digit 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

 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 near-primes 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

 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 0-9 or 1-10. 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

 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 near-primes 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) 1-10, 2-11, 3-12, etc. however, if it's actually 1-10, 11-20, 21-30, 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

 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) 1-10, 2-11, 3-12, etc.
Yes this is what I meant.
NType3 wrote:
however, if it's actually 1-10, 11-20, 21-30, 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 near-primes.

Carl

_________________
-

Top

 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

 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:

1209318-180529 or 1028789 prime quadruples between 10^10 and 10^11

So between 10000000000 and 99999999999 we have 9 billion non-overlaping 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

 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:

1209318-180529 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 100-199 than there will be between 200-299. Similarly, I don't think you can assume 0-9 will be statistically different from 1-10.
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

 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

 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 quad-primes). 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, quad-primes 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

 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

 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

 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 quad-prime 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 11-digit 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

 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 quad-prime 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 11-digit 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 near
7 near
7 near

Here'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

 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 near
7 near
7 near
NICE!!!
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

 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

 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

 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

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 40 posts ]

 All times are UTC - 5 hours

#### Who is online

Users browsing this forum: No registered users and 6 guests

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

Search for:
 Jump to:  Select a forum ------------------ Announcements General Puzzle Topics New Puzzles Puzzle Building and Modding Puzzle Collecting Solving Puzzles Marketplace Non-Twisty Puzzles Site Comments, Suggestions & Questions Content Moderators Off Topic

Forum powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group