mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Archived Projects > ElevenSmooth

 
 
Thread Tools
Old 2003-10-08, 13:12   #1
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

5·269 Posts
Default More factors found with a new program

I've just written a program in UBASIC in order to find factors of M(3326400):

10 for A=1 to 100000000
20 J=(2*A+1)*3326400+1
30 if J@3=0 or J@5=0 or J@7=0 or J@11=0 then 220
40 K=modpow(2,3326400,J)
50 if K>1 then 220
60 if modpow(13,J-1,J)<>1 and modpow(17,J-1,J)<>1 then 220
70 Expon=3326400
80 if modpow(2,Expon\2,J)<>1 then 140 else Expon=Expon\2
90 if modpow(2,Expon\2,J)<>1 then 140 else Expon=Expon\2
100 if modpow(2,Expon\2,J)<>1 then 140 else Expon=Expon\2
110 if modpow(2,Expon\2,J)<>1 then 140 else Expon=Expon\2
120 if modpow(2,Expon\2,J)<>1 then 140 else Expon=Expon\2
130 if modpow(2,Expon\2,J)<>1 then 140 else Expon=Expon\2
140 if modpow(2,Expon\3,J)<>1 then 170 else Expon=Expon\3
150 if modpow(2,Expon\3,J)<>1 then 170 else Expon=Expon\3
160 if modpow(2,Expon\3,J)<>1 then 170 else Expon=Expon\3
170 if modpow(2,Expon\5,J)<>1 then 190 else Expon=Expon\5
180 if modpow(2,Expon\5,J)<>1 then 190 else Expon=Expon\5
190 if modpow(2,Expon\7,J)<>1 then 200 else Expon=Expon\7
200 if modpow(2,Expon\11,J)<>1 then 210 else Expon=Expon\11
210 print J;"divides M(";Expon;")"
220 next A


In less than one hour it found the following factors:

