A056993 -id:A056993 - cp's OEIS frontend

A153438 Least k > 1 such that k^(3^n)*(k^(3^n)+1) + 1 is prime.

2, 2, 2, 21, 209, 72, 260, 17, 3311, 4469, 94259, 55599

Offset: 0

Pierre CAMI, Dec 26 2008

Numbers of the form k^n*(k^n+1) + 1 with n > 0, k > 1 may be primes only if n has the form 3^j. When n is even k^(4*n) + k^(2*n) + 1 = (k^(2*n)+1)^2 - (k^n)^2 = (k^(2*n)+k^n+1)*(k^(2*n)-k^n+1) so composite. But why if n odd > 3 and not a power of 3 is k^n*(k^n+1) + 1 always composite?
Phi[3^(n+1),k] = k^(3^n)*(k^(3^n)+1)+1. When m <> 3^n in k^m*(k^m+1)+1, Phi[3m,k] < k^m*(k^m+1)+1 and is a divisor of it. - Lei Zhou, Feb 09 2012
The prime number corresponding to the 10th term is a 587458-digit number. - Lei Zhou, Jul 04 2014
x^(2*k) + x^k + 1 = (x^(3*k) - 1)/(x^k - 1) is the product over n dividing 3k but not dividing k of cyclotomic polynomials Phi(n). If k is a power of 3, n = 3k is the only such divisor and we have a single irreducible cyclotomic polynomial Phi(3k). Otherwise we have the product of more than one polynomial, with integer values > 1 for integer x > 1, and thus always composite numbers. - Martin Becker, Jun 22 2021

Lei Zhou, Prime Database Entry, July 04, 2014.
R. Propper and S. Batalov, Prime Database Entry, Nov 17, 2023.

Cf. A056993, A085398, A101406, A153436.

Table[i = 1; m = 3^u; While[i++; cp = 1 + i^m + i^(2*m); ! PrimeQ[cp]]; i, {u, 1, 7}] (* Lei Zhou, Feb 01 2012 *)

a(n) = my(k=2); while (!isprime(k^(3^n)*(k^(3^n)+1) + 1), k++); k; \\ Michel Marcus, Jan 01 2023

a(n) = A085398(3^(n+1)). - Jinyuan Wang, Jan 01 2023

3311 from Lei Zhou using OpenPFGW, Feb 01 2012
4469 from Lei Zhou using OpenPFGW, Feb 09 2012
New term, 94259, from Lei Zhou using OpenPFGW, Jul 04 2014
Name and Comment corrected by Robert Price, Nov 11 2018
a(0) inserted by Jinyuan Wang, Jan 01 2023
a(11) from Ryan Propper and Serge Batalov, Nov 17 2023

A103795 Minimal base b such that (b^prime(n)+1)/(b+1) is prime.

Original entry on oeis.org

2, 2, 2, 2, 2, 2, 2, 2, 7, 2, 16, 61, 2, 6, 10, 6, 2, 5, 46, 18, 2, 49, 16, 70, 2, 5, 6, 12, 92, 2, 48, 89, 30, 16, 147, 19, 19, 2, 16, 11, 289, 2, 12, 52, 2, 66, 9, 22, 5, 489, 69, 137, 16, 36, 96, 76, 117, 26, 3, 159, 10, 16, 209, 2, 16, 23, 273, 2, 460, 22, 3, 36, 28, 329, 43, 69, 86

Offset: 2

Lei Zhou, Feb 23 2005

nonn

Conjecture: sequence is defined for any n>=2.

			(2^prime(2)+1)/(2+1) = 3 is prime, so a(2)=2;
(2^prime(10)+1)/(2+1) = 178956971 has a factor of 59;
(3^prime(10)+1)/(3+1) = 17157594341221 has a factor of 523;
...
(7^prime(10)+1)/(7+1) = 402488219476647465854701 is prime, so a(10)=7.

Cf. A056993, A066180, A085398.

