Largest known k? - Page 3

plandon · 2009-07-11, 19:26

axn is of course right.
Also 2*43112609 does divide 2*(2^43112608-1)

43112609 first divides 2^10778152-1 but I doubt it has the smallest k for that exponent.

Uncwilly · 2009-07-11, 20:14

Quote:

Originally Posted by plandon

43112609 first divides 2^10778152-1 but I doubt it has the smallest k for that exponent.

&

Quote:

Originally Posted by Uncwilly, emphasised

And lest my question was unclear, I meant the largest k for the smallest factor of a mersenne number.

ATH · 2009-07-11, 20:45

Quote:

Originally Posted by axn

Really? How do you figure?

If you agree that M(p) is a factor of M(p), then that is exactly what this thread discusses (hint:- 2kp = M(p)-1 and 2kp+1 = M(p) are equivalent)

Sorry, instead of thinking logically I tried to test it numerically and misscalculated somehow.

TimSorbet · 2009-07-12, 01:01

Quote:

Originally Posted by ATH

2*42643801 is not a factor of 2^42643801-2, same for p=43112609.

Anyway even if they were that would be a 2*k*p factor of 2^p-2. This thread is about 2*k*p+1 factors of 2^p-1.

Actually they are factors. Your other, much more important, point still stands.

Code:

(20:00) gp > Mod(2^43112609-2,2*43112609)
%2 = Mod(0, 86225218)
(20:00) gp > Mod(2^42643801-2,2*42643801)
%3 = Mod(0, 85287602)

Edit: In case anyone's wondering, this seems to happen every time the n in 2^n-1 is prime, and so can not be used to predict Mersenne primes. Sorry!

axn · 2009-07-12, 01:18

Quote:

Originally Posted by Mini-Geek

Your other, much more important, point still stands.

Ok. What _is_ the smallest factor of a Mersenne prime?

Quote:

Originally Posted by Mini-Geek

this seems to happen every time the n in 2^n-1 is prime

There is nothing "seems to" about it. Hint: Fermat's Little Theorem

TimSorbet · 2009-07-12, 01:29

Quote:

Originally Posted by axn

Ok. What _is_ the smallest factor of a Mersenne prime?

I meant this following point, not this thread's focus:

Quote:

Originally Posted by ATH

Anyway even if they were that would be a 2*k*p factor of 2^p-2. This thread is about 2*k*p+1 factors of 2^p-1.

Quote:

Originally Posted by axn

There is nothing "seems to" about it. Hint: Fermat's Little Theorem

Ah. Could've guessed there'd be a simple and certain reason/proof, I just didn't know what it was!

axn · 2009-07-12, 01:37

Quote:

Originally Posted by Mini-Geek

I meant this following point, not this thread's focus