56951294401 divides M( 13860 )
88365816001 divides M( 277200 )
129486772801 divides M( 184800 )
245997259201 divides M( 15120 )
276254193601 divides M( 46200 )
642304555201 divides M( 3780 )
934635240001 divides M( 25200 )
1195092360001 divides M( 110880 )
1490170651201 divides M( 110880 )
2529298094401 divides M( 13860 )
3171273336001 divides M( 75600 )
3180287880001 divides M( 831600 )
3445362043201 divides M( 138600 )
4283754552001 divides M( 138600 )
6277838212801 divides M( 27720 )
6523812187201 divides M( 83160 )
6820427275201 divides M( 73920 )
7135197854401 divides M( 207900 )
7321709102401 divides M( 27720 )
7698377332801 divides M( 23760 )
7885387540801 divides M( 7920 )
8179574356801 divides M( 73920 )
9173203300801 divides M( 11088 )
9829076241601 divides M( 55440 )
9880169745601 divides M( 138600 )
10424834481601 divides M( 60480 )
12540657729601 divides M( 5040 )
13473919166401 divides M( 69300 )
14027691585601 divides M( 46200 )
14385073348801 divides M( 69300 )
14798731147201 divides M( 332640 )
14900731876801 divides M( 110880 )
15737381352001 divides M( 1108800 )
16289330904001 divides M( 25200 )
17068593326401 divides M( 415800 )
17085657758401 divides M( 25200 )
20380816209601 divides M( 554400 )
20982648456001 divides M( 158400 )
21567728952001 divides M( 4200 )
23500600200001 divides M( 831600 )
24542508513601 divides M( 7920 )
29599288488001 divides M( 184800 )
32057358379201 divides M( 60480 )
33319846929601 divides M( 83160 )
36861538190401 divides M( 36960 )
36963465739201 divides M( 50400 )
37830804580801 divides M( 277200 )
39750642993601 divides M( 55440 )
40707834552001 divides M( 166320 )
42539816088001 divides M( 138600 )
44406445406401 divides M( 69300 )
45455265979201 divides M( 18480 )
47058258139201 divides M( 1260 )
49527917208001 divides M( 277200 )
54095297256001 divides M( 1663200 )
54788572238401 divides M( 55440 )
59025780475201 divides M( 158400 )
60445820635201 divides M( 221760 )
60712910596801 divides M( 207900 )
61880011300801 divides M( 55440 )
66321014760001 divides M( 55440 )
68302870574401 divides M( 69300 )
68637819096001 divides M( 95040 )
68766238094401 divides M( 55440 )
69686001000001 divides M( 554400 )
75163956436801 divides M( 277200 )
77237920267201 divides M( 207900 )
82523024337601 divides M( 41580 )
83582715585601 divides M( 41580 )
85809986539201 divides M( 221760 )
90686628648001 divides M( 50400 )
91599346238401 divides M( 277200 )
94173800212801 divides M( 332640 )
94386490228801 divides M( 415800 )
98014627972801 divides M( 55440 )
98757652593601 divides M( 554400 )
102422606932801 divides M( 138600 )
104208557745601 divides M( 34650 )
108002909044801 divides M( 665280 )
108068259499201 divides M( 92400 )
112637515636801 divides M( 1663200 )
116337922747201 divides M( 75600 )
117425515838401 divides M( 554400 )
117538207617601 divides M( 43200 )
122700055262401 divides M( 138600 )
125889640430401 divides M( 151200 )
130775343652801 divides M( 138600 )
137826167371201 divides M( 110880 )
139898434737601 divides M( 665280 )
149246856158401 divides M( 332640 )
152858534875201 divides M( 554400 )
156183810552001 divides M( 118800 )
160915202078401 divides M( 3080 )
162810724507201 divides M( 554400 )
177203871028801 divides M( 1663200 )
177909147662401 divides M( 69300 )
178277573073601 divides M( 110880 )
180505349640001 divides M( 415800 )
184952520244801 divides M( 277200 )
188172774820801 divides M( 277200 )
194486987217601 divides M( 16632 )
197172043992001 divides M( 41580 )
200010720571201 divides M( 18900 )
211835972779201 divides M( 554400 )
219380075006401 divides M( 221760 )
226937815473601 divides M( 18480 )
228026685902401 divides M( 138600 )
229761736142401 divides M( 277200 )
232537889707201 divides M( 39600 )
238511079576001 divides M( 554400 )
251133949281601 divides M( 7920 )
256396859611201 divides M( 277200 )
257978695867201 divides M( 18480 )
264015825796801 divides M( 69300 )
265925146132801 divides M( 69300 )
276941431166401 divides M( 332640 )
286333834248001 divides M( 1108800 )
295978025851201 divides M( 20790 )
311020339291201 divides M( 46200 )
314020698868801 divides M( 110880 )
315965132683201 divides M( 831600 )
318420694468801 divides M( 332640 )
330735479659201 divides M( 138600 )
332854150305601 divides M( 7200 )
335632479336001 divides M( 83160 )
345083313960001 divides M( 41580 )
348712356484801 divides M( 166320 )
359673762571201 divides M( 1663200 )
367871336078401 divides M( 59400 )
371240087803201 divides M( 55440 )
376797078504001 divides M( 20790 )
389887946078401 divides M( 277200 )
392592615307201 divides M( 277200 )
400450004539201 divides M( 221760 )
412279574414401 divides M( 1108800 )
413736411211201 divides M( 69300 )
415114924593601 divides M( 415800 )
427635793569601 divides M( 277200 )
430119024350401 divides M( 92400 )
432727620494401 divides M( 50400 )
436919230440001 divides M( 138600 )
447025718462401 divides M( 1980 )
448099267492801 divides M( 184800 )
465550406798401 divides M( 69300 )
468542523556801 divides M( 69300 )
478938381768001 divides M( 46200 )
480789729604801 divides M( 13860 )
483564559262401 divides M( 13860 )
494562622276801 divides M( 831600 )
494681441284801 divides M( 665280 )
510863578948801 divides M( 831600 )
515047731105601 divides M( 831600 )
529264851192001 divides M( 69300 )
530227970395201 divides M( 25200 )
530446089096001 divides M( 55440 )
548837821224001 divides M( 3600 )
559371711729601 divides M( 69300 )
588092248497601 divides M( 207900 )
595389318955201 divides M( 277200 )
611590330612801 divides M( 36960 )
616719679329601 divides M( 27720 )
619119084830401 divides M( 30240 )
624446434180801 divides M( 14850 )
629641552478401 divides M( 18900 )
635122960718401 divides M( 166320 )
646508828750401 divides M( 166320 )
656815645886401 divides M( 554400 )
662910222744001 divides M( 332640 )
664117446484801 divides M( 1663200 )

Notice that more factors can be found in two ways:

1) Changing the range in the first line

2) Changing the number 3326400 by a divisor of it in all lines where this number appear.
alpertron is offline  
Old 2003-10-08, 13:56   #2
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

54116 Posts
Default

This completes the 15-digit range for the increment 3326400:

