A property of Fermat numbers. Already known ?

T.Rex · 2006-09-16, 23:13

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

akruppa · 2006-09-17, 08:32

Hi,

what is the K_n sequence? How is it generated?

Alex

T.Rex · 2006-09-17, 10:43

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

ATH · 2006-09-17, 11:10

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)})$

T.Rex · 2006-09-17, 11:10

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$

ATH · 2006-09-17, 12:23

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.

T.Rex · 2006-09-17, 22:11

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

2006-09-16, 23:13	#1
T.Rex Feb 2004 France 929 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 = (11+21+43)/3 = 5$ $\large F_2 = (11+21+43+813)/7 = 17$ $\large F_3 = (11+21+43+830+16225)/15 = 257$ $\large F_4 = (11+21+43+830+164080+3261441)/31 = 65537$ $\large F_5 = (11+21+43+830+164080+32134215680+644160749569)/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^k3 , 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, 12:23	#6
ATH Einyen Dec 2003 Denmark 3×1,117 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^01+2^12^0(2^1-1)+2^22^0(2^2-1)+2^32^1(2^4-1)+2^42^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*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Property of pseudoprime numbers by base 2 AND / OR 3	allasc	And now for something completely different	1	2017-05-17 15:00
new property of prime numbers discovered?	ixfd64	Math	1	2016-03-14 21:53
Curious property of Mersenne numbers.	arithmeticae	Lounge	5	2008-10-27 06:15
A property of prime Mersenne numbers under LLT	T.Rex	Math	12	2005-09-12 07:56
LLT numbers, linkd with Mersenne and Fermat numbers	T.Rex	Math	4	2005-05-07 08:25

2006-09-17, 08:32	#2
akruppa "Nancy" Aug 2002 Alexandria 9A3₁₆ Posts	Hi, what is the K_n sequence? How is it generated? Alex

2006-09-17, 11:10	#4
ATH Einyen Dec 2003 Denmark 3×1,117 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 3A1₁₆ Posts	Seems: $F_n = 2 + \sum_{i=0}^{n} 2^i \times K_i$ Example: $F_4 = 2 + 11 + 21 +43 + 830 +16*4080$