frequency k gives a factor

[bgbeuning]

The attached graph shows k (as in 2*k*p+1 is a factor of 2^p-1)
and how many factors (y axis) are known in the GIMPS database
for 400 < k < 800 (x axis).

I have two questions for you smart people.

1. Since some k result in more factors than other k, would there be any
algorithmic benefit to searching for factors using those more prolific k ?

2. The large spike on the left of the graph is for k=420 (2*2*3*5*7) while the
spike for k=512 (2*2*2*2*2*2*2*2*2) is 1/3 as high. Prime k have low data points.
From perusing the data it seems that k with more unique factors are more prolific.
Is there anything in Number Theory to support this hunch?
(Some people would call this numerology.)
I tried computing a linear correlation between the number of unique factors of k
and number of Mersenne factors found by that k, but the best correlation I
found was 0.6 . If there is a relation, I expect it is not linear.

If RDS was still here, I would not dare ask these questions.

[LaurV]

1. No. Once we know the p, its k's have all the same probability. This was discussed here not far than few weeks ago.

Your distribution may have something to do with the fact that "for all p", k's being 0 mod 4 have a double probability to result in a factor than k's which are 1 or 3 mod 4 (k can not be 2 mod 4, in that case 2kp+1 is 5 mod 8 and it can not be a factor).

Looking to your graph like that, it just shows 3 lines, going asimptotically down, as k gets bigger (which is normal, as we don't know "all" mersenne factors (yet ))

You could try to re-plot 3 graphics, for k being 0, 1, and 3 mod 4, respectively, and see how the bars look. Then we may need (or not) to talk deeper about it...

edit: or two graphs, one for k=0 mod 4, which has a double probability, as it can be factor of both p=1 or p=3 mod 4, and a second graph for k=1 and k=3 mod 4 together, which can be respective factors when p=3 and p=1 mod 4.

[science_man_88]

Originally Posted by bgbeuning

The attached graph shows k (as in 2*k*p+1 is a factor of 2^p-1)
and how many factors (y axis) are known in the GIMPS database
for 400 < k < 800 (x axis).

I have two questions for you smart people.

1. Since some k result in more factors than other k, would there be any
algorithmic benefit to searching for factors using those more prolific k ?

2. The large spike on the left of the graph is for k=420 (2*2*3*5*7) while the
spike for k=512 (2*2*2*2*2*2*2*2*2) is 1/3 as high. Prime k have low data points.
From perusing the data it seems that k with more unique factors are more prolific.
Is there anything in Number Theory to support this hunch?
(Some people would call this numerology.)
I tried computing a linear correlation between the number of unique factors of k
and number of Mersenne factors found by that k, but the best correlation I
found was 0.6 . If there is a relation, I expect it is not linear.

If RDS was still here, I would not dare ask these questions.

I think what you are seeing with the highly composite k having more is that if k is highly composite ( within the primes themselves not as a whole) it leaves less factors for 2*k*p+1 under a certain size. like the proof that there are infinitely many primes we have w=2*k*p that has loads of factors, w and w+1 can't share factors so w+1 can't have factors below the highest prime fully covered by k.

[bgbeuning]

All the graphs look similar to me.

Used this AWK script to split the data

$2 < 400 { next }
$2 > 800 { exit }

$2 % 4 == 0 { print >> "k0.csv" }
$2 % 4 == 1 { print >> "k1.csv" }
$2 % 4 == 2 { print >> "k2.csv" }
$2 % 4 == 3 { print >> "k3.csv" }

[science_man_88]

though the bias you talked about makes sense in that a k value that is 0 mod a prime is least likely to be composite all k that are 1 mod 3 when tried with p that are 1 mod 3 give q values that are divisible by 3. all k that are 2 mod 3 when tried with p = 2 mod 3 will also give q values that divide by 3. k=0 mod 3 are the only values of k that aren't going to give a composite for whole groups of p. basically any time k%r * p%r = r\2 mod r where \ means euclidean division then q=2*k*p+1 divides by r. edit: the caveat of using this of course is that you may take longer to find a factor if at all within a range of bit levels. similar to how saying mersennes must have at least 1 factor that is 3 mod 4 isn't in itself useful as there could still be any number of factors that are 1 mod 4 underneath said factor. not to mention for example with p=11 no factor exist with k=0 mod 3.

[bgbeuning]

I read your post about 20 times. What I got from it is that k values with
lots of unique factors have a better chance of making q=2*k*p+1 a prime,
so those k get tried more often as potential factors of 2^p-1. With the odds
of any q being a factor equal, more tries yield more successes.

The Wikipedia page made it sounds like euclidean division is what programmers
call integer division (throw away any remainder).

Thanks,

[science_man_88]

Originally Posted by bgbeuning

I read your post about 20 times. What I got from it is that k values with
lots of unique factors have a better chance of making q=2*k*p+1 a prime,
so those k get tried more often as potential factors of 2^p-1. With the odds
of any q being a factor equal, more tries yield more successes.

The Wikipedia page made it sounds like euclidean division is what programmers
call integer division (throw away any remainder).

Thanks,

in fact any time k and 2 together contain all the primes less than sqrt(2*k*p+1) it has to be prime because all the divisor less than the square root are part of k or 2. so for example 2*3*5+1 is prime because sqrtint(31)==5 and all of 2,3, and 5 are not allowed.( okay that one involved p so p has some involvement as well) 2*7*5+1 = 71 is also prime as the next prime square is 11^2 so all factors other than 3 below the square root are taken up and 69 divides by 3 so 71 can't. we can also now say like i did through pm that all k = 71*x+7 also create values divisible by 71 ( for k=7 in the example) ( aka can't be prime for x>0). edit: if we were to switch k and p values so k=5 p=7 we could also say for p=7 k=71*x+5 are also composite or 71. but GIMPS searches by p.