670397170766401 divides M( 47520 )
673640603697601 divides M( 831600 )
686149803662401 divides M( 15840 )
688217121345601 divides M( 83160 )
693327396484801 divides M( 55440 )
695285042760001 divides M( 9240 )
703034304033601 divides M( 138600 )
704541682152001 divides M( 1663200 )
713682576129601 divides M( 55440 )
734378685163201 divides M( 55440 )
738529320513601 divides M( 554400 )
754730405352001 divides M( 138600 )
760954505572801 divides M( 277200 )
771645362241601 divides M( 3326400 )
778124544120001 divides M( 50400 )
779022359438401 divides M( 83160 )
788111388187201 divides M( 8400 )
804209660654401 divides M( 138600 )
823444122916801 divides M( 92400 )
866863748520001 divides M( 47520 )
872093734142401 divides M( 415800 )
873816217243201 divides M( 29700 )
883782816840001 divides M( 207900 )
889851973348801 divides M( 5040 )
899510821070401 divides M( 83160 )
924326057793601 divides M( 59400 )
955742162760001 divides M( 27720 )
959266164225601 divides M( 277200 )
963319861627201 divides M( 2100 )
980925226142401 divides M( 1663200 )
989059564785601 divides M( 46200 )
1016287146705601 divides M( 277200 )

Notice that there is a number that divides the primitive part of M( 3326400 ).
alpertron is offline  
Old 2003-10-08, 14:19   #3
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

3·787 Posts
Default Re: More factors found with a new program

Quote:
Originally posted by alpertron

56951294401 divides M( 13860 )
But your Java applet tells me that
56951294401 = 37 x 41 x 43 x 881 x 991


I'd be surprised if there are any new prime factors in the list - the ECM work should have found most factors below 20 digits by now.
wblipp is offline  
Old 2003-10-08, 14:47   #4
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

5×269 Posts
Default Re: Re: More factors found with a new program

Quote:
Originally posted by wblipp
But your Java applet tells me that
56951294401 = 37 x 41 x 43 x 881 x 991


I'd be surprised if there are any new prime factors in the list - the ECM work should have found most factors below 20 digits by now.
Yes, you are right. It appears that these numbers above are Fermat-pseudoprimes base a lot of numbers. When I added a filter to exclude composites no factors were generated by the program (at least for A less than 1000000).
alpertron is offline  
Old 2003-10-08, 17:54   #5
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

118910 Posts
Default Re: Re: Re: More factors found with a new program

Quote:
Originally posted by alpertron
When I added a filter to exclude composites no factors were generated by the program (at least for A less than 1000000).
Can you paste the source here? I know this probably find us any new factors, but still i'm interested.

Code:
30 if J@3=0 or J@5=0 or J@7=0 or J@11=0 then 220
Is this just a check if the factor can be divided by small primes?

Code:
60 if modpow(13,J-1,J)<>1 and modpow(17,J-1,J)<>1 then 220
What about this?
smh is offline  
Old 2003-10-08, 18:31   #6
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

101010000012 Posts
Default Re: Re: Re: Re: More factors found with a new program

Quote:
Originally posted by smh
Can you paste the source here? I know this probably find us any new factors, but still i'm interested.

Code:
30 if J@3=0 or J@5=0 or J@7=0 or J@11=0 then 220
Is this just a check if the factor can be divided by small primes?

Code:
60 if modpow(13,J-1,J)<>1 and modpow(17,J-1,J)<>1 then 220
What about this?
The line 30 is a bad idea to check for small factors. The selected values of J are such that they are never divisible by 3, 5, 7 or 11 (the remainder of the division is always 1). It would have been better to use 13, 17, 19 and 23, for instance. The idea here is to make the loop faster so if the number has a small factor the program does not compute the modular exponentiation.

The line 60 tests for Fermat pseudoprimes. If the program passes to the next line it is because the number is a pseudoprime. Notice that the AND must be replaced by OR.

For some unknown reason, almost all numbers written above are pseudoprimes for a lot of bases (it has obviously a mathematical explanation that I cannot found at this moment). Even replacing AND by OR this filters only a few numbers. In general, the pseudoprimality test discards almost all composites, but this is not the case here.

The line 60 should be replaced by a complete primality test.
alpertron is offline  
Old 2003-10-08, 19:48   #7
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

5·269 Posts
Default

I changed the program so all factors of M (n) that have factors less than 100 are discarded, so the list given in the first two messages of this thread was reduced a lot (and the program runs much faster):

