A085398 -id:A085398 - cp's OEIS frontend

A117544 Least k such that Phi(n,k), the n-th cyclotomic polynomial evaluated at k, is prime.

3, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 1, 6, 1, 4, 3, 2, 1, 2, 1, 2, 1, 4, 1, 2, 1, 1, 2, 2, 14, 3, 1, 2, 10, 2, 1, 2, 1, 25, 11, 2, 1, 5, 1, 6, 30, 11, 1, 7, 7, 2, 5, 7, 1, 3, 1, 2, 3, 1, 2, 9, 1, 85, 2, 3, 1, 3, 1, 16, 59, 7, 2, 2, 1, 2, 1, 61, 1, 7, 2, 2, 8, 5, 1, 2, 11, 4, 2, 6, 44, 4, 1, 2, 63

Offset: 1

T. D. Noe, Mar 28 2006

nonn

Note that a(n)=1 iff n is a power of a prime.
Because every cyclotomic polynomial is irreducible, it is expected that a(n) exists for all n.
Note that if p=Phi(n,k) is prime and n>1, then p==1 (mod k). - Corrected by Robert Israel, Apr 22 2019

Jinyuan Wang, Table of n, a(n) for n = 1..5000 (terms 1..1000 from T. D. Noe)

Cf. A085398, A117545 (least k such that Phi(k, n) is prime), A307687.

f:= proc(n) local C, x, k;
  C:= unapply(numtheory:-cyclotomic(n, x), x);
  for k from 1 do if isprime(C(k)) then return k fi od
end proc:
map(f, [$1..200]); # Robert Israel, Apr 22 2019

Table[k=1; While[ !PrimeQ[Cyclotomic[n,k]], k++ ]; k, {n,100}]

a(n) = my(k=1); while (!isprime(polcyclo(n, k)), k++); k; \\ Michel Marcus, Apr 22 2019

Phi(n, a(n)) = A307687(n). - Robert Israel, Apr 22 2019

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

A250177 Numbers n such that Phi_21(n) is prime, where Phi is the cyclotomic polynomial.

Original entry on oeis.org

3, 6, 7, 12, 22, 27, 28, 35, 41, 59, 63, 69, 112, 127, 132, 133, 136, 140, 164, 166, 202, 215, 218, 276, 288, 307, 323, 334, 343, 377, 383, 433, 474, 479, 516, 519, 521, 532, 538, 549, 575, 586, 622, 647, 675, 680, 692, 733, 790, 815, 822, 902, 909, 911, 915, 952, 966, 1025, 1034, 1048, 1093

Offset: 1

Eric Chen, Dec 24 2014

nonn

G. C. Greubel, Table of n, a(n) for n = 1..10000

Cf. A008864 (1), A006093 (2), A002384 (3), A005574 (4), A049409 (5), A055494 (6), A100330 (7), A000068 (8), A153439 (9), A250392 (10), A162862 (11), A246397 (12), A217070 (13), A250174 (14), A250175 (15), A006314 (16), A217071 (17), A164989 (18), A217072 (19), A250176 (20), this sequence (21), A250178 (22), A217073 (23), A250179 (24), A250180 (25), A250181 (26), A153440 (27), A250182 (28), A217074 (29), A250183 (30), A217075 (31), A006313 (32), A250184 (33), A250185 (34), A250186 (35), A097475 (36), A217076 (37), A250187 (38), A250188 (39), A250189 (40), A217077 (41), A250190 (42), A217078 (43), A250191 (44), A250192 (45), A250193 (46), A217079 (47), A250194 (48), A250195 (49), A250196 (50), A217080 (53), A217081 (59), A217082 (61), A006315 (64), A217083 (67), A217084 (71), A217085 (73), A217086 (79), A153441 (81), A217087 (83), A217088 (89), A217089 (97), A006316 (128), A153442 (243), A056994 (256), A056995 (512), A057465 (1024), A057002 (2048), A088361 (4096), A088362 (8192), A226528 (16384), A226529 (32768), A226530 (65536), A251597 (131072), A244150 (524287), A243959 (1048576).

Cf. A085398 (Least k>1 such that Phi_n(k) is prime).

