mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Data

Reply
 
Thread Tools
Old 2009-07-11, 19:26   #23
plandon
 
May 2009
Loughborough, UK

22×11 Posts
Default

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

43112609 first divides 210778152-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
plandon is offline   Reply With Quote
Old 2009-07-11, 20:14   #24
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

22·7·389 Posts
Default

Quote:
Originally Posted by plandon View Post
43112609 first divides 210778152-1 but I doubt it has the smallest k for that exponent.
&
Quote:
Originally Posted by Uncwilly, emphasised View Post
And lest my question was unclear, I meant the largest k for the smallest factor of a mersenne number.
Uncwilly is offline   Reply With Quote
Old 2009-07-11, 20:45   #25
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

22×859 Posts
Default

Quote:
Originally Posted by axn View Post
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.
ATH is offline   Reply With Quote
Old 2009-07-12, 01:01   #26
TimSorbet
Account Deleted
 
TimSorbet's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

11×389 Posts
Default

Quote:
Originally Posted by ATH View Post
2*42643801 is not a factor of 242643801-2, same for p=43112609.

Anyway even if they were that would be a 2*k*p factor of 2p-2. This thread is about 2*k*p+1 factors of 2p-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!

Last fiddled with by TimSorbet on 2009-07-12 at 01:07
TimSorbet is online now   Reply With Quote
Old 2009-07-12, 01:18   #27
axn
 
axn's Avatar
 
Jun 2003

153C16 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
Your other, much more important, point still stands.
Ok. What _is_ the smallest factor of a Mersenne prime?

Quote:
Originally Posted by Mini-Geek View Post
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
axn is offline   Reply With Quote
Old 2009-07-12, 01:29   #28
TimSorbet
Account Deleted
 
TimSorbet's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

102678 Posts
Default

Quote:
Originally Posted by axn View Post
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 View Post
Anyway even if they were that would be a 2*k*p factor of 2p-2. This thread is about 2*k*p+1 factors of 2p-1.
Quote:
Originally Posted by axn View Post
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!

Last fiddled with by TimSorbet on 2009-07-12 at 01:33
TimSorbet is online now   Reply With Quote
Old 2009-07-12, 01:37   #29
axn
 
axn's Avatar
 
Jun 2003

22×32×151 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
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)?

Last fiddled with by axn on 2009-07-12 at 01:38
axn is offline   Reply With Quote
Old 2009-07-12, 02:13   #30
TimSorbet
Account Deleted
 
TimSorbet's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

11·389 Posts
Default

Quote:
Originally Posted by axn View Post
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 View Post
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).
TimSorbet is online now   Reply With Quote
Old 2009-07-12, 02:24   #31
axn
 
axn's Avatar
 
Jun 2003

22·32·151 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
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

Last fiddled with by axn on 2009-07-12 at 02:34
axn is offline   Reply With Quote
Old 2009-07-12, 14:45   #32
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

22·859 Posts
Default

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 2p-1 with p<=109 where 2kp+1 is the smallest factor.
Column B is the number of mersennenumbers 2p-1 with p<=109 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

Last fiddled with by ATH on 2009-07-12 at 14:47
ATH is offline   Reply With Quote
Old 2009-07-12, 15:34   #33
10metreh
 
10metreh's Avatar
 
Nov 2008

2×33×43 Posts
Default

1 is the smallest factor of any whole number.
10metreh is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 13:40.


Fri Feb 3 13:40:18 UTC 2023 up 169 days, 11:08, 1 user, load averages: 1.13, 1.08, 1.09

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