Do[p=Prime[k]; n=2; cp=(n^p+1)/(n+1); While[ !PrimeQ[cp], n=n+1; cp=(n^p+1)/(n+1)]; Print[n], {k, 2, 200}]

a(n) = A085398(2*prime(n)) for n >= 2. - Jinyuan Wang, Dec 17 2022

A205506 Least positive integer m > 1 such that 1 - m^k + m^(2*k) is prime, where k=A003586(n).

Original entry on oeis.org

2, 2, 6, 2, 3, 5, 7, 3, 4, 3, 6, 93, 2, 88, 5, 33, 5, 196, 15, 106, 174, 196, 14, 342, 207, 28, 372, 14, 47, 25, 569, 646, 141, 129, 278, 5, 421, 224, 629, 26, 424, 1081, 688, 246, 736, 4392, 124, 484, 759, 791, 4401, 863, 2854, 410, 1044, 22, 848, 1402, 2006

Offset: 1

Lei Zhou, Feb 01 2012

1 - m^k + m^(2*k) equals Phi(6*k,m) when k=2^p*3^q, p>=0, q>=0, which may be prime numbers for certain positive integer m>1.
The Mathematica program given here generates the first 33 terms.  Further terms were generated by OpenPFGW.
a(62)=7426, while A003586(62)=3^8=6561.

			n=1, A003586(1)=1, when m=2, 1-2^1+2^2=3 is prime, so a(1)=2;
n=2, A003586(2)=2, when m=2, 1-2^2+2^4=13 is prime, so a(2)=2;
...
n=7, A003586(7)=9, when m=7, 1-7^9+7^18=1628413557556843 is prime, so a(7)=7.

Cf. A003586, A033845, A056993, A085398, A153438.

fQ[n_] := n == 3 EulerPhi@n; a = Select[6 Range@500, fQ]/6; l =
Length[a]; Table[m = a[[j]]; i = 1;
While[i++; cp = 1 - i^m + i^(2*m); ! PrimeQ[cp]]; i, {j, 1, l}]