88365816001 (433 x 3697 x 55201) divides M( 277200 )
4283754552001 (181 x 281 x 353 x 397 x 601) divides M( 138600 )
9829076241601 (prime) divides M( 55440 )
68302870574401 (199 x 397 x 8317 x 103951) divides M( 69300 )
94173800212801 (541 x 757 x 12097 x 19009) divides M( 332640 )
94386490228801 (127 x 199 x 617 x 2161 x 2801) divides M( 415800 )
116337922747201 (1201 x 1601 x 2801 x 21601) divides M( 75600 )
180505349640001 (prime) divides M( 415800 )
295978025851201 (463 x 4159 x 9241 x 16633) divides M( 20790 )
335632479336001 (113 x 241 x 617 x 1321 x 15121) divides M( 83160 )
760954505572801 (211 x 631 x 661 x 1801 x 4801) divides M( 277200 )
804209660654401 (1321 x 7393 x 8317 x 9901) divides M( 138600 )
872093734142401 (113 x 241 x 401 x 3697 x 21601) divides M( 415800 )

So the entire list given at the beginning has only two primes and they are already known.

It is obvious that this program cannot find a new factor, but for the record this is the source code:

10 for A=1 to 160000000
20 J=(2*A+1)*3326400+1
30 if J@13=0 or J@17=0 or J@19=0 or J@23=0 then 260
40 if J@29=0 or J@31=0 or J@37=0 or J@41=0 then 260
50 if J@43=0 or J@47=0 or J@53=0 or J@59=0 then 260
60 if J@61=0 or J@67=0 or J@71=0 or J@73=0 then 260
70 if J@79=0 or J@83=0 or J@89=0 or J@97=0 then 260
80 K=modpow(2,3326400,J)
90 if K>1 then 260
100 if modpow(13,J-1,J)<>1 or modpow(17,J-1,J)<>1 then 260
110 Expon=3326400
120 if modpow(2,Expon\2,J)<>1 then 180 else Expon=Expon\2
130 if modpow(2,Expon\2,J)<>1 then 180 else Expon=Expon\2
140 if modpow(2,Expon\2,J)<>1 then 180 else Expon=Expon\2
150 if modpow(2,Expon\2,J)<>1 then 180 else Expon=Expon\2
160 if modpow(2,Expon\2,J)<>1 then 180 else Expon=Expon\2
170 if modpow(2,Expon\2,J)<>1 then 180 else Expon=Expon\2
180 if modpow(2,Expon\3,J)<>1 then 210 else Expon=Expon\3
190 if modpow(2,Expon\3,J)<>1 then 210 else Expon=Expon\3
200 if modpow(2,Expon\3,J)<>1 then 210 else Expon=Expon\3
210 if modpow(2,Expon\5,J)<>1 then 230 else Expon=Expon\5
220 if modpow(2,Expon\5,J)<>1 then 230 else Expon=Expon\5
230 if modpow(2,Expon\7,J)<>1 then 240 else Expon=Expon\7
240 if modpow(2,Expon\11,J)<>1 then 250 else Expon=Expon\11
250 print J;"divides M(";Expon;")"
260 next A

The factors inside parenthesis were inserted manually using my applet.
alpertron is offline  
Old 2003-10-13, 11:09   #8
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29×41 Posts
Default

I'm puzzeled about this line:

20 J=(2*A+1)*3326400+1

I changed that program to find factors of all numbers of the form 2^P-1 but didn't find any until i changed the above line in:

20 J=2*A*3326400+1

Factors of Mersenne numbers are of the form 2*A*P+1, why adding an extra 1?
smh is offline  
Old 2003-10-15, 10:29   #9
Maybeso
 
Maybeso's Avatar
 
Aug 2002
Portland, OR USA

2×137 Posts
Default

Quote:
I'm puzzeled about this line:
20 J=(2*A+1)*3326400+1
smh:
The 2*p is 'in' 3326400, the (2*A+1) steps through the odd integers. ie:
(odds) *( 2 * p ) + 1 =
(2a+1)*3326400 + 1

(I got this because I had just read the 3*2^n - 1 forum)
Maybeso is offline  
 

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Biggest factors found by P-1 TheMawn Lounge 29 2014-12-14 12:43
No factors found aketilander PrimeNet 9 2011-05-17 11:32
Fermat 12 factors already found? UberNumberGeek Factoring 6 2009-06-17 17:22
program to verify factors found by sr(x)sieve? mdettweiler Software 16 2009-03-08 02:06
Program to verify factors HiddenWarrior LMH > 100M 5 2005-04-18 09:00

All times are UTC. The time now is 02:12.

Sun Apr 11 02:12:06 UTC 2021 up 2 days, 20:52, 1 user, load averages: 1.77, 1.65, 1.59

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.