New largest prime number??? - Page 4

antiroach · 2003-07-25, 06:56

oh yeah i keep forgetting that the bigger the exponents the fewer factors need to be tested. :)

kwstone · 2003-07-25, 11:38

why fewer? i don't get it. can someone please explain why?
(sorry, but my lack of mathematical knowledge is showing again)

Thomas · 2003-07-25, 12:39

Because every factor of a Mersenne number 2^p - 1 has the form 2kp+1.
So if you search for factors for two different Mersenne numbers in the same interval (lets say up to 2^78 ), the higher Mersenne number (with the higher p) has fewer possible factors. Because as p increases, there are fewer numbers of the form 2kp+1, which are lower than 2^78.

ET_ · 2003-07-25, 12:59

Quote:

I was bored, so I resumed the search, and quickly found this 84-bit factor:

M41234123412341 has a factor: 10437279104937894533506183

Thanks a lot Ernst! :(

Luigi

Fusion_power · 2003-08-10, 01:46

Here is a tweak that uses Microsoft Excel to factor numbers. Its pretty limited but interesting.

Cell Formula
B2 =INT(SQRT(A1))
C2 =B2+INT((A1-(B2*B2))/B2)
D2 =A1-(B2*C2)
E2 =IF(D2=0,E1+1,E1)
B3 =B2-1
C3 =C2+INT((C2+D2)/B3)
D3 =MOD((C2+D2),B3)
E3 =IF(D3=0,E2+1,E2)

When you have pasted the formulas into the appropriate cells, highlight row 3 and copy then paste it down to the bottom of the spreadsheet. Place a number to be factored in cell A1.

This method of factoring is not very efficient, it would take thousands of years to factor a multimillion digit number. The math could be improved by taking advantage of some better techniques.

Fusion

Maybeso · 2003-08-11, 21:49

Fusion,

Here is a previous post of mine about extending Excel's integer precision to 250 digits. It looks like your method uses int( / ), so it should work.

Again, the zzmath add-in seems to occationally leak memory - perhaps a string allocation that doesn't get cleaned up. I've learned to live with it. Worst case I just save my work, close and reopen XL, and get the memory back.

Maybeso

Fusion_power · 2003-08-12, 19:35

It is indeed a simple integer factoring algorithm that sets up a rectangular matrix then tests if the current form has a remainder. Its a bit difficult to understand exactly how it works though. But it does work and you don't have to do repetitive division by an ascending sequence of digits.

There is a way this could be done that would take about 1/1000th as much time on large numbers, still its too slow.

Thanks for the link!

:idea: Fusion

2003-08-10, 01:46	#38
Fusion_power Aug 2003 Snicker, AL 7·137 Posts	pique your interest a bit. Here is a tweak that uses Microsoft Excel to factor numbers. Its pretty limited but interesting. Cell Formula B2 =INT(SQRT(A1)) C2 =B2+INT((A1-(B2B2))/B2) D2 =A1-(B2C2) E2 =IF(D2=0,E1+1,E1) B3 =B2-1 C3 =C2+INT((C2+D2)/B3) D3 =MOD((C2+D2),B3) E3 =IF(D3=0,E2+1,E2) When you have pasted the formulas into the appropriate cells, highlight row 3 and copy then paste it down to the bottom of the spreadsheet. Place a number to be factored in cell A1. This method of factoring is not very efficient, it would take thousands of years to factor a multimillion digit number. The math could be improved by taking advantage of some better techniques. Fusion

2003-08-12, 19:35	#40
Fusion_power Aug 2003 Snicker, AL 7·137 Posts	Thanks, Maybeso It is indeed a simple integer factoring algorithm that sets up a rectangular matrix then tests if the current form has a remainder. Its a bit difficult to understand exactly how it works though. But it does work and you don't have to do repetitive division by an ascending sequence of digits. There is a way this could be done that would take about 1/1000th as much time on large numbers, still its too slow. Thanks for the link! :idea: Fusion

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
(M48) NEW MERSENNE PRIME! LARGEST PRIME NUMBER DISCOVERED!	dabaichi	News	571	2020-10-26 11:02
Yes, Virginia, there _is_ a largest prime number!	R.D. Silverman	Data	82	2013-08-14 15:58
New largest prime number found	Prime95	Miscellaneous Math	20	2008-07-29 16:58
Number of zero's in largest prime...	Heather	Math	90	2006-04-01 22:06
get the 15th largest prime number in 3 months	wfgarnett3	PSearch	1	2004-06-28 20:51

2003-07-25, 06:56	#34
antiroach Jun 2003 2²×61 Posts	oh yeah i keep forgetting that the bigger the exponents the fewer factors need to be tested. :)

2003-07-25, 11:38	#35
kwstone Jun 2003 Shanghai, China 109 Posts	why fewer? i don't get it. can someone please explain why? (sorry, but my lack of mathematical knowledge is showing again)

2003-07-25, 12:39	#36
Thomas Jul 2003 Wuerzburg, Germany 2³ Posts	Because every factor of a Mersenne number 2^p - 1 has the form 2kp+1. So if you search for factors for two different Mersenne numbers in the same interval (lets say up to 2^78 ), the higher Mersenne number (with the higher p) has fewer possible factors. Because as p increases, there are fewer numbers of the form 2kp+1, which are lower than 2^78.

2003-08-11, 21:49	#39
Maybeso Aug 2002 Portland, OR USA 2×137 Posts	Fusion, Here is a previous post of mine about extending Excel's integer precision to 250 digits. It looks like your method uses int( / ), so it should work. Again, the zzmath add-in seems to occationally leak memory - perhaps a string allocation that doesn't get cleaned up. I've learned to live with it. Worst case I just save my work, close and reopen XL, and get the memory back. Maybeso