Fermat Number

Author

Eric W. Weisstein
November 30, 2005

This notebook downloaded from http://mathworld.wolfram.com/notebooks/PrimeNumbers/FermatNumber.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/FermatNumber.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Enumeration

Fermat/@Range[6]

Number of Digits

Table[1+Floor[(2^n)Log[10,2]],{n,0,25}]

Powers of 10

Table[Digits[Fermat[10^n]],{n,0,3}]//Timing

Block[{$MaxExtraPrecision=Infinity},Table[1+Floor[(2^(10^n))Log[10,2]],{n,0,3}]
]

Limit[(1+Log[10,Fermat[n]])/n,n->∞]

Generating Functions

Generating Function

Sum[((2^n)+1)x^n,{n,0,∞}]//FullSimplify

GeneratingFunction[((2^n)+1),n,z]//FullSimplify

Subtract[((2-3 x)/(1-3 x+2 (x^2))),(1/(1-2 x))+(1/(1-x))]//Simplify

ExponentialGeneratingFunction

Sum[((2^n)+1)((x^n)/(n!)),{n,0,∞}]//FullSimplify

DirichletGeneratingFunction

Sum[((((2^n)+1))/(n^s)),{n,∞}]

Lambert Series

Sum[((((2^n)+1)(x^n))/(1-(x^n))),{n,∞}]

Recurrence

FindLinearRecurrence[{2,3,5,9,17,33,65,129,257,513,1025,2049}]

f[0]:=2
f[1]:=3
f[n_]:=3f[n-1]-2f[n-2]

f/@Range[0,10]

g[0]:=2c
g[n_]:=2g[n-1]-1

g/@Range[0,10]

Periods of Last n Digits

Fermat/@Range[8]

Solve[(2^n)Log[10,2]+1==d,n]//Simplify

Log[2,(d-1)Log[2,10]]

Table[Ceiling[Log[2,(d-1)Log[2,10]]],{d,10}]

Period[l_List]:=Module[
{
p=NestWhileList[Rest,Rest[l],#≠Take[l,Length[#]]&,1]
},
If[Last[p]=={}||Length[p]==Length[l]-1,0,Length[p]]
]

LastDigits[d_,n_]:=Table[PowerMod[2,2^k,10^d],{k,Max[1,Ceiling[Log[2,(d-1)Log[2,10]]]],n}]+1

d=1

LastDigits[1,10]

Period[Rest[LastDigits[1,10]]]

d=1

LastDigits[2,10]

Period[LastDigits[2,10]]

d=3

LastDigits[3,30]

Period[%]

d=4

Period[LastDigits[4,200]]

d=5

Period[LastDigits[5,1000]]

d=6

Period[LastDigits[6,5000]]//Timing

d=7

Period[LastDigits[7,20000]]//Timing

d=8

Period[LastDigits[8,20000]]//Timing

Period[LastDigits[8,50000]]//Timing

Period[LastDigits[8,70000]]//Timing

l=LastDigits[8,63000];//Timing

{Length[l],MaxMemoryUsed[]/1024.^2 Megabyte}

With[{p=62500},Equal@@{Take[l,Length[l]-p],Take[l,p-Length[l]]}]

l=LastDigits[8,2 63000];//Timing

{Length[l],MaxMemoryUsed[]/1024.^2 Megabyte}

-Subtract@@@Partition[Flatten[Position[l,l[[1]]]],2,1]

With[{p=62500},Equal@@{Take[l,p],Take[l,{p+1,2p}]}]

d=9

Period[LastDigits[9,50000]]//Timing

l=LastDigits[9,313000];//Timing

{Length[l],MaxMemoryUsed[]/1024.^2 Megabyte}

With[{p=312500},Equal@@{Take[l,Length[l]-p],Take[l,p-Length[l]]}]

Conjectured

With[{p=312500},Equal@@{Take[l,Length[l]-p],Take[l,p-Length[l]]}]

1, 4, 20, 100, 500, 2500, 12500, 62500, 312500, 1562500, 7812500, …

Factors

Table[{n,Length@FermatFactors[n],ToString@(Length/@(IntegerDigits/@knFn@@@FermatFactors[n]))},{n,5,11}]//TableForm

And@@Table[Times@@knFn@@@FermatFactors[n]==Fermat[n],{n,11}]

Table[PrimeQ/@knFn@@@FermatFactors[n],{n,11}]

OrderedQ/@Table[knFn@@@FermatFactors[n],{n,11}]

First/@Table[knFn@@@FermatFactors[n],{n,11}]

Last/@Table[knFn@@@FermatFactors[n],{n,11}]

Flatten[Table[knFn@@@FermatFactors[n],{n,11}]]

?FermatList

FermatList[0,19]