20070618, 18:58  #12  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}·1,877 Posts 
Quote:
Not to be picky, but I can compute 2^2^n + 1 on any modern computer without *any* squarings. Of course converting it to decimal takes a bit more work............. 

20070618, 19:21  #13 
P90 years forever!
Aug 2002
Yeehaw, FL
2^{3}·1,019 Posts 
You just explained why the book is wrong. The book says you need n squarings when in fact you need 2^{n} squarings.

20070618, 20:01  #14  
∂^{2}ω=0
Sep 2002
República de California
11755_{10} Posts 
Quote:
"According to the book 2^2^n+1 requires n squarings..." and misinterpreted that as meaning "to calculate 2^2^n+1 requires n squarings," which would have been correct, just not relevant to the ensuing primality test of that number. 

20070618, 20:16  #15 
"Jason Goatcher"
Mar 2005
3·7·167 Posts 
I was hoping people would forget my stupid mistake. The book was right, I was wrong.
The mistake I made was that the example given involved F(5), when I thought it involved F(32), F(5) is 2^2^5, so requires 32 squarings. Sorry for the trouble. Last fiddled with by jasong on 20070618 at 20:17 
20070618, 23:53  #16  
Feb 2007
2^{4}×3^{3} Posts 
Quote:
Is it admissible to store the number in a "sparse" format (e.g., only list indices of nonzero bits) ? 

20070619, 00:38  #17 
∂^{2}ω=0
Sep 2002
República de California
5×2,351 Posts 

20070619, 12:57  #18 
Bronze Medalist
Jan 2004
Mumbai,India
2^{2}·3^{3}·19 Posts 
Records!
Well Jasong if its of any help to you I will give you the results in 2004. The largest known Fermat prime is F4 = 65537. The largest known composite Fermat number is F2145351 discovered by J.B. Cosgrave on feb 21, 2003. This number has the factor 3 x 2^2145353 + 1. It has 645817 digits. Among others the program by G. Woltman was essential for the discovery. At the end of May 2003 there was a total of 214 Fermat numbers known to be composite. Mally 
20070619, 13:24  #19 
Feb 2007
660_{8} Posts 
You oversimplify a bit. I mean, { Fn } is only a very limited subset of Z. What I was suggesting is to code /any/ number, using (maybe conditionally (and maybe recursively)) a sparse format where only indices of nonzero bits are stored.
Just like its commonly done for (sparse) matrices : you can do any operation allowed in the algebra of matrices with them. Or with polynomials: you may store them as a vector of (all) coefficients, but also as a list of the (nonzero) monomials. When calculating by hand, we usually adopt the latter. In fact, my idea amounts to that, where any number is seen as a polynomial in 2. Since this is only a matter of storage (and of efficiently defining the usual operations depending on the storage format), it does not affect the properties of the algebra. PS: I think your English is getting a bit too much "franglaisé"... ;) Last fiddled with by m_f_h on 20070619 at 13:36 Reason: + recursively, + polynomial interpretation 
20070619, 15:01  #20  
Einyen
Dec 2003
Denmark
3434_{10} Posts 
Quote:
http://www.prothsearch.net/fermat.html 

20070619, 15:53  #21  
∂^{2}ω=0
Sep 2002
República de California
5·2,351 Posts 
Quote:
More generally, one can use the same technique to do a base2 probableprime test on any number of form 2^{n} +1 and thereby prove in elementary fashion that such a number can only possibly be prime if n is itself a power of 2. 

20070619, 22:01  #22  
Feb 2004
France
1645_{8} Posts 
Quote:
Tony 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
ecm with Fermat numbers  ET_  FermatSearch  1  20160802 19:40 
P1/P+1 on Fermat numbers  ATH  Operazione Doppi Mersennes  2  20150125 06:27 
LLT numbers, linkd with Mersenne and Fermat numbers  T.Rex  Math  4  20050507 08:25 
Fermat Numbers  devarajkandadai  Math  8  20040727 12:27 
Factoring Fermat Numbers  Axel Fox  Software  14  20030704 18:57 