 mersenneforum.org > Math A property of Fermat numbers. Already known ?
 Register FAQ Search Today's Posts Mark Forums Read 2006-09-16, 23:13 #1 T.Rex   Feb 2004 France 2·461 Posts A property of Fermat numbers. Already known ? I'd like to know if the following property of Fermat numbers (prime or not) is already known: where: Do you know ? or do you think this can be easily built from known properties of Fermat numbers ? Examples: I don't have a proof ... It just appeared while playing with the number of cycles under x^2 modulo a Mersenne number Mq where q is a Fermat number ... I already seen: 3, 30, 4080 when playing with LLT, long time ago, but cannot remember when ... Ki numbers have Fermat numbers as factors, plus 2^k*3 , where k is quite strange ... Interestingly, we have a relation for the sum S(i) of the Ki mod Fn (from which one could find a formula for the Ki. But too late for me now ...) : 1+1+3 = 5 = 5 + 0 : A0 = 0 1+1+3+13 = 18 = 17 + 1 : A1 = 1 = A0 + 2^0 1+1+3+30+225 = 260 = 257 + 3 : A2 = 3 = A1 + 2^1 1+1+3+30+4080+61441 = 65537 + 19 : A3 = 19 = A2 + 2^4 1+1+3+30+4080+134215680+4160749569= 4294967297 + 2067 : A4 = 2067 = A3 + 2^11 So: A(i+1) = A(i) + 2^(2^i-1) . Funny ! Useful ? Tony Last fiddled with by T.Rex on 2006-09-16 at 23:15   2006-09-17, 08:32 #2 akruppa   "Nancy" Aug 2002 Alexandria 2,467 Posts Hi, what is the Kn sequence? How is it generated? Alex   2006-09-17, 10:43 #3 T.Rex   Feb 2004 France 2×461 Posts PARI code Here is the PARI code that generates the values. It comes from the formula computing the number of cycles of length L (L divides q-1, and here q=2^(2^n)+1 ) under x^2 modulo a Mersenne number 2^q-1 . I(ve only optimized the code since divisors of q-1 here are powers of 2. Code: HGFn(n,f)= { Fn=2^(2^n)+1; print("\n",Fn); print("L= 1 -> N= 1"); SS_ = 1; SS_m= 1; SS_p= 1; for(j=1, 2^n, m=2^j; S = 0; for(i=0, j, S+ = moebius(2^(j-i)) * 2^(2^i); ); SS_ += S; SS_m+= (S/m)%Fn; SS_p+= S%Fn; if(S!=0, print1("L= ",m," -> N%Fn= ",(S/m)%Fn, " (", SS_p,") ")); if(f==1, print(factor(S/m)), print(" ")); ); print("S/mi % Fn: ", SS_%Fn,"\nS % Fn", SS_m, "\n", SS_p); } HGFn(1,0) HGFn(2,0) \\ No factorisation HGFn(3,1) \\ Factorisation Tony   2006-09-17, 11:10 #4 ATH Einyen   Dec 2003 Denmark 22×17×47 Posts It seems that:   2006-09-17, 11:10 #5 T.Rex   Feb 2004 France 2·461 Posts Seems: Example:   2006-09-17, 12:23 #6 ATH Einyen   Dec 2003 Denmark 1100011111002 Posts Actually: for n>0 Inserting in your F4 formula: rewriting to: So: for n>0 So its trivial. Last fiddled with by ATH on 2006-09-17 at 13:20   2006-09-17, 22:11   #7
T.Rex

Feb 2004
France

2·461 Posts Quote:
 Originally Posted by ATH ... So its trivial.
Yes, thanks to show it. I was 95% sure of that today (I wrote the first post of this thread after midnight. Not a good moment to use my mind ...).

What is not trivial is that I've found where I saw 4080: In the paper A LLT-like test for proving the primality of Fermat numbers. I wrote 2 years ago, Chapter 5 page 6, the residues before the last step of the LLT-like iteration, for n=2, 3 and 4, are: 6, -60 and 4080 . To be compared with K2=3, K3=30 and K4=4080 here. Remind that this paper proves how to build a LLT-like test for Fermat numbers. For n=5, the residue before the last one is: 3443904229, which is prime and has no link with K5, probably because F5 is not prime ...

Also, in my other paper A primality test for Fermat numbers faster than Pépin test ?, in chapter 3.3 page 7, , and in chapter 3.4 page 8 . Vn here is a Pell number. E. Lucas thought that this could be used to speed up the primality proof for Fermat numbers (but he gave no hints !).

That may be a coincidence, but I think there is a link.
But I do not see what to do with it.
Or, simply, all these numbers are made of the product of the first Fermat numbers.

What is not trivial too is that one can build the Fermat numbers by using the moebius function:
Code:
SS=1;
for(j=1, 2^n,
m=2^j;
S = 0;
for(i=0, j, S += moebius(2^(j-i)) * 2^(2^i); );
SS += S % Fn;
if(S!=0, print1("L= ",m," -> N%Fn= ",(S/m)%Fn, "  (", S%Fn,") "));
);
Here SS is the sum of all the (S mod Fn), and SS = Fn .

Just for fun.

Tony

Last fiddled with by T.Rex on 2006-09-17 at 22:13  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post allasc And now for something completely different 1 2017-05-17 15:00 ixfd64 Math 1 2016-03-14 21:53 arithmeticae Lounge 5 2008-10-27 06:15 T.Rex Math 12 2005-09-12 07:56 T.Rex Math 4 2005-05-07 08:25

All times are UTC. The time now is 19:03.

Wed Dec 1 19:03:24 UTC 2021 up 131 days, 13:32, 1 user, load averages: 1.24, 1.22, 1.24