So did I (as explained in Post #22 second point). Which is why asked: what is the smallest factor of a mersenne prime? Do you consider it as the Mersenne prime itself? Or do you consider it as having no factor (for the purpose of this thread)?

TimSorbet · 2009-07-12, 02:13

Quote:

Originally Posted by axn

So did I (as explained in Post #22 second point).

Oh, I misunderstood and thought you were talking about Mersenne numbers and not Mersenne primes. I just misread.

Quote:

Originally Posted by axn

Which is why asked: what is the smallest factor of a mersenne prime? Do you consider it as the Mersenne prime itself? Or do you consider it as having no factor (for the purpose of this thread)?

I'd say no...I don't have any particularly good reason for this, just that then this thread would have a trivial answer: (Mp-1)/2p where p is the exponent of the current largest known Mersenne prime (currently 43112609).

axn · 2009-07-12, 02:24

Quote:

Originally Posted by Mini-Geek

just that then this thread would have a trivial answer: (Mp-1)/2p where p is the exponent of the current largest known Mersenne prime (currently 43112609).

And that's exactly what plandon did in post #15 (except he got the exponent wrong). A bit cheeky, for sure.

EDIT:- btw, I agree with your sentiments on post #8

ATH · 2009-07-12, 14:45

I got curious about k-values so I made a program find factors 2kp+1 with fixed k for p up to 1 billion (like primenet v5). There is 50,847,534 primes up to 1 billion minus the 47 known mersenne primes, so 50,847,487 primes left.

I discovered k=+/-2 (mod 8) gives no factors. This comes from the fact that 2kp+1 has to be +/- 1 (mod 8): http://primes.utm.edu/notes/proofs/MerDiv.html
2kp + 1 = +1/-1 (mod 8) => 2kp = 0/-2 (mod 8) (this is same as 6/8) => kp = 0/3/4/7 (mod 8). Primes p is always 1,3,5 or 7 mod 8, so:
p=1 (mod 8): kp = 0/3/4/7 => k=0/3/4/7 (mod 8)
p=3 (mod 8): kp = 0/3/4/7 => k=0/1/4/5 (mod 8)
p=5 (mod 8): kp = 0/3/4/7 => k=0/3/4/7 (mod 8)
p=7 (mod 8): kp = 0/3/4/7 => k=0/1/4/5 (mod 8)
So k=2/6 (mod 8) gives no factors.

Column A is the number of mersennenumbers 2^p-1 with p<=10⁹ where 2kp+1 is the smallest factor.
Column B is the number of mersennenumbers 2^p-1 with p<=10⁹ where 2kp+1 is a factor, not necessarily the smallest. I left out B when it was same as A.

Code:

	   A		   B
k=1	1655600
k=2	      0
k=3	 773434
k=4	 409773		 442260
k=5	 191162
k=6	      0
k=7	  83083		  88872
k=8	 109830		 114789
k=9	  81930		  90882
k=10	      0
k=11	  32549		  34274
k=12	  94461		 104326
k=13	  20504		  24545
k=14	      0
k=15	  40699		  44859
k=16	  24778		  29716
k=17	  12909		  13999
k=18	      0
k=19       9752           11171
k=20      23567           25772
k=21      17568           21032
k=22          0
k=23       6754            7636
k=24      23341           27013
k=25       6584            8409
k=26          0
k=27       9483           10696
k=28      10005           12160
k=29       4370            4839
k=30          0
k=31       3714            4323
k=32       6909            7716
k=33       6793            8161
k=34          0
k=35       4617            5208
k=36      10360           12435
k=37       2340            3022
k=38          0
k=39       4925            5708
k=40       5310            6643
k=41       2174            2420
k=42          0
k=43       1947            2311
k=44       4037            4573
k=45       4316            5315
k=46          0
k=47       1633            1850
k=48       5954            7180
k=49       1472            1990
k=50          0
k=51       2860            3337
k=52       2640            3326
k=53       1319            1493
k=54          0
k=55       1627            1956
k=56       2724            3187
k=57       2148            2681
k=58          0
k=59       1089            1275
k=60       5043            6193
k=61        774            1133
k=62          0
k=63       2030            2444
k=64       1537            2009
k=65       1210            1427
k=66          0
k=67        762             937
k=68       1566            1845
k=69       1393            1805
k=70          0
k=71        770             894
k=72       2601            3214
k=73        576             800
k=74          0
k=75       1668            2014
k=76       1164            1523
k=77        770             899
k=78          0
k=79        544             696
k=80       1505            1794
k=81        994            1300
k=82          0
k=83        510             608
k=84       2317            2870
k=85        571             829
k=86          0
k=87        990            1226
k=88        959            1241
k=89        464             549
k=90          0
k=91        499             622
k=92        884            1076
k=93        807            1020
k=94          0
k=95        562             688
k=96       1468            1852
k=97        325             440
k=98          0
k=99        812             989
k=100       874            1160
k=101       339             410
k=102         0
k=103       329             415
k=104       730             858
k=105       940            1218
k=106         0
k=107       276             324
k=108      1116            1482
k=109       252             369
k=110         0
k=111       623             755
k=112       614             811
k=113       307             381
k=114         0
k=115       352             451
k=116       507             615
k=117       537             683
k=118         0
k=119       293             365
k=120      1170            1523
k=121       228             329
k=122         0
k=123       474             587
k=124       409             577
k=125       321             381
k=126         0
k=127       212             272
k=128       428             529
k=129       417             521
k=130         0
k=131       243             292
k=132       838            1088
k=133       220             324
k=134         0
k=135       527             662
k=136       378             509
k=137       217             247
k=138         0
k=139       171             214
k=140       603             734
k=141       320             456
k=142         0
k=143       172             230
k=144       617             785
k=145       197             299
k=146         0
k=147       356             470
k=148       276             389
k=149       138             178
k=150         0
k=151       155             203
k=152       337             413
k=153       324             429
k=154         0
k=155       192             237
k=156       594             761
k=157       126             176
k=158         0 
k=159       272             346
k=160       341             460
k=161       169             212
k=162         0
k=163       138             175
k=164       258             328
k=165       373             512
k=166         0
k=167       117             147
k=168       585             743
k=169       124             175
k=170         0
k=171       221             284
k=172       202             289
k=173       131             155
k=174         0
k=175       184             228
k=176       252             315
k=177       205             290
k=178         0
k=179       117             140
k=180       511             680
k=181        81             122
k=182         0
k=183       204             270
k=184       193             266
k=185       131             163
k=186         0
k=187       107             151
k=188       205             251
k=189       219             294
k=190         0
k=191        99             123
k=192       386             507
k=193        73             117
k=194         0
k=195       278             344
k=196       187             275
k=197        91             117
k=198         0
k=199        94             119
k=200       223             284
k=201       171             241
k=202         0
k=203       100             135
k=204       354             454
k=205       113             162
k=206         0
k=207       179             229
k=208       175             235
k=209       122             144
k=210         0
k=211        75              95
k=212       164             202
k=213       143             192
k=214         0
k=215       105             137
k=216       288             384
k=217        73             101
k=218         0
k=219       170             218
k=220       204             291
k=221        81              99
k=222         0
k=223        68              84
k=224       154             201
k=225       173             231
k=226         0
k=227        61              85
k=228       269             352
k=229        66              93
k=230         0
k=231       167             208
k=232       148             202
k=233        76              92
k=234         0
k=235        66              89
k=236       147             190
k=237       108             155
k=238         0
k=239        75              88
k=240       304             407
k=241        64              93
k=242         0
k=243       104             140
k=244       119             168
k=245       100             118
k=246         0
k=247        71              90
k=248       117             148
k=249       102             151
k=250         0
k=251        46              61
k=252       261             352
k=253        48              69
k=254         0
k=255       157             200

Total	3790227

10metreh · 2009-07-12, 15:34

1 is the smallest factor of any whole number.

2009-07-11, 19:26	#23
plandon May 2009 Loughborough, UK 2²×11 Posts	axn is of course right. Also 243112609 does divide 2(2^43112608-1) 43112609 first divides 2^10778152-1 but I doubt it has the smallest k for that exponent. Last fiddled with by plandon on 2009-07-11 at 19:30 Reason: brackets added

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Largest Known PRP	a1call	Probability & Probabilistic Number Theory	32	2017-11-29 13:59
Largest known prime	Unregistered	Information & Answers	24	2008-12-13 08:13
Largest 64 bit prime?	amcfarlane	Math	6	2004-12-26 23:15
largest factor ,i think.	heryu	Miscellaneous Math	10	2004-09-08 11:15
need Pentium 4s for 5th largest prime search (largest proth)	wfgarnett3	Lounge	7	2002-11-25 06:34

2009-07-12, 15:34	#33
10metreh Nov 2008 2×3³×43 Posts	1 is the smallest factor of any whole number.