[QUOTE=Christenson;266975]What if the exponent had several factors [e.g. look up the exponent "god" was using[/quote]Since that was me for a while, let me provide a short list (they're easy to find if you know how/where to look :)[code]M800000041 has a factor: 32000001641
M800000041 has a factor: 5357430980168323663
found 2 factor(s) for M800000041 from 2^35 to 2^69 [mfaktc 0.18-pre1-Win 71bit_mul24]

M800000759 has a factor: 1600001519
M800000759 has a factor: 6400006073
M800000759 has a factor: 10240019438409224887
found 3 factor(s) for M800000759 from 2^33 to 2^69 [mfaktc 0.18-pre1-Win 71bit_mul24]

M800002139 has a factor: 14400038503
M800002139 has a factor: 13677324569648791
found 2 factor(s) for M800002139 from 2^34 to 2^69 [mfaktc 0.18-pre1-Win 71bit_mul24]

M800002649 has a factor: 24000079471
M800002649 has a factor: 30400100663
found 2 factor(s) for M800002649 from 2^35 to 2^69 [mfaktc 0.18-pre1-Win 71bit_mul24]

M800002699 has a factor: 14400048583
M800002699 has a factor: 67425000050326478281
found 2 factor(s) for M800002699 from 2^34 to 2^69 [mfaktc 0.18-pre1-Win 71bit_mul24]

M800003401 has a factor: 12800054417
M800003401 has a factor: 64733252796071023
M800003401 has a factor: 18730039702542776497
found 3 factor(s) for M800003401 from 2^34 to 2^69 [mfaktc 0.18-pre1-Win 71bit_mul24]

M800003999 has a factor: 6400031993
M800003999 has a factor: 5133878758848163631
found 2 factor(s) for M800003999 from 2^33 to 2^69 [mfaktc 0.18-pre1-Win 71bit_mul24]

M800004311 has a factor: 1600008623
M800004311 has a factor: 9256351487895290111
found 2 factor(s) for M800004311 from 2^31 to 2^69 [mfaktc 0.18-pre1-Win 71bit_mul24]

M800004847 has a factor: 8000048471
M800004847 has a factor: 1380197213419202209
found 2 factor(s) for M800004847 from 2^33 to 2^69 [mfaktc 0.18-pre1-Win 71bit_mul24]

M800005403 has a factor: 33600226927
M800005403 has a factor: 18992736271326281
found 2 factor(s) for M800005403 from 2^35 to 2^69 [mfaktc 0.18-pre1-Win 71bit_mul24]

M800007251 has a factor: 1600014503
M800007251 has a factor: 85002820037327063
found 2 factor(s) for M800007251 from 2^31 to 2^69 [mfaktc 0.18-pre1-Win 71bit_mul24]

M800008757 has a factor: 6400070057
M800008757 has a factor: 164187461134123649273
M800008757 has a factor: 1940039026319738167
M800008757 has a factor: 26502690101897
found 4 factor(s) for M800008757 from 2^33 to 2^69 [mfaktc 0.18-pre1-Win 71bit_mul24]

M800009557 has a factor: 56000668991
M800009557 has a factor: 573355047504912077761
M800009557 has a factor: 12495915504747291689
found 3 factor(s) for M800009557 from 2^36 to 2^69 [mfaktc 0.18-pre1-Win 71bit_mul24]

M862436279 has a factor: 1724872559
M862436279 has a factor: 509958343703150891009
found 2 factor(s) for M862436279 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M862437671 has a factor: 1724875343
M862437671 has a factor: 986547654080931473
found 2 factor(s) for M862437671 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M862439531 has a factor: 1724879063
M862439531 has a factor: 541488560349621103
found 2 factor(s) for M862439531 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M862439663 has a factor: 1724879327
M862439663 has a factor: 8697849796780030151
found 2 factor(s) for M862439663 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M862446323 has a factor: 1724892647
M862446323 has a factor: 1166882518344965239417
found 2 factor(s) for M862446323 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M862449803 has a factor: 1724899607
M862449803 has a factor: 79380523255673039
found 2 factor(s) for M862449803 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M862452323 has a factor: 1724904647
M862452323 has a factor: 103494278761
M862452323 has a factor: 26768470919200553
M862452323 has a factor: 178517762372762302367
M862452323 has a factor: 50544926613807686257
found 5 factor(s) for M862452323 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M862458959 has a factor: 1724917919
M862458959 has a factor: 206990150161
M862458959 has a factor: 357041019069209634959
found 3 factor(s) for M862458959 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M862460411 has a factor: 1724920823
M862460411 has a factor: 510435025768812467849
M862460411 has a factor: 23636726266737125671
found 3 factor(s) for M862460411 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M862464059 has a factor: 1724928119
M862464059 has a factor: 10397394163320570727
found 2 factor(s) for M862464059 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M862465931 has a factor: 1724931863
M862465931 has a factor: 99918198394020824183
found 2 factor(s) for M862465931 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M862469711 has a factor: 1724939423
M862469711 has a factor: 33635373938280024473
found 2 factor(s) for M862469711 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M862472651 has a factor: 1724945303
M862472651 has a factor: 19055217184234607
found 2 factor(s) for M862472651 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M862479851 has a factor: 1724959703
M862479851 has a factor: 413990328481
M862479851 has a factor: 714116634061458201143
found 3 factor(s) for M862479851 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M862483991 has a factor: 1724967983
M862483991 has a factor: 146587766718190017313
found 2 factor(s) for M862483991 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M862484663 has a factor: 1724969327
M862484663 has a factor: 81555017960518513
found 2 factor(s) for M862484663 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M862486043 has a factor: 1724972087
M862486043 has a factor: 5708644866648421057
found 2 factor(s) for M862486043 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M719908379 has a factor: 1439816759
M719908379 has a factor: 232789913230194889
found 2 factor(s) for M719908379 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M719910071 has a factor: 1439820143
M719910071 has a factor: 2069092085162217007
found 2 factor(s) for M719910071 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M719911859 has a factor: 1439823719
M719911859 has a factor: 4394341987337
found 2 factor(s) for M719911859 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M719913983 has a factor: 1439827967
M719913983 has a factor: 40274894059742185439
found 2 factor(s) for M719913983 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M719916143 has a factor: 1439832287
M719916143 has a factor: 173954498024165765407
found 2 factor(s) for M719916143 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M719918123 has a factor: 1439836247
M719918123 has a factor: 14421511271742750433
found 2 factor(s) for M719918123 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M719918183 has a factor: 1439836367
M719918183 has a factor: 113245578616121692073
found 2 factor(s) for M719918183 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M719918723 has a factor: 1439837447
M719918723 has a factor: 48533437337878127
M719918723 has a factor: 17853201058829377
found 3 factor(s) for M719918723 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M719920559 has a factor: 1439841119
M719920559 has a factor: 17887233584232404713
found 2 factor(s) for M719920559 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M719923511 has a factor: 1439847023
M719923511 has a factor: 443649962529022924553
found 2 factor(s) for M719923511 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M719923703 has a factor: 1439847407
M719923703 has a factor: 4730478123306174401
found 2 factor(s) for M719923703 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M719928551 has a factor: 1439857103
M719928551 has a factor: 1170603823927
M719928551 has a factor: 684751402141039
found 3 factor(s) for M719928551 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M719930999 has a factor: 1439861999
M719930999 has a factor: 235880898999359710631
found 2 factor(s) for M719930999 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M719935823 has a factor: 1439871647
M719935823 has a factor: 21156990157931970833
found 2 factor(s) for M719935823 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M719938343 has a factor: 1439876687
M719938343 has a factor: 715511442128893001
found 2 factor(s) for M719938343 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M719940659 has a factor: 1439881319
M719940659 has a factor: 1276097697840137
found 2 factor(s) for M719940659 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M719941571 has a factor: 1439883143
M719941571 has a factor: 1058879983444807
M719941571 has a factor: 1798414044359
M719941571 has a factor: 135867062928147456463
found 4 factor(s) for M719941571 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M719941643 has a factor: 1439883287
M719941643 has a factor: 5910824560626593
found 2 factor(s) for M719941643 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24]

M719943923 has a factor: 1439887847
M719943923 has a factor: 84048328604913973369
M719943923 has a factor: 25820857442168282359
found 3 factor(s) for M719943923 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24][/code]

