Near-Square Prime

Author

Eric W. Weisstein
June 20, 2016

This notebook downloaded from http://mathworld.wolfram.com/notebooks/PrimeNumbers/Near-SquarePrime.nb.

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

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

(n^2)-5

Range[10]^2-5

Position[Range[100]^2-5,_?PrimeQ]//Flatten

%^2-5

(n^2)-4

Range[10]^2-4

Factor[(n^2)-4]

Position[Range[100]^2-4,_?PrimeQ]//Flatten

%^2-4

(n^2)-3

Range[10]^2-3

Position[Range[100]^2-3,_?PrimeQ]//Flatten

%^2-3

(n^2)-2

Range[10]^2-2

Position[Range[100]^2-2,_?PrimeQ]//Flatten

%^2-2

(n^2)-1

Range[10]^2-1

Factor[(n^2)-1]

Position[Range[10^5]^2-1,_?PrimeQ]//Flatten

%^2-1

(n^2)+1

Range[10]^2+1

Position[Range[100]^2+1,_?PrimeQ]//Flatten

%^2+1

And@@PrimeQ[%]

Large

Generalized Fermat Primes

Length[IntegerDigits[(1372930^(2^17))+1]]

IntegerQ[Sqrt[(1372930^(2^17))]]

(2^17)

Simplify[Sqrt[(a^(2^b))],a>0&&b>0]

(1372930^(2^16))^2+1==(1372930^(2^17))+1

3355 digits (Broadhurst 1 Apr 2006)

Length[IntegerDigits[p=(3565874^256)^2+1]]

PrimeQ[p]//Timing

1150678 digits

http://primes.utm.edu/top20/page.php?id=12

IntegerLength[24518^262144+1]

2000 Digits

Length[IntegerDigits[p=(10^1000+19784)^2+1]]

PrimeQ[p]//Timing

4000 Digits

