mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > FermatSearch

Reply
 
Thread Tools
Old 2020-11-19, 07:55   #56
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

24×571 Posts
Default

Quote:
Originally Posted by retina View Post
The main difference between F33 and pi is that
me, me, pick me, pick me!
...one is integer and the other is irrational?...
LaurV is offline   Reply With Quote
Old 2020-11-19, 10:33   #57
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

2·34 Posts
Wink

And the difference between F0 and pi is negative. /JeppeSN
JeppeSN is offline   Reply With Quote
Old 2020-11-19, 15:50   #58
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

484310 Posts
Default

Quote:
Originally Posted by JeppeSN View Post
MM82589933 = 2^(2^82589933-1) - 1 is a prime.

Now please prove me wrong - any prime factor of that number would be the largest prime ever found.

/JeppeSN
Sure, write me some error free code that runs in O(ln(n)) or faster and I'll try it.
The odds of n being prime ~1/ln(n), are very much against your assertion of primality for MMp51*.

Now could we all please return to on-topic for the thread? Perhaps some comments on posts 12 or 13?

I read in https://www.mersenneforum.org/showpo...1&postcount=64 that Ernst is making progress in coding P-1 factoring in Mlucas v20.

Last fiddled with by kriesel on 2020-11-19 at 15:53
kriesel is offline   Reply With Quote
Old 2020-11-27, 02:33   #59
bbb120
 
bbb120's Avatar
 
Feb 2019
China

5910 Posts
Default

Quote:
Originally Posted by bsquared View Post
I didn't know much about the algorithm either, really, but after looking at it for a few minutes I'll illustrate how I think it works. I'm going by the recursive description here:
numberworld.org/y-cruncher/internals/binary-splitting-library.html#pi_chudnovsky

Say you want to compute pi to 1000 decimal places. With ~15 digits per term, you need about 67 terms. So n=67 and we therefore need to compute P(0,67) and Q(0,67), after which we can get pi by doing a few more multiplications/divisions/additions by constants.

I am not going to spell out every single recursive step, but lets look at just the P term, starting with P(0,67):

Code:
Need P(0,67), Q(0,67)
Pick m=33
P(0,67)=P(0,33)Q(33,67)+P(33,67)R(0,33)
Q(0,67)=Q(0,33)Q(33,67)
R(0,67)=R(0,33)R(33,67)

Need P(0,33)
Pick m=16
P(0,33)=P(0,16)Q(16,33)+P(16,33)R(0,16)

Need P(0,16)
Pick m=8
P(0,16)=P(0,8)Q(8,16)+P(8,16)R(0,8)

Need P(0,8)
Pick m=4
P(0,8)=P(0,4)Q(4,8)+P(4,8)R(0,4)

Need P(0,4)
Pick m=2
P(0,4)=P(0,2)Q(2,4)+P(2,4)R(0,2)

Need P(0,2)
Pick m=1
P(0,2)=P(0,1)Q(1,2)+P(1,2)R(0,1)
Now we have a bunch of terms of the form P(b-1,b), Q(b-1,b), and R(b-1,1), for which we have explicit formulas. Following the recursion back upward, each multiplication is now of two (large) numbers of approximately equal size, so we can take advantage of asymptotically fast multipliers.

The number of steps in the recursion is logarithmic in 'n'. So, you can see now, hopefully, that we are not really iterating anything. We are recursively multiplying numbers of equal size, using fast multiplication algorithms. Hence arriving at O(n (log n)^3).

Fermat tests *do* have to iterate, on each binary bit of the exponent. Each iteration also uses fast multiplication algorithms, but we have way more terms to iterate over than we would have steps in the recursive computation of pi.

I encourage you to go through all of the recursive steps in this process. Getting your hands dirty like this is a great way to learn something. For a small enough target (pi to 1000 digits is probably doable), you can do all of the computing with mathematica and track the intermediate products in a text file.
http://www.numberworld.org/y-crunche...#pi_chudnovsky
maybe this is answer
bbb120 is offline   Reply With Quote
Old 2021-01-01, 01:56   #60
jyb
 
