mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2006-09-16, 23:13   #1
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

91510 Posts
Default 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
T.Rex is offline   Reply With Quote
Old 2006-09-17, 08:32   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Hi,

what is the Kn sequence? How is it generated?

Alex
akruppa is offline   Reply With Quote
Old 2006-09-17, 10:43   #3
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

3·5·61 Posts
Default 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
T.Rex is offline   Reply With Quote
Old 2006-09-17, 11:10   #4
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2×29×53 Posts
Default

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)})
ATH is online now   Reply With Quote
Old 2006-09-17, 11:10   #5
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

39316 Posts
Default

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
T.Rex is offline   Reply With Quote
Old 2006-09-17, 12:23   #6
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2·29·53 Posts
Default

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
ATH is online now   Reply With Quote
Old 2006-09-17, 22:11   #7
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

3×5×61 Posts
Default

Quote:
Originally Posted by ATH View Post
... 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
T.Rex is offline   Reply With Quote
Reply

Thread Tools


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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.