With[{k=10^2000},
Do[
If[Last[t=PrimeQ[(k+n)^2+1]//Timing],Print[{n,t[[1]]}]],
{n,10^6}]
]

PrimeQ[p=(10^2000+2330)^2+1]//Timing

IntegerDigits[p]//Length

6000 Digits

n=10^3000;
k=1;
While[!Last[t=PrimeQ[(k+n)^2+1]//Timing],k++];
Print[{k,t[[1]]}]

Length[IntegerDigits[(10^3000+6514)^2+1]]

10000 Digits

n=10^5000;
k=1;
While[!Last[t=PrimeQ[(k+n)^2+1]//Timing],k++];
Print[{k,t[[1]]}]

Length[IntegerDigits[(10^5000+16696)^2+1]]

20000 Digits

n=10^10000;
k=1;
While[!Last[t=PrimeQ[(k+n)^2+1]//Timing],k++];
Print[{k,t[[1]]}]

40000 Digits

n=10^20000;
k=1;
While[!Last[t=PrimeQ[(k+n)^2+1]//Timing],k++];
Print[{k,t[[1]]}]

(n^2)+2

Range[10]^2+2

Position[Range[100]^2+2,_?PrimeQ]//Flatten

%^2+2

And@@PrimeQ[%]

Large

40000 Digits

n=10^20000;
k=1;
While[!Last[t=PrimeQ[(k+n)^2+2]//Timing],k++];
Print[{k,t[[1]]}]

Broadhurst 31 Mar 2006

Digits[(2361544^384 + 2361544^256 + 1)^2 + 2]

PrimeQ[(2361544^384 + 2361544^256 + 1)^2 + 2]//Timing

Digits[(2279950^384 + 2279950^256 + 1)^2 + 2]

Broadhurst 1 Apr 2006

Length[IntegerDigits[p=(3565874^768+3565874^512+1)^2+2]]

PrimeQ[p]//Timing

Broadhurst 1 Apr 2006

Length[IntegerDigits[p=(2558^3072+13081*(2558^2048+1))^2+2]]

PrimeQ[p]//Timing

Broadhurst 4 Apr 2006

Length[IntegerDigits[p=((655*2^1854*(655*2^16686+1)+2^14832)^3+10299*((655*2^16686+1)^2+2^29664))^2+2]]

PrimeQ[p]//Timing

(n^2)+3

Range[10]^2+3

Position[Range[100]^2+3,_?PrimeQ]//Flatten

%^2+3

(n^2)+4

Range[10]^2+4

Position[Range[100]^2+4,_?PrimeQ]//Flatten

%^2+4

(n^2)+5

Range[10]^2+5

Position[Range[100]^2+5,_?PrimeQ]//Flatten

%^2+5

Carol ((((2^k)-1))^2)-2==(4^k)-(2^(k+1))-1

Carol[k_]:=(((2^k-1))^2)-2

Identities

FullSimplify[Subtract@@{(((2^k-1))^2)-2,(4^k)-(2^(k+1))-1}]

Solve[n==(4^k)-(2^(k+1))-1,k]

Enumeration

Carol/@Range[20]

Primes

A091515

Length[carol={2,3,4,6,7,10,12,15,18,19,21,25,27,55,129,132,159,171,175,315,324,358,393,435,786,1459,1707,2923,6462,14289,39012,51637,100224,108127,110953,175749,185580,226749,248949,253987,520363,653490}]

a(41) = 520363 from M. Rodenkrich, Jun 8 2016
a(42) = 653490 from M. Rodenkrich, Jun 15 2016

Flatten[Position[Carol/@Range[1000],_?PrimeQ]]//Timing

Flatten[Position[Table[(((2^k-1))^2)-2,{k,1000}],_?PrimeQ]]//Timing

IntegerLength[Carol[Last[carol]]]

Grid[MapIndexed[{#2[[1]],#,IntegerLength[(2^#+1)^2-2]}&,carol],Dividers->All,Alignment->Decimal]

Prime Test

Do[
Print[{i,FullSimplify[((Log[1+(Sqrt[2+carol[[i]]])])/(Log[2]))],PrimeQ[carol[[i]]]//Timing}],
{i,Length[carol]}]

Kynea ((((2^k)+1))^2)-2==(4^k)+(2^(k+1))-1

Kynea[k_]:=(((2^k+1))^2)-2

Position[Table[(2^n+1)^2-2,{n,0,10^3}],_?PrimeQ]-1//Flatten

Select[Table[(2^n+1)^2-2,{n,0,50}],PrimeQ]

Identities

FullSimplify[Subtract@@{(((2^k+1))^2)-2,(4^k)+(2^(k+1))-1}]

Solve[n==(4^k)+(2^(k+1))-1,k]

Enumeration

Kynea/@Range[15]

Primes

FullSimplify[((Log[-1+(Sqrt[2+#])])/(Log[2]))&[(2^110615+1)^2-2]]

checked to 102695, & 108843-117300

A091513

Length[kynea={0,1,2,3,5,8,9,12,15,17,18,21,23,27,32,51,65,87,180,242,467,491,501,507,555,591,680,800,1070,1650,2813,3281,4217,5153,6287,6365,10088,10367,37035,45873,69312,102435,106380,108888,110615,281621,369581,376050,442052,621443,661478}]

a(47) = 376050, a(48) = 442052 from M. Rodenkirch, Feb 9, 2016
a(49) = 621443 from M. Rodenkirch, Jun 8, 2016
a(50) = 661478 from M. Rodenkirch, Jun 19, 2016

Kynea/@Take[kynea,10]

Grid[MapIndexed[{#2[[1]]-1,#,IntegerLength[(2^#+1)^2-2]}&,kynea],Dividers->All,Alignment->Decimal]

Prime Test

$Version

SystemInformation["Small"]

Do[
Print[{i,kynea[[i]],PrimeQ[Kynea[kynea[[i]]]]//Timing}],
{i,Length[kynea]}]

Prime Test (old)

Do[
Print[{i,kynea[[i]],PrimeQ[Kynea[kynea[[i]]]]//Timing}],
{i,Length[kynea]}]