I just found a triple-factor with P-1. I thought it would be too good to be true to find a 202-bit P-1 factor and assumed it was composite, but I haven't found any (previously-unknown) triple factors with P-1 before; I expected it was a pair of factors. Interestingly this is one of those exponents where the original P-1 missed one of the factors for whatever reason, but my second run at it found that one, plus another two. :smile:
[url]http://mersenne-aries.sili.net/M8724319[/url][code][Sun May 27 22:31:10 2012]
P-1 found a factor in stage #2, B1=160000, B2=3560000.
UID: JamesHeinrich/i7-920, M8724319 has a factor: 9893948425753647218051318141410341116826278223498667572999089[/code]

[QUOTE=James Heinrich;300528]I just found a triple-factor with P-1.[/QUOTE]
Cool!

I'm just curious as to what is done with a number once it has a factor or more than one in the case of the one James Heinrich found. Is it just kept for information sake or some other purpose? I know we need to figure all these factors out to search for the Mersenne Primes, but as I'm stupid when it comes to anything above basic algebra, I was wondering.

Generally once a factor is found the number is left alone. Some enterprising individuals try and find more factors (up to [url=http://mersenne-aries.sili.net/manyfactors.php]10 factors are known[/url] for some exponents), but a single factor is certainly sufficient to prove that a Mersenne number is not-prime, which is helpful towards GIMPS' goal. Ideally it would be nice to have complete factorizations of all Mersenne numbers, but since that's an unattainable goal a list of known factors will always be maintained somewhere.

Factors are great in that they're easily-verifiable proof that said Mersenne number is not prime. Lucas-Lehmer tests are great, but non-trivial to verify. There's always the very-small possibility that a supposedly not-prime result is in fact incorrect, either through error or malice, so having a factor as not-prime proof is always best. Multiple factors, while possibly interesting, don't add any extra benefit to GIMPS' goal in that sense.

[QUOTE=James Heinrich;300722](up to [url=http://mersenne-aries.sili.net/manyfactors.php]10 factors are known[/url] for some exponents)[/QUOTE]

Heh, I wonder how many exponents have factors with k==1?

[QUOTE=Dubslow;300728]Heh, I wonder how many exponents have factors with k==1?[/QUOTE]2,157,779

As it happens I spent the last 24 hours reworking my database to store k differently, so I can easily tell you.

If you care for the more detailed breakdown:[code] [total] => 2157779
[known_factors_000] => 28090
[known_factors_001] => 23476
[known_factors_002] => 21762
[known_factors_003] => 21088
[known_factors_004] => 20428
[known_factors_005] => 19978
[known_factors_006] => 19756
[known_factors_007] => 19218
[known_factors_008] => 19038
[known_factors_009] => 18865
[known_factors_010] => 18564
[known_factors_011] => 18459
[known_factors_012] => 18452
[known_factors_013] => 18238
[known_factors_014] => 18116
[known_factors_015] => 17942
[known_factors_016] => 17861
[known_factors_017] => 17662
[known_factors_018] => 17459
[known_factors_019] => 17618
[known_factors_020] => 17339
[known_factors_021] => 17209
[known_factors_022] => 17046
[known_factors_023] => 17312
[known_factors_024] => 17057
[known_factors_025] => 17046
[known_factors_026] => 16969
[known_factors_027] => 16762
[known_factors_028] => 16700
[known_factors_029] => 16913
[known_factors_030] => 16644
[known_factors_031] => 16702
[known_factors_032] => 16731
[known_factors_033] => 16655
[known_factors_034] => 16801
[known_factors_035] => 16524
[known_factors_036] => 16297
[known_factors_037] => 16428
[known_factors_038] => 16398
[known_factors_039] => 16248
[known_factors_040] => 16254
[known_factors_041] => 15932
[known_factors_042] => 16103
[known_factors_043] => 16240
[known_factors_044] => 16168
[known_factors_045] => 16150
[known_factors_046] => 15994
[known_factors_047] => 15939
[known_factors_048] => 16193
[known_factors_049] => 15844
[known_factors_050] => 15879
[known_factors_051] => 15959
[known_factors_052] => 16040
[known_factors_053] => 15870
[known_factors_054] => 15908
[known_factors_055] => 15780
[known_factors_056] => 15717
[known_factors_057] => 15743
[known_factors_058] => 15441
[known_factors_059] => 15485
[known_factors_060] => 15793
[known_factors_061] => 15599
[known_factors_062] => 15468
[known_factors_063] => 15666
[known_factors_064] => 15460
[known_factors_065] => 15399
[known_factors_066] => 15492
[known_factors_067] => 15516
[known_factors_068] => 15487
[known_factors_069] => 15470
[known_factors_070] => 15395
[known_factors_071] => 15445
[known_factors_072] => 15440
[known_factors_073] => 15346
[known_factors_074] => 15217
[known_factors_075] => 15329
[known_factors_076] => 15291
[known_factors_077] => 15182
[known_factors_078] => 15231
[known_factors_079] => 15289
[known_factors_080] => 15124
[known_factors_081] => 15219
[known_factors_082] => 15143
[known_factors_083] => 15136
[known_factors_084] => 15119
[known_factors_085] => 15289
[known_factors_086] => 15002
[known_factors_087] => 15128
[known_factors_088] => 15087
[known_factors_089] => 14987
[known_factors_090] => 14859
[known_factors_091] => 14965
[known_factors_092] => 15000
[known_factors_093] => 14888
[known_factors_094] => 14934
[known_factors_095] => 15069
[known_factors_096] => 14923
[known_factors_097] => 14955
[known_factors_098] => 14963
[known_factors_099] => 14805
[known_factors_OBD] => 502179[/code]Where "000" = 0M-10M, "001" = 10M-20M .. "099" = 990M-1000M, and OBD is >=1000M

This means approx 5% of all known factors have k=1 ... except for >=1000M where that number jumps to 62%

Law of small number? not enough tested?

Above 1000M testing is scattered (and I almost certainly don't have a complete set of either status or known factors), but the testing has been done is all very-low-level (relative to the exponent size) TF. Once GPU-to-172 gets there, and some P-1 is done, etc, then I'm sure it'll fall back to the normal ~5%.

[QUOTE=James Heinrich;300741]2,157,779

As it happens I spent the last 24 hours reworking my database to store k differently, so I can easily tell you.

<...snip...>

This means approx 5% of all known factors have k=1 ... except for >=1000M where that number jumps to 62%[/QUOTE]

You don't need very laborious calculus or database for this. Let p be a prime, a prime factor q of Mp can be of the form q=2*p+1 if and only if p is 4x+3. If p=4x+1, the smallest possible factor is 6*p+1, therefore k=3. Very easy to prove if you consider that all the factors are either 1 (mod 8) - and in this case all are 8zp+1, z>0 - either 7 (mod 8), and in this case they are 8zp+2p+1, z>=0, for p=3 (mod4) or 8zp+6p+1 for p=1 (mod 4). [B]THIS CASE [/B](when p=1 mod 4 and k=3)[B] would be somehow interesting[/B] to "enumerate" from your data base, as we have no criterion for finding it out by calculus. For the case in discussion, k=1, p can only be 3 mod 4, and [B]any enumeration [/B](searching the data base and counting the factors)[B] makes no sense[/B]: we have the Sophie-Germain criterion.

You can enumerate all the primes p=3 (mod4) for which q=2p+1 is prime up to any number you like (not only GIMPS limit of 10^9) using pari/gp in very short time. I had done this long ago, still have the work. This is the "kernel" routine, it outputs in a file all the exponents and its smallest factor.

[CODE]elimSGp3m4(start,stop,file,pflag)=
{
my(p,d,cnt);
p=max(start,5);
cnt=0;
while(p<stop,
until(p%4==3 && isprime(d=2*p+1),
p=nextprime(p+1)
);
if(p<stop,
if(bitand(pflag,1), printf("...%d...%c",p,13));
if(bitand(pflag,2), print("M"p" is divisible by "d));
if(bitand(pflag,4), write(file,p,",",d));
cnt++
)
);
return(cnt)
};
[/CODE]some sample of result:

[CODE]gp >\r tfm
gp > elimSGp3m4(0,1000,"sophie_germain_primes.txt",7)
M11 is divisible by 23
M23 is divisible by 47
M83 is divisible by 167
M131 is divisible by 263
M179 is divisible by 359
M191 is divisible by 383
M239 is divisible by 479
M251 is divisible by 503
M359 is divisible by 719
M419 is divisible by 839
M431 is divisible by 863
M443 is divisible by 887
M491 is divisible by 983
M659 is divisible by 1319
M683 is divisible by 1367
M719 is divisible by 1439
M743 is divisible by 1487
M911 is divisible by 1823
%111 = 18[/CODE]and the associated output file:
[CODE]11,23
23,47
83,167
131,263
179,359
191,383
239,479
251,503
359,719
419,839
431,863
443,887
491,983
659,1319
683,1367
719,1439
743,1487
911,1823[/CODE]which can be further used to eliminate the exponents from the list of the prime candidates. I believe this is the first things GIMPS ever did in its life.

For the record, there are 1655600 such exponents for which k of the first factor is 1, on whole the GIMPS range (under 10^9).

[CODE]gp > total=0; for(i=2,12,print("Between 10^"i-1" and 10^"i" : "cnt=elimSGp3m4(10^(i-1),10^i,,1)".\tTotal : "total+=cnt))
Between 10^1 and 10^2 : 3. Total : 3
Between 10^2 and 10^3 : 15. Total : 18
Between 10^3 and 10^4 : 81. Total : 99
Between 10^4 and 10^5 : 481. Total : 580
Between 10^5 and 10^6 : 3331. Total : 3911
Between 10^6 and 10^7 : 24179. Total : 28090
Between 10^7 and 10^8 : 183609. Total : 211699
Between 10^8 and 10^9 : 1443901. Total : 1655600
...1302645131...[/CODE](still running, it will take about 5 minutes to reach here, maybe 50 minutes or a hour or so to reach 10Gig, it can still be optimized, but who needs all this statistics? :razz:)

[QUOTE=James Heinrich;300746]Above 1000M testing is scattered (and I almost certainly don't have a complete set of either status or known factors), but the testing has been done is all very-low-level (relative to the exponent size) TF. Once GPU-to-172 gets there, and some P-1 is done, etc, then I'm sure it'll fall back to the normal ~5%.[/QUOTE]
I have/had a complete list of factors under 2^56 of Mp for all prime exponents p between 0 and 10G. This is generated by hunting for the size of the factor first (for a given prime q which is 1 or 7 mod 8, factor (q-1)/2 and see if for any p in the resulted factor list, if q divides Mp. This can be done very fast, as you are not interested in full-factoring q-1, but only in its factors p which are on your "interest range", in our case, lower then a billion, or 10 billions). This idea is debated on the forum here and there in the past, and I even posted pieces of (unoptimized) pari code. I did this long time ago, I may not find all the files, but if you are interested I can send you the log files which I still can find. It takes one day to go to 2^40 on a single core, then the time doubles for each bit. It generates different files for each exponent range and bit range. See here a starting-from-40-bits-factors interrupted after about 30 seconds, and then a second run for starting-from-45-bits factors, interrupted after about 5 minutes (of course, for higher bit-count the factors are output less and less frequent). For 50 bits and higher, one can get about ONE factor every few minutes. In the files it creates, the format is "factor, exponent". If you are really interested, I can look for the original (complete) files, or eventually give it a new run, but this would take some time. The only thing I found interesting at the time when I was doing this it was the fact that the factors come "in waves", for example you see even for the interval I have run this simple demo, there is no file with _9B_, this means there is no factor of Mp with exponent p between 9G and 10G ("B" stands for billion, but I use G for Giga to avoid confusion, as some people use long scale, B=10^12, other use short scale, B=10^9). The factors coming in waves, in packages, buckets, whatever, is somehow normal, due to the form of the factors. As k in q=2kp+1 can never be of the form 4x+2 (a factor can't be, for example 4p+1, 12p+1, 20p+1, etc, as those would be all 5 mod 8, and we know the factors have to be 1 or 7 mod 8), there will be "gaps", behaving almost the same as prime gaps. For example, if p is between 1000 and 2000, all factors 2p+1 would be in 2000-4000, all of the form 6p+1 would be in 6000-12000, and there would never be a factor between 4000 and 6000. If p is in 6000-7000, then by the same reason, there could never be a factor below 12000, nor between 14-36 thousands, nor between 42-48 thousands, 56-60, 70-84, and nor 126-132 thousands. This can be scaled to millions, billions or trillions. As the interval grows, there are more and larger gaps. But more than this, one can not get. There is no known way one could predict where a factor will be, or what values k will take for a certain exponent or range of exponents.

[QUOTE=James Heinrich;300528]I just found a triple-factor with P-1.[/QUOTE]Another slightly unusual composite P-1 factor:
[url]http://mersenne-aries.sili.net/M8724929[/url]
[code][Wed Jun 13 17:30:01 2012]
P-1 found a factor in stage #2, B1=160000, B2=3560000.
UID: JamesHeinrich/i7-920, M8724929 has a factor: 2929655011230723414437969299453013510477993453298031[/code]Only 171 bits this time, but one of the components was still a respectable 105 bits, and the other 65-bit factor was just slightly outside the normal B2 range, so Brent-Suyama saved the day.