[QUOTE=Christenson;266975]finding two within a bit level is definitely rare, though not unknown[/QUOTE]I haven't looked through other ranges, but there are 705 exponents between M1,000,000 and M2,000,000 that have 2 (or more) factors of the same bitsize.

I found an interesting issue, possibly bug, in mfaktc:[code]
M862452323 has a factor: 1724904647
M862452323 has a factor: 103494278761
M862452323 has a factor: 26768470919200553
M862452323 has a factor: 178517762372762302367
M862452323 has a factor: 50544926613807686257
found 5 factor(s) for M862452323 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24][/code]The problem?
1724904647 * 103494278761 = 178517762372762302367
So it really only found 4 factors, but [i]also[/i] reported a composite factor of the two smallest factors.

How did this happen?


edit: found another example:[code]
M999916103 has a factor: 1999832207
M999916103 has a factor: 113990435743
M999916103 has a factor: 12648938702951
M999916103 has a factor: 227961744688815374801
found 4 factor(s) for M999916103 from 2^ 1 to 2^70 [mfaktc 0.18-pre1-Win 71bit_mul24][/code]
227961744688815374801 = 1999832207 * 113990435743


edit2: another example:[code]
M800000759 has a factor: 1600001519
M800000759 has a factor: 6400006073
M800000759 has a factor: 10240019438409224887
found 3 factor(s) for M800000759 from 2^33 to 2^69 [mfaktc 0.18-pre1-Win 71bit_mul24][/code]
10240019438409224887 = 1600001519 * 6400006073