jyb's Avatar
 
Aug 2005
Seattle, WA

66216 Posts
Default

Quote:
Originally Posted by bbb120 View Post
F33=2^(2^33)+1=2^8589934592+1
(F33-1)/2=2^4294967296
3^((F33-1)/2)=-1(mod F33) <=> F33 is a prime number
it needs 4294967296 iterations
You may want to check your math again. How many iterations are required?
jyb is offline   Reply With Quote
Old 2021-01-02, 01:29   #61
Happy5214
 
Happy5214's Avatar
 
"Alexander"
Nov 2008
The Alamo City

23×5×11 Posts
Default

Quote:
Originally Posted by jyb View Post
You may want to check your math again. How many iterations are required?
Yeah, that's off slightly. (Several orders of magnitude, in fact.) It's more like 2^(2^33-1) iterations.

Last fiddled with by Happy5214 on 2021-01-02 at 01:35
Happy5214 is offline   Reply With Quote
Old 2021-01-02, 10:58   #62
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

100011101100002 Posts
Default

Quote:
Originally Posted by bbb120 View Post
F33=2^(2^33)+1=2^8589934592+1
(F33-1)/2=2^4294967296
Yep, in his mind, 29/2 is not 28, but it is 24.5

Last fiddled with by LaurV on 2021-01-02 at 10:59
LaurV is offline   Reply With Quote
Old 2021-01-02, 13:24   #63
sweety439
 
Nov 2016

22·691 Posts
Default

I think that F33 may be prime!!!

Since (see http://www.prothsearch.com/fermat.html) F20 was proven composite in 1987, and F24 was proven composite in 1999, and the largest known prime number in the electronic era has grown roughly as a double exponential function of the year, and indeed the Fermat numbers have double exponential function behavior, thus, the Fermat number Fn may be a linear function of the year (if the Fn is composite and with no small prime factor (like F20, F24, and F33), or if the Fn is prime, which year the primality of Fn will be known):

Code:
F20 = 1987 **
F21 = 1990
F22 = 1993
F23 = 1996
F24 = 1999 **
F25 = 2002
F26 = 2005
F27 = 2008
F28 = 2011
F29 = 2014
F30 = 2017
F31 = 2020
F32 = 2023
F33 = 2026
See the table, F33 corresponding to the year 2026, and 11/13/2026 is the technological singularity, predicted by Heinz von Foerster, by the formula, in 2026 the world population will be infinity.
sweety439 is offline   Reply With Quote
Old 2021-01-02, 15:56   #64
Viliam Furik
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

32510 Posts
Default

Quote:
Originally Posted by sweety439 View Post
I think that F33 may be prime!!!
I hope that was a joke.
Viliam Furik is offline   Reply With Quote
Old 2021-01-02, 16:26   #65
mathwiz
 
Mar 2019

100011112 Posts
Default

Quote:
Originally Posted by sweety439 View Post
I think that F33 may be prime!!!
Well, I mean, it *may* be prime. And it may not be prime. The latter is just way, way, way, way, WAY more likely....
mathwiz is offline   Reply With Quote
Old 2021-01-02, 16:27   #66
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

26×5×13 Posts
Default

Quote:
Originally Posted by sweety439 View Post
<snip>
by the formula, in 2026 the world population will be infinity.
That's what I would call a good reason to question the formula's validity.

I am reminded of a (then) fellow grad student who told me of a problem his actuarial science prof had assigned, as an exercise in showing the unsustainability of exponential growth: Given the current population, and assuming the population grows at 1% per year, (unrealistically assuming sufficient inflow of resources, and making some assumption about how densely human beings can be packed in) calculate how long it would be until the human population were literally expanding at the speed of light.

Meanwhile, back in the real world,as documented here, a factor for F103 has been found:
Quote:
103 7595155767819149 105 31 Dec 2020 P. Strasser & Woltman


Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


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

Sun Jan 17 00:02:32 UTC 2021 up 44 days, 20:13, 0 users, load averages: 1.61, 1.66, 1.58

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.