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 91510 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: $\large F_n = \frac{\sum_{i=0}^{n+1} \ 2^i \ \times \ (K_i \ \pmod{F_n})}{(2^{n+1}-1)}$ where: $\large K_{0,1,2,3,4,5,6,...} = 1, 1, 3, 30, 4080, 134215680, 288230376084602880, ...$ Do you know ? or do you think this can be easily built from known properties of Fermat numbers ? Examples: $\large F_1 = (1*1+2*1+4*3)/3 = 5$ $\large F_2 = (1*1+2*1+4*3+8*13)/7 = 17$ $\large F_3 = (1*1+2*1+4*3+8*30+16*225)/15 = 257$ $\large F_4 = (1*1+2*1+4*3+8*30+16*4080+32*61441)/31 = 65537$ $\large F_5 = (1*1+2*1+4*3+8*30+16*4080+32*134215680+64*4160749569)/63 = 4294967297$ 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 3·5·61 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 2×29×53 Posts It seems that: $K_0 = 1, K_1 = 1, K_{n+1} = K_n * 2^{(2^{n-1}-1)} * (2^{(2^{n-1})}+1)=K_n*(2^{(2^n-1)}+2^{(2^{(n-1)}-1)})$
 2006-09-17, 11:10 #5 T.Rex     Feb 2004 France 39316 Posts Seems: $F_n = 2 + \sum_{i=0}^{n} 2^i \times K_i$ Example: $F_4 = 2 + 1*1 + 2*1 +4*3 + 8*30 +16*4080$
 2006-09-17, 12:23 #6 ATH Einyen     Dec 2003 Denmark 2·29·53 Posts Actually: $K_n = 2^{(2^{(n-1)}-n)}*(2^{(2^{(n-1)})}-1)$ for n>0 Inserting in your F4 formula: $F_4 = 2+2^0*1+2^1*2^0*(2^1-1)+2^2*2^0*(2^2-1)+2^3*2^1*(2^4-1)+2^4*2^4*(2^8-1)$ rewriting to: $F_4 = 1+2+2^1*(2^1-1)+2^2*(2^2-1)+2^4*(2^4-1)+2^8*(2^8-1)$ So: $F_n = 3+\sum_{i=1}^{n}2^{(2^{(n-1)})}*(2^{(2^{(n-1)})}-1) = 3+\sum_{i=1}^{n}(2^{(2^n)}-2^{(2^{(n-1)})}) = F_0+\sum_{i=1}^{n}(F_n-F_{n-1})$ 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

3×5×61 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, $V_{1024} mod F_4 = 4080 = K_4$, and in chapter 3.4 page 8 $V_{1395920} mod F_5 = 16776960 = K_5 / 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

 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 13:52.

Thu Apr 15 13:52:20 UTC 2021 up 7 days, 8:33, 0 users, load averages: 3.29, 2.76, 2.60