from itertools import count
from sympy import isprime, integer_log
def A205506(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return n+x-sum((x//3**i).bit_length() for i in range(integer_log(x,3)[0]+1))
    k = bisection(f,n,n)
    return next(filter(lambda m:isprime(1-m**k+m**(k<<1)),count(2))) # Chai Wah Wu, Oct 22 2024

a(n) = A085398(6*A003586(n)). - Jinyuan Wang, Jan 01 2023

a(n) is smallest positive m such that Phi(A033845(n),m) is prime. - Chai Wah Wu, Sep 16 2024

A123599 Smallest generalized Fermat prime of the form a^(2^n) + 1, where base a>1 is an integer; or -1 if no such prime exists.

Original entry on oeis.org

3, 5, 17, 257, 65537, 185302018885184100000000000000000000000000000001

Offset: 0

Alexander Adamchuk, Nov 14 2006

nonn

First 5 terms {3, 5, 17, 257, 65537} = A019434 are the Fermat primes of the form 2^(2^n) + 1. Note that for all currently known a(n) up to n = 17 last digit is 7 or 1 (except a(0) = 3 and a(1) = 5). Corresponding least bases a>1 such that a^(2^n) + 1 is prime are listed in A056993.

The last-digit behavior clearly continues since, for any a, we have that a^(2^2) will be either 0 or 1 modulo 5. So for n >= 2, a(n) is 1 or 2 modulo 5, and odd. - Jeppe Stig Nielsen, Nov 16 2020

Charles R Greathouse IV, Table of n, a(n) for n = 0..9
Eric Weisstein's World of Mathematics, Generalized Fermat Number.

Cf. A000215, A019434, A056993.

Cf. A006093, A005574, A000068, A006314, A006313, A006315, A006316, A056994, A056995, A057465, A057002.

Do[f=Min[Select[ Table[ i^(2^n) + 1, {i, 2, 500} ],PrimeQ]];Print[{n,f}],{n,0,9}]

A070025 At these values of k, the 1st, 2nd, 3rd and 4th cyclotomic polynomials all give prime numbers.

Original entry on oeis.org

6, 150, 2730, 9000, 9240, 35280, 41760, 43050, 53280, 65520, 76650, 96180, 111030, 148200, 197370, 207480, 213360, 226380, 254280, 264600, 309480, 332160, 342450, 352740, 375450, 381990, 440550, 458790, 501030, 527070, 552030, 642360, 660810

Offset: 1

Labos Elemer, May 07 2002

Numbers k such that k-1, k+1, k^2+k+1 and k^2+1 are all primes.

			For k = 6: 5, 7, 43 and 37 are prime values of the first 4 cyclotomic polynomials.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A070155, A070156, A070157, A000068, A006313, A006314, A006315, A006316, A056993, A056994, A056995, A005574, A057465, A057002, A070020, A070042.

lst={};Do[If[PrimeQ[n-1]&&PrimeQ[n+1]&&PrimeQ[1+n+n^2]&&PrimeQ[1+n^2], AppendTo[lst, n]], {n, 10^6}];lst (* Vladimir Joseph Stephan Orlovsky, Aug 19 2008 *)
Select[Range[10^6], Function[k, AllTrue[Cyclotomic[#, k] & /@ Range@ 4, PrimeQ]]] (* Michael De Vlieger, Jul 18 2017 *)

is(k) = isprime(k-1) && isprime(k+1) && isprime(k^2+1) && isprime(k^2+k+1); \\ Amiram Eldar, Sep 24 2024

A235390 Numbers k such that k^(2^i)+1 are primes for i=0...5.

Original entry on oeis.org

1, 7072833120, 9736020616, 12852419340, 36632235070, 41452651506, 44619665520, 53569833730, 54673378956, 66032908020, 69449109580, 69936419290, 82549220670, 99574135650, 106362659256, 108208833756, 113366066976, 136032409906, 167385272500, 174963279540, 195763339776

Offset: 1

Alex Ratushnyak, Jan 09 2014

nonn

A subsequence of A070694.
Conjecture: the sequence is infinite.
For n=4 and n=9, a(n)*2+1 is also a prime.
The first term greater than 1 such that k^(2^6) + 1 is also prime, is a(148) = 2072005925466, see A335805. - Jeppe Stig Nielsen, Aug 18 2020

			k=7072833120 is in the sequence because the following are six primes: 7072833121, 7072833120^2+1, k^4+1, k^8+1, k^16+1, k^32+1.

Jeppe Stig Nielsen, Table of n, a(n) for n = 1..101 (calculated by Yves Gallot (pers. communication), terms n = 2..94 from Martin Raab)
Yves Gallot, GFP (Generalized Fermat Progressions) / gfp6, software for calculating this sequence.

Cf. A000040, A006093, A019434, A056993, A070325, A070655, A070689, A070694, A090872, A335805.

a(1)=1 inserted by Jeppe Stig Nielsen, Aug 11 2020

A291944 a(n) is the least A for which there exists B with 0 < B < A so that A^(2^n) + B^(2^n) is prime.

Original entry on oeis.org

2, 2, 2, 2, 2, 9, 11, 27, 14, 13, 47, 22, 53, 72, 216, 260, 124, 1196, 200

Offset: 0

Jeppe Stig Nielsen, Mar 09 2018

A^(2^n) + B^(2^n) is called an (extended) generalized Fermat prime, and often denoted F_n(A, B); or xGF(n, A, B).

If we require B=1, we get A056993. Therefore a(n) <= A056993(n).

			a(10)=47 corresponds to the prime number 47^1024 + 26^1024, the smallest prime number of the form A^1024 + B^1024 (or more precisely, it minimizes A).
a(14)=216 corresponds to the prime number 216^16384 + 109^16384, a 38248-decimal digit PRP, the smallest prime number of the form A^16384 + B^16384. - _Serge Batalov_, Mar 16 2018

Jeppe Stig Nielsen, List of [n, A, B] tuples for this sequence.
Chris K. Caldwell, The Prime Database: 72^8192 + 43^8192 (related to a(13)).
Henri Lifchitz & Renaud Lifchitz, 1196^131072+595^131072, a(17).
Henri Lifchitz & Renaud Lifchitz, 200^262144+119^262144, a(18).

Cf. A056993, A253633, A111635.

f[n_] := Monitor[ Block[{a = 2, b}, While[a < Infinity, b = 1 +Mod[a, 2]; While[b < a, If[ PrimeQ[a^2^n + b^2^n], Goto[fini]]; b+=2]; a++]; Label[fini]; {a, b}], {a, b}]; Array[f, 14, 0] (* Robert G. Wilson v, Mar 10 2018 *)

for(n=0,30,for(a=2,10^100,forstep(b=(a % 2)+1,a-1,2,if(ispseudoprime(a^(2^n)+b^(2^n)),print1(a,", ");next(3)))))

a(14) = 216 (and B = 109) from Serge Batalov, Mar 16 2018
a(15) = 260 (and B = 179) from Serge Batalov, Mar 16 2018
a(16) = 124 (and B = 57) from Serge Batalov, Mar 16 2018
a(17) = 1196 (and B = 595) from Kellen Shenton, Aug 10 2022
a(18) = 200 (and B = 119) from Kellen Shenton, Aug 27 2022

A070020 At these values of k the first, 2nd and 3rd cyclotomic polynomials all give prime numbers.

Original entry on oeis.org

6, 12, 138, 150, 192, 348, 642, 1020, 1092, 1230, 1620, 1788, 1932, 2112, 2142, 2238, 2658, 2688, 2730, 3330, 3540, 3918, 4002, 4158, 5010, 5640, 6090, 6450, 6552, 6702, 7950, 8088, 9000, 9042, 9240, 9462, 9768, 10008, 10092, 10272, 10302, 10332

Offset: 1

Labos Elemer, May 07 2002

Numbers k such that k-1, k+1 and k^2+k+1 are all primes.

			For k = 6: 5, 7 and 43 are prime values of the first 3 cyclotomic polynomials.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..5000 from Michael De Vlieger)

Cf. A070155, A070156, A070157, A000068, A006313, A006314, A006315, A006316, A056993, A056994, A056995, A005574, A057465, A057002, A070025, A070042.

psQ[n_]:=And@@PrimeQ[{n-1,n+1,n^2+n+1}]; Select[Range[11000],psQ] (* Harvey P. Dale, Nov 05 2011 *)
Select[Range[10500], AllTrue[Cyclotomic[Range@ 3, #], PrimeQ] &] (* Michael De Vlieger, Dec 08 2018 *)

is(k) = isprime(k-1) && isprime(k+1) && isprime(k^2+k+1); \\ Amiram Eldar, Sep 24 2024

A246119 a(n) is the least k such that k^(2^n)*(k^(2^n) - 1) + 1 is prime.

Original entry on oeis.org

2, 2, 2, 5, 4, 2, 5, 196, 14, 129, 424, 484, 22, 5164, 7726, 13325, 96873, 192098, 712012, 123447

Offset: 0

Serge Batalov, Aug 14 2014

Numbers of the form k^m*(k^m-1)+1 with m > 0, k > 1 may be primes only if m is 3-smooth, because these numbers are Phi(6,k^m) and cyclotomic factorizations apply to any prime divisors >3. This series is a subset of A205506 with only m=2^n.
Trivially, a(n) <= a(n+1)^2. This upper bound, indeed, holds for a(4) = a(5)^2, a(7) = a(8)^2 and a(11) = a(12)^2.
The numbers of this form are Generalized Unique primes (see Links section).
a(16)=96873 corresponds to a prime with 653552 decimal digits.
The search for a(17) which corresponds to a 1385044-decimal digit prime was performed on a small Amazon EC2 cloud farm (40 GRID K520 GPUs), at a cost of approximately $1000 over three weeks.
a(18) <= 712012 corresponds to a prime with 3068389 decimal digits. - Serge Batalov, Jan 15 2018
a(19) <= 123447 corresponds to a prime with 5338805 decimal digits. - Serge Batalov, Jan 15 2018
a(20) <= 465859 corresponds to a prime with 11887192 decimal digits (not all lower candidates have been checked). This is the largest known non-Mersenne prime at the time of its discovery. - Serge Batalov, May 31 2023

C. Caldwell, Generalized unique primes
C. Caldwell, The Prime Pages, Phi_3(-465859^1048576)

Cf. A056993, A085398, A101406, A153436, A153438, A205506, A246120, A246121, A298206.

Table[SelectFirst[Range@ 200, PrimeQ[#^(2^n) (#^(2^n) - 1) + 1] &], {n, 0, 9}] (* Michael De Vlieger, Jan 15 2018 *)

a(n)=k=1;while(!ispseudoprime(k^(2^n)*(k^(2^n)-1)+1),k++);k
n=0;while(n<100,print1(a(n),", ");n++) \\ Derek Orr, Aug 14 2014

a(n) = A085398(3*2^(n+1)). - Jinyuan Wang, Jan 01 2023

a(16) from Serge Batalov, Dec 30 2014
a(17) from Serge Batalov, Feb 10 2015
a(18-19) from Serge Batalov, May 31 2023

A246120 Least k such that k^(3^n)*(k^(3^n) - 1) + 1 is prime.

Original entry on oeis.org

2, 6, 7, 93, 15, 372, 421, 759, 7426, 9087

Offset: 0

Serge Batalov, Aug 14 2014

Numbers of the form k^m*(k^m - 1) + 1 with m > 0, k > 1 may be primes only if m is 3-smooth, because these numbers are Phi(6,k^m) and cyclotomic factorizations apply to any prime divisors > 3. This sequence is a subset of A205506 with only m=3^n, which is similar to A153438.

Search limits: a(10) > 35000, a(11) > 3500.

			When k = 7, k^18 - k^9 + 1 is prime. Since this isn't prime for k < 7, a(2) = 7.

Cf. A056993, A085398, A101406, A153436, A153438, A205506, A246119, A246121.

a246120[n_Integer] := Module[{k = 1},
  While[! PrimeQ[k^(3^n)*(k^(3^n) - 1) + 1], k++]; k]; a246120 /@ Range[0, 9] (* Michael De Vlieger, Aug 15 2014 *)

a(n)=k=1;while(!ispseudoprime(k^(3^n)*(k^(3^n)-1)+1),k++);k
n=0;while(n<100,print1(a(n),", ");n++) \\ Derek Orr, Aug 14 2014

a(n) = A085398(2*3^(n+1)). - Jinyuan Wang, Jan 01 2023

cp's OEIS Frontend

A153438 Least k > 1 such that k^(3^n)*(k^(3^n)+1) + 1 is prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A103795 Minimal base b such that (b^prime(n)+1)/(b+1) is prime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A205506 Least positive integer m > 1 such that 1 - m^k + m^(2*k) is prime, where k=A003586(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

Formula

A123599 Smallest generalized Fermat prime of the form a^(2^n) + 1, where base a>1 is an integer; or -1 if no such prime exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A070025 At these values of k, the 1st, 2nd, 3rd and 4th cyclotomic polynomials all give prime numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A235390 Numbers k such that k^(2^i)+1 are primes for i=0...5.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A291944 a(n) is the least A for which there exists B with 0 < B < A so that A^(2^n) + B^(2^n) is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A070020 At these values of k the first, 2nd and 3rd cyclotomic polynomials all give prime numbers.

Views

Author

Keywords

Comments