a250177[n_] := Select[Range[n], PrimeQ@Cyclotomic[21, #] &]; a250177[1100] (* Michael De Vlieger, Dec 25 2014 *)

{is(n)=isprime(polcyclo(21,n))};
for(n=1,100, if(is(n)==1, print1(n, ", "), 0)) \\ G. C. Greubel, Apr 14 2018

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

A085399 Let Cn(x) be the n-th cyclotomic polynomial; a(n) is the first prime Cn(x) after Cn(1).

Original entry on oeis.org

2, 3, 7, 5, 31, 3, 127, 17, 73, 11, 12207031, 13, 8191, 43, 151, 257, 131071, 46441, 524287, 61681, 368089, 683, 11111111111111111111111, 241, 705429635566498619547944801, 2731, 262657, 15790321, 7369130657357778596659, 331, 2147483647, 65537, 599479, 43691

Offset: 1

Don Reble, Jun 28 2003

nonn

			a(11)=12207031 because C11(x) is composite for x=2,3,4 and C11(5)=12207031 is prime.

Jinyuan Wang, Table of n, a(n) for n = 1..396

Cf. A084732, A085398, A307687.

a(n) = Phi(n,A085398(n)) where Phi(n,k) is the n-th cyclotomic polynomial evaluated at k. - Jinyuan Wang, Sep 04 2022

More terms from Jinyuan Wang, Sep 04 2022

A246121 Least k such that k^(6^n)*(k^(6^n) - 1) + 1 is prime.

Original entry on oeis.org

2, 3, 88, 28, 688, 7003, 1925

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=6^n.

Numbers of this form are Generalized unique primes. a(6) generates a 306477-digit prime.

			When k = 88, k^72 - k^36 + 1 is prime. Since this isn't prime for k < 88, a(2) = 88.

C. Caldwell, Generalized unique primes

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

a(n)=k=1; while(!ispseudoprime(k^(6^n)*(k^(6^n)-1)+1), k++); k
n=0; while(n<100, print1(a(n), ", "); n++)

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

a(6) from Serge Batalov, Aug 15 2014

A253240 Square array read by antidiagonals: T(m, n) = Phi_m(n), the m-th cyclotomic polynomial at x=n.

Original entry on oeis.org

1, 1, -1, 1, 0, 1, 1, 1, 2, 1, 1, 2, 3, 3, 1, 1, 3, 4, 7, 2, 1, 1, 4, 5, 13, 5, 5, 1, 1, 5, 6, 21, 10, 31, 1, 1, 1, 6, 7, 31, 17, 121, 3, 7, 1, 1, 7, 8, 43, 26, 341, 7, 127, 2, 1, 1, 8, 9, 57, 37, 781, 13, 1093, 17, 3, 1, 1, 9, 10, 73, 50, 1555, 21, 5461, 82, 73, 1, 1, 1, 10, 11, 91, 65, 2801, 31, 19531, 257, 757, 11, 11, 1, 1, 11, 12, 111, 82, 4681, 43, 55987, 626, 4161, 61, 2047, 1, 1

Offset: 0

Eric Chen, Apr 22 2015

Outside of rows 0, 1, 2 and columns 0, 1, only terms of A206942 occur.
Conjecture: There are infinitely many primes in every row (except row 0) and every column (except column 0), the indices of the first prime in n-th row and n-th column are listed in A117544 and A117545. (See A206864 for all the primes apart from row 0, 1, 2 and column 0, 1.)
Another conjecture: Except row 0, 1, 2 and column 0, 1, the only perfect powers in this table are 121 (=Phi_5(3)) and 343 (=Phi_3(18)=Phi_6(19)).

			Read by antidiagonals:
m\n  0   1   2   3   4   5   6   7   8   9  10  11  12
------------------------------------------------------
0    1   1   1   1   1   1   1   1   1   1   1   1   1
1   -1   0   1   2   3   4   5   6   7   8   9  10  11
2    1   2   3   4   5   6   7   8   9  10  11  12  13
3    1   3   7  13  21  31  43  57  73  91 111 133 157
4    1   2   5  10  17  26  37  50  65  82 101 122 145
5    1   5  31 121 341 781 ... ... ... ... ... ... ...
6    1   1   3   7  13  21  31  43  57  73  91 111 133
etc.
The cyclotomic polynomials are:
n        n-th cyclotomic polynomial
0        1
1        x-1
2        x+1
3        x^2+x+1
4        x^2+1
5        x^4+x^3+x^2+x+1
6        x^2-x+1
...

Eric Chen, Table of n, a(n) for n = 0..5049 (first 100 antidiagonals)
Eric Weisstein's World of Mathematics, Cyclotomic polynomial
Wikipedia, Cyclotomic polynomial
Index entries for Cyclotomic polynomials, values at X

Rows 0-16 are A000012, A023443, A000027, A002061, A002522, A053699, A002061, A053716, A002523, A060883, A060884, A060885, A060886, A060887, A060888, A060889, A060890.
Columns 0-13 are A158388, A020500, A019320, A019321, A019322, A019323, A019324, A019325, A019326, A019327, A019328, A019329, A019330, A019331.
Main diagonal is A070518.
Indices of primes in n-th row for n = 1-20 are A008864, A006093, A002384, A005574, A049409, A055494, A100330, A000068, A153439, A246392, A162862, A246397, A217070, A250174, A250175, A006314, A217071, A164989, A217072, A250176.
Indices of primes in n-th column for n = 1-10 are A246655, A072226, A138933, A138934, A138935, A138936, A138937, A138938, A138939, A138940.
Indices of primes in main diagonal is A070519.
Cf. A117544 (indices of first prime in n-th row), A085398 (indices of first prime in n-th row apart from column 1), A117545 (indices of first prime in n-th column).
Cf. A206942 (all terms (sorted) for rows>2 and columns>1).
Cf. A206864 (all primes (sorted) for rows>2 and columns>1).

Table[Cyclotomic[m, k-m], {k, 0, 49}, {m, 0, k}]

t1(n)=n-binomial(floor(1/2+sqrt(2+2*n)), 2)
t2(n)=binomial(floor(3/2+sqrt(2+2*n)), 2)-(n+1)
T(m, n) = if(m==0, 1, polcyclo(m, n))
a(n) = T(t1(n), t2(n))

T(m, n) = Phi_m(n)

A206418 a(n) is the least integer k > 1 such that 1 + k^(5^n) + k^(25^n) + k^(35^n) + k^(4*5^n) is prime.

Original entry on oeis.org

2, 22, 127, 55, 1527, 18453, 5517

Offset: 0

Lei Zhou, Feb 09 2012

Phi(5^(n+1), k) = 1 + k^(5^n) + k^(2*5^n) + k^(3*5^n) + k^(4*5^n).
The primes correspond to k(1) through k(4) have a p-1 factorable up to 34% or higher, thus are proved prime by OpenPFGW.
The fifth one, Phi(5^6,18453) = 1 + 18453^3125 + 18453^6250 + 18453^9375 + 18453^12500, is a 55326-digit Fermat and Lucas PRP with 78.86% proof.  A CHG proofing is running but it will take month to complete.
The sixth one, Phi(5^7,5517), has 233857 digits and can only be factored to about 26%.  It is too big for CHG to provide a proof.

			Phi(5^2, 22) = 705429635566498619547944801 is prime, while Phi(25, k) with k = 2 to 21 are composites, so a(1) = 22.

David Broadhurst, Coppersmith--Howgrave-Graham certificate tester (2006)
Chris Caldwell, John Renze's Coppersmith-Howgrave-Graham PARI script

Cf. A085398, A153438.

Table[i = 1; m = 5^u; While[i++; cp = 1 + i^m + i^(2*m) + i^(3*m) + i^(4^m); ! PrimeQ[cp]]; i, {u, 1, 4}]

PARI
```
See Broadhurst link.
```

a(n)=my(k=2);while(!ispseudoprime(polcyclo(5,k^n)),k++);k \\ Charles R Greathouse IV, Feb 09 2012

a(n) = A085398(5^(n+1)). - Jinyuan Wang, Dec 21 2022

a(0) inserted by Jinyuan Wang, Dec 21 2022

A250201 Least b such that Phi_n(b, b-1) is prime.

Original entry on oeis.org

2, 2, 2, 2, 2, 2, 2, 2, 2, 6, 2, 2, 2, 2, 2, 2, 3, 2, 3, 4, 2, 6, 2, 4, 2, 2, 3, 3, 2, 2, 2, 2, 2, 4, 5, 40, 2, 3, 2, 7, 2, 5, 3, 3, 2, 13, 3, 2, 14, 4, 22, 3, 3, 13, 2, 34, 5, 3, 5, 2, 2, 34, 9, 2, 17, 7, 3, 2, 3, 18, 9, 47, 4, 20, 3, 2, 2, 8, 2, 4, 17, 6, 14, 2, 2, 61, 18, 2, 2

Offset: 2

Eric Chen, Mar 09 2015

nonn

Phi_n(b, b-1) = (b-1)^EulerPhi(n) * Phi_n(b/(b-1)).
This sequence is not defined at n = 1 since Phi_1(b, b-1) = 1 for all b, and 1 is not prime. Conjecture: a(n) is defined for all n>1.
If b = 1, then Phi_n(b, b-1) = 1 for all n, and 1 is not prime, so all a(n) > 1.
a(n) = 2 if and only if n is in A072226.
n        Phi_n(a, b)
1        a-b
2        a+b
3        a^2+ab+b^2
4        a^2+b^2
5        a^4+a^3*b+a^2*b^2+a*b^3+b^4
6        a^2-ab+b^2
...      ...
n        b^EulerPhi(n)*Phi_n(a/b)

			a(11) = 6 because Phi_11(b, b-1) is composite for b = 2, 3, 4, 5 and prime for b = 6.
a(37) = 40 because Phi_37(b, b-1) is composite for b = 2, 3, 4, ..., 39 and prime for b = 40.

Eric Chen, Table of n, a(n) for n = 2..490

Cf. A103794, A253633, A085398, A058013.

Table[k = 2; While[!PrimeQ[(k-1)^EulerPhi(n)*Cyclotomic[n, k/(k-1)]], k++]; k, {n, 2, 300}]

a(n) = for(k = 2, 2^16, if(ispseudoprime((k-1)^eulerphi(n) * polcyclo(n, k/(k-1))), return(k)))

cp's OEIS Frontend

A117544 Least k such that Phi(n,k), the n-th cyclotomic polynomial evaluated at k, is prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

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

A250177 Numbers n such that Phi_21(n) is prime, where Phi is the cyclotomic polynomial.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A085399 Let Cn(x) be the n-th cyclotomic polynomial; a(n) is the first prime Cn(x) after Cn(1).

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A246121 Least k such that k^(6^n)*(k^(6^n) - 1) + 1 is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A253240 Square array read by antidiagonals: T(m, n) = Phi_m(n), the m-th cyclotomic polynomial at x=n.

Views

Author

A206418 a(n) is the least integer k > 1 such that 1 + k^(5^n) + k^(25^n) + k^(35^n) + k^(4*5^n) is prime.