20131002, 01:08  #23 
"Ben"
Feb 2007
2^{2}·23·37 Posts 

20131002, 07:09  #24 
Romulan Interpreter
Jun 2011
Thailand
11·853 Posts 
You all seem like you are sure that Mr. Guy will die in 3 years...
Who the hack cares about factors for Fermat numbers? I wish that none would be found till 2026 and Mr. Guy lose the bet, but personally pay the 20 bucks with his own hand after the expiration in 2026... Last fiddled with by LaurV on 20131002 at 07:09 
20131002, 08:30  #25 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
10010010101111_{2} Posts 

20131002, 09:11  #26 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
9391_{10} Posts 
the tyranny of evil men
Always wanted to find this speech, but it is too obscure for people to know. And it's a shame. A hundred times more people probably think in terms of, say, "Five Easy Pieces", you know, or Jules"I'mtryingrealhardtobetheshepherd" from Pulp Fiction. (And by all means, go ahead thinking that we are the tyranny of evil men, complete with a Mr.9 mm in your face while reading from the Bible. "But that sh!t ain't the truth either." "Go.")
But here's an explanation that really matters, in my opinion: 
20131002, 13:08  #27 
Nov 2003
1D24_{16} Posts 

20131002, 19:00  #28  
Aug 2010
Kansas
547 Posts 
Quote:


20131002, 23:25  #29  
"Phil"
Sep 2002
Tracktown, U.S.A.
1119_{10} Posts 
Quote:
I have coded such a sieve in C, but to optimize it, the sieving routines should be done in assembly language. It would be a good learning exercise, though, to code it in a higher level language. The integer squareroot function is only called occasionally, and the C routine in GMP or MPIR would probably work just fine. Or you could just write the candidate n values to a list (there shouldn't be very many) and check to see if the resulting expression is a square using PARI or some other computational package. Try it with F5. You are sieving values of F5  (65536  n)^{2} = 1 + 131072*n  n^{2} by all small primes p to eliminate all values of n for which this expression is not a perfect square mod p. If you set up an array to check all n values from 1 to say, 20,000, you should find that the only value of n which gives you a perfect square will be 3272 = 65536  62264. There is more to my method than this, I suggested working in general on trying to find sums of squares representations of N, where N could be a Fermat number, or a composite factor of a Fermat number, or either of these two possibilities multiplied by a product of distinct prime factors which all have representations of sums of squares. Or N could be any other number whose factors are all equal to 1 mod 4. The possibilities of trying many multipliers takes this from being a deterministic method of order n^{1/2} to a probabilistic method of order n^{1/4}. The method of sieving was around for centuries before the Lehmers used an electronic device to automate and speed up the sieving. In general, we sieve on N  (sqrt(N)  n)^{2} where sqrt(N) is the integer truncation of the squareroot of N. 

20131003, 03:00  #30 
May 2007
Kansas; USA
2·7·739 Posts 
Hum. Factoring a 1133digit number or primality testing a 2.58+ billiondigit number? Which will require more CPU time assuming an "average" number of factors and difficulty for the 1133digit number? My guess is that the factorization would require more CPU time in the long run assuming that it was "average" with today's knowledge and technology.
BUT...2 factors (pun intended) weigh in favor of doing the factorization: 1. It can be distributed across 1000s of computers. To the best of my knowledge, the primality test cannot. (At least not yet anyway.) 2. We might get lucky and factor it quickly. There would be no equivalent probability of "luckiness" for the primality test. It would be interesting to see a project set up specifically to fully factor F12. Even with many computers running it, I think it would be unlikely to complete its task in 3 years. It would become the equivalent of a "Riesel Sieve" or 17orbust type project where the goal is a finite one but will likely take decades to finish. Personally, I find huge finite projects to be much more interesting than openended ones that have no purpose other than to just find primes until they get tired of searching for them. Last fiddled with by gd_barnes on 20131003 at 03:03 
20131003, 03:33  #31 
Romulan Interpreter
Jun 2011
Thailand
11×853 Posts 
third factor: (in favor of factorization)
3. you may finish the primality test and find out that F33 is composite, therefore you are back at the starting point (edit: which would  most probably  be the case, because the general belief/heuristic/probabilistic/etc is that all fermat numbers are composite, except the first 5). Last fiddled with by LaurV on 20131003 at 03:37 
20131003, 04:27  #32 
P90 years forever!
Aug 2002
Yeehaw, FL
2^{2}×17×109 Posts 

20131003, 04:32  #33 
Romulan Interpreter
Jun 2011
Thailand
11×853 Posts 
What do you mean by that? If I would be the lucky son of the gun to factor some Fm, then I WILL take his $10, and I will expressly ask him to send me a signed check... After 50 years that will worth a fortune! I will make my grandchildren happy and they won't need to work for all their lives...

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Weird freezing error, desperate for a solution.  jasong  Lounge  5  20161118 00:43 
September 2016  Batalov  Puzzles  8  20161004 14:10 
YAFU Poly Select Deadline  amphoria  YAFU  22  20160917 09:47 
Official Ernst (ewmayer) / Richard (cheesehead) feud thread  cheesehead  Soap Box  50  20140630 01:06 
Appeal for machines  dave_dm  GMPECM  0  20050629 02:23 