If you're looking for Mersenne numbers with multiple factors in a given range, I have (at least) one.

M43363759 is divisible by 566645733218532866731538439737694884449681 (138.7 bits).

566645733218532866731538439737694884449681 = 692113095422672631017 (69.2 bits) * 818718410280162380393 (69.5 bits)

...If that's not what you're looking for, then pretend this post doesn't exist. :wink:

It just so happens that I found the composite factor with P-1, but obviously a TF from 69 to 70 would've found 'em both.

[QUOTE=KingKurly;266981]It just so happens that I found the composite factor with P-1, but obviously a TF from 69 to 70 would've found 'em both.[/QUOTE]I took a look through the top-10 P-1 factors on my site, which are all composite, and found two more that break into same-bit prime factors:[code]M24742121 : 555087078799770339769608793045705436436591887 = 20563047713721235292639 (74.1 bits) * 26994397257045406913233 (74.5 bits)
M2098193 : 60994061286916913266355388473561822515085761 = 6546629382726350366497 (72.4 bits) * 9316864866041320842913 (72.9 bits)[/code]

[QUOTE=James Heinrich;266984]I took a look through the top-10 P-1 factors on my site, which are all composite, and found two more that break into same-bit prime factors:[/QUOTE]
Another one:

[code]For M1997293:
33579362377488332973816211929918617758917702673 (154.5 bits) = 156319993046900879655881 (77.0 bits) * 214811693136484951130633 (77.5 bits)
[/code]

[QUOTE=James Heinrich;266974]Sounds like a plan. And then you should be able to quickly test it yourself, since I've given you a list of likely assignments that could probably find 2 factors in the same class.[/QUOTE]

Here's version without MORE_CLASSESS. So far I've tried only a couple of exponents on your list and haven't been lucky to have factors in the same class.

[QUOTE=Christenson;266975]b) running them through a large, relatively slow expression in parallel. [/QUOTE]

That actually makes it harder to trigger. The atomics deal only with storing thread local data to shared memory. That's only four bytes for each factor, seven lines of c code:

[CODE]
index=RES[0]++;
if(index<10) /* limit to 10 factors per thread */
{
RES[index*3 + 1]=f.d2;
RES[index*3 + 2]=f.d1;
RES[index*3 + 3]=f.d0;
}
[/CODE]

It's very negligible time comparing with the rest of computation.


[QUOTE=Christenson;266975]
Now, I'm willing to temporarily introduce a "bug" in the program to determine whether a problem exists. What if the exponent had several factors [e.g. look up the exponent "god" was using, or look through the operation Billion Digits web page] and, in addition, the CPU sieving process just "got lucky" and included them all in the same class, preferably one right after another? This is the statistically unlikely construction we are searching for.
[/QUOTE]

That's quite a lot of work for the bug I believe I've fixed. :smile:
Besides I haven't looked into the sieving process so I do not know how to modify it.

[QUOTE=Christenson;266975]
However, I'd also like to point out that in my practical mfaktc work, actually finding a factor is relatively rare, and finding two within a bit level is definitely rare, though not unknown: [url]http://www.mersenneforum.org/showpost.php?p=265202&postcount=179[/url] Therefore, detecting the problem of a collision somewhat after not quite reporting correct results isn't an unreasonable course of action. The user will be able to re-run a more careful, if slower, TF program over a very narrow range quickly and get the correct results. Something very similar happens when factors are reported to the server and the server verifies them with much less effort than that required to find them in the first place.[/QUOTE]

It looks like the approach Bdot is taking with mfakto. BTW I wonder if he's still reading this thread? Maybe he'll borrow my solution? :smile:

I've run through the entire list again, and also played with upper bit range, NumStreams, CPUStreams, GridSize, and Stages; all to no effect -- I found plenty of factors in adjacent classes, but none on that list came both in the same class. Perhaps tomorrow I can generate another list of potentials, but maybe it would help if I knew more what I was looking for -- obviously simply having two factors of similar size isn't enough to put them in the same class with any regularity.

[QUOTE=James Heinrich;266989] but maybe it would help if I knew more what I was looking for -- obviously simply having two factors of similar size isn't enough to put them in the same class with any regularity.[/QUOTE]

To be in the same class they would have the same result when the mod 120 of the factors is calculates - this would give you 16 classes. It would be mod 840 if you are using 96 classes and mod 1155 if you are using 960 classes.

[QUOTE=James Heinrich;266989]I've run through the entire list again, and also played with upper bit range, NumStreams, CPUStreams, GridSize, and Stages; all to no effect -- I found plenty of factors in adjacent classes, but none on that list came both in the same class. Perhaps tomorrow I can generate another list of potentials, but maybe it would help if I knew more what I was looking for -- obviously simply having two factors of similar size isn't enough to put them in the same class with any regularity.[/QUOTE]


mfaktc TF sieving isn't terribly smart...it just sieves and creates long lists of reasonably "probable" primes of the right form and size, in order on the CPU....and then calculates the mersenne number modulo the "probable" primes on the GPU. I'm not at all surprised if it's not smart enough to eliminate previously found large cofactors.

If we are going to prove out Apsen's method, someone (I'm not available this week, have mfaktc-primenet to work on) will need to induce the problem in a way similar to what I suggested or just do it on some simpler, faster calculation. We need either bdot or Oliver for this.

If it were mine right now, I would want to make an array of atomically writeable storage with one element for each thread/potential trial factor, and write a value in each element when the TF expression was complete, depending on success or failure -- and then count the number of success expressions there to ensure it was the same as the factors reported. I'd want to do this on the GPU, as it would eat quite a bit of CPU bus bandwidth.

I do have this dream of moving sieving off the CPU in mfaktc....it would significantly improve my multi-core LL performance...so your effort to understand how the sieving works in enough detail to make it screw up creatively won't be wasted.

[QUOTE=Christenson;266975]
However, I'd also like to point out that in my practical mfaktc work, actually finding a factor is relatively rare, and finding two within a bit level is definitely rare, though not unknown: [URL]http://www.mersenneforum.org/showpost.php?p=265202&postcount=179[/URL] [/QUOTE]

Expected number of 70 bit factors is 1/70

Probability of 2 factors is e^(-1/70)/9800 (Poisson)

David