A097792 -id:A097792 - cp's OEIS frontend

A097764 Numbers of the form (kp)^p for prime p and k=1,2,3,....

4, 16, 27, 36, 64, 100, 144, 196, 216, 256, 324, 400, 484, 576, 676, 729, 784, 900, 1024, 1156, 1296, 1444, 1600, 1728, 1764, 1936, 2116, 2304, 2500, 2704, 2916, 3125, 3136, 3364, 3375, 3600, 3844, 4096, 4356, 4624, 4900, 5184, 5476, 5776, 5832, 6084, 6400

Offset: 1

T. D. Noe, Aug 24 2004

The polynomial x^n - n is reducible over the integers for n in this sequence.
A result of Vahlen shows that the polynomial x^n - n is reducible over the integers for n in this sequence and no other n.
The representation (k*p)^p is generally not unique, e.g. a(120) = 46656 = (108*2)^2 = (12*3)^3. - Reinhard Zumkeller, Feb 14 2015
This is also numbers of the form (km)^m for any m > 1, not just primes. Let m be > 1; then m has a prime factor, so let m=pj, p a prime and j an integer > 0. Then (km)^m = (kpj)^pj = (k^j p^j j^j)^p = ((k^j p^(j-1) j^j) p) ^ p. - Franklin T. Adams-Watters, Sep 13 2015

T. D. Noe, Table of n, a(n) for n = 1..1000
A. Schinzel, Problems and results on polynomials.

Cf. A084746 (least k such that n^k-k is prime).
Cf. A097792 (numbers of the form 4k^4 or (kp)^p).
Cf. A000040, A051674, A255134 (first differences).

import Data.Set (singleton, deleteFindMin, insert)
a097764 n = a097764_list !! (n-1)
a097764_list = f 0 (singleton (4, 2, 2)) $
                 tail $ zip a051674_list a000040_list where
   f m s ppps'@((pp, p) : ppps)
     | pp < qq   = f m (insert (pp, p, 2) s) ppps
     | qq == m   = f m (insert ((k * q) ^ q, q, k + 1) s') ppps'
     | otherwise = qq : f qq (insert ((k * q) ^ q, q, k + 1) s') ppps'
     where ((qq, q, k), s') = deleteFindMin s
-- Reinhard Zumkeller, Feb 14 2015

nMax=10000; lst={}; n=1; While[p=Prime[n]; p^p<=nMax, k=1; While[(k*p)^p<=nMax, AppendTo[lst, (k*p)^p]; k++ ]; n++ ]; Union[lst]

is(n)=my(b,e=ispower(n,,&b),f); if(e==0, return(0)); f=factor(e)[,1]; for(i=1,#f, if(b%f[i]==0, return(1))); 0 \\ Charles R Greathouse IV, Aug 29 2016

A072883 Least k >= 1 such that k^n + n is prime, or 0 if no such k exists.

Original entry on oeis.org

1, 1, 2, 1, 2, 1, 16, 3, 2, 1, 32, 1, 118, 417, 2, 1, 14, 1, 22, 81, 76, 1, 12, 55, 28, 15, 0, 1, 110, 1, 232, 117, 230, 3, 12, 1, 4, 375, 2, 1, 48, 1, 46, 15, 218, 1, 78, 7, 100, 993, 28, 1, 624, 13, 252, 183, 226, 1, 104, 1, 1348, 777, 1294, 0, 1806, 1, 306, 1815, 10, 1, 30, 1

Offset: 1

Benoit Cloitre, Aug 13 2002

nonn

Because the polynomial x^n + n is reducible for n in A097792, a(27) and a(64) are 0. Although x^4 + 4 is reducible, the factor x^2 - 2x + 2 is 1 for x=1. - T. D. Noe, Aug 24 2004

Hugo Pfoertner, Table of n, a(n) for n = 1..756

Cf. A097792 (n such that x^n + n is reducible).

Cf. A239666, A303121, A303122.

Table[If[MemberQ[{27, 64}, n], 0, k=1; While[ !PrimeQ[k^n+n], k++ ]; k], {n, 100}]
(* Second program: *)
okQ[n_] := n == 4 || IrreduciblePolynomialQ[x^n + n];
a[n_] := If[!okQ[n], 0, s = 1; While[!PrimeQ[s^n + n], s++]; s];
Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Jan 15 2019, from PARI *)

isok(n) = (n==4) || polisirreducible(x^n+n);
a(n) = if (!isok(n), 0, my(s=1); while(!isprime(s^n+n), s++); s); \\ adapted by Michel Marcus, Jan 15 2019

apply( {A072883(n)=if(is_A097792(n), n==4, for(k=1, oo, ispseudoprime(k^n+n) && return(k)))}, [1..99]) \\ M. F. Hasler, Jul 07 2024

from sympy import isprime
def A072883(n):
    if is_A097792(n): return int(n==4)
    for k in range(1,99**9):
        if isprime(k**n+n): return k # M. F. Hasler, Jul 07 2024

More terms from T. D. Noe, Aug 24 2004

A239666 a(n) = least number k such that n*k^n+1 is prime, or 0 if no such number exists.

Original entry on oeis.org

1, 1, 4, 1, 8, 1, 4, 3, 10, 1, 42, 1, 60, 15, 22, 1, 8, 1, 198, 42, 10, 1, 8, 115, 34, 21, 0, 1, 54, 1, 130, 3, 4, 7, 72, 1, 778, 204, 30, 1, 108, 1, 178, 15, 14, 1, 924, 28, 234, 63, 1376, 1, 44, 3, 16, 27, 256, 1, 180, 1, 706, 51, 98, 0, 546, 1, 4, 153, 150, 1, 170

Offset: 1

Derek Orr, Mar 29 2014

nonn

a(n) = 1 iff n+1 is prime.
If a(n) = 0, then n is in A097792. Note that the converse is not true: a(4) = 1, not 0.
If n is in A097792 and n > 4, then a(n) = 0. For a sketch of this proof, either n = 4b^4 for some positive integer b > 2 or n = (bp)^p for some prime p > 2 and some positive integer b. In the first case, n*k^n+1 can be factored by Sophie Germain's identity into two trinomials where neither can equal 1 since b > 2, so n*k^n+1 must be composite. In the second case, (bpk^{b^p p^(p-1)}+1) is a factor of n*k^n+1 since p is odd. - William Dean, Oct 23 2024

			3*1^3+1 = 4 is not prime. 3*2^3+1 = 25 is not prime. 3*3^3+1 = 82 is not prime. 3*4^3+1 = 193 is prime. Thus, a(3) = 4.

William Dean, Table of n, a(n) for n = 1..1000

Cf. A097792, A116954, A089001.

is_A097792(n)={my(p,t); n%4==0 && ispower(n\4, 4) || ((2 < p = ispower(n, , &t)) && if(isprime(p), t%p==0, foreach(factor(p)[, 1], q, q%2 && n%q==0 && return(1))))}
a(n) = if(n!=4 && is_A097792(n), 0, for(k=1,oo,if(ispseudoprime(n*k^n+1),return(k)))); \\ [corrected by Andrew Howroyd, Oct 25 2024]

A303121 Least k>1 such that k^n + n is prime, 0 if no such k exists.

Original entry on oeis.org

2, 3, 2, 0, 2, 175, 16, 3, 2, 539, 32, 221, 118, 417, 2, 85, 14, 133, 22, 81, 76, 115, 12, 55, 28, 15, 0, 2465, 110, 31, 232, 117, 230, 3, 12, 851, 4, 375, 2, 1599, 48, 5461, 46, 15, 218, 6815, 78, 7, 100, 993, 28, 901, 624, 13, 252, 183, 226, 43247, 104, 5063, 1348, 777, 1294, 0, 1806

Offset: 1

Hugo Pfoertner, Apr 23 2018

nonn

The values of n for which k^n + n is reducible over the integers are given in A097792. - Joseph Myers, Allan C. Wechsler Apr 16 2018

			a(2) = 3 because 3^2 + 3 = A303122(2) = 11 is prime, whereas 2^2 + 2 = 6 is composite.

Hugo Pfoertner, Table of n, a(n) for n = 1..365

Cf. A072883, A093324, A097764, A097792, A303122.

If n + 1 is composite, then a(n) = A072883(n). - Altug Alkan, Apr 23 2018

A303122 Least prime of the form k^n + n with k>1, 0 if no such prime exists.

Original entry on oeis.org

3, 11, 11, 0, 37, 28722900390631, 268435463, 6569, 521, 2069605890837224702290236611, 36028797018963979, 13573982477229290545823357053, 859935929762876868984659981, 4807339234680508004200143948920808143, 32783, 7425108623606394726715087890641, 30491346729331195921

Offset: 1

Hugo Pfoertner, Apr 23 2018

nonn

No primes of the form k^n + n exist for n in A097792.

			a(3) = 11 because 2^3 + 3 = 11 is the least prime that can be expressed as k^3 + 3, k > 1.

Hugo Pfoertner, Table of n, a(n) for n = 1..100

Cf. A097792, A303121.

A130827 Least k >= 1 such that k^n + n is semiprime, or 0 if no such k exists.

Original entry on oeis.org

3, 2, 1, 3, 1, 7, 3, 1, 1, 11, 2, 7, 1, 1, 7, 3, 5, 23, 4, 1, 1, 3, 2, 1, 1, 21, 14, 11, 12, 7, 16, 1, 1, 1, 26, 37, 1, 1, 4, 21, 6, 31, 4, 25, 1, 71, 14, 1, 10, 1, 10, 371, 36, 1, 3, 1, 1, 185, 2, 43, 1, 49, 104, 1, 18, 205, 70, 1, 2, 33, 38, 541, 1, 105, 8, 1, 24, 395, 30, 3, 1, 71, 20, 1, 1, 1

Offset: 1

Zak Seidov, Aug 18 2007

nonn

There exist values of n for which k^n + n is never prime (cf. A072883). Do there exist values of n for which k^n + n is never semiprime?

Compare with A361803, the equivalent sequence for k^n - n, where a generalized factorization (effectively a polynomial factorization) into 3 factors is given to show that k^n - n is never semiprime for certain n. - Peter Munn, Jun 19 2023

			a(1)=3 because 1^1 + 1 = 2 (prime) and 2^1 + 1 = 3 (prime) but 3^1 + 1 = 4 = 2*2 (semiprime).
a(2)=2 because 1^2 + 2 = 3 (prime) but 2^2 + 2 = 6 = 2*3 (semiprime).
a(3)=1 because 1^3 + 3 = 4 = 2*2 (semiprime).
a(4)=3 because 1^4 + 4 = 5 (prime) and 2^4 + 4 = 20 = 2^2 * 5 but 3^4 + 4 = 85 = 5*17 (semiprime).
a(5)=1 because 1^5 + 5 = 6 = 2*3 (semiprime).

Sean A. Irvine, Table of n, a(n) for n = 1..100.

Cf. A097792 (n such that x^n+n is reducible), A072883 (least k >= 1 such that k^n+n is prime, or 0 if no such k exists).

Cf. A361803.

a(n) = my(k=1); while (bigomega(k^n+n)!=2, k++); k; \\ Michel Marcus, Jun 19 2023

More terms from Sean A. Irvine, Oct 20 2009

cp's OEIS Frontend

A097764 Numbers of the form (kp)^p for prime p and k=1,2,3,....

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

A072883 Least k >= 1 such that k^n + n is prime, or 0 if no such k exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Extensions

A239666 a(n) = least number k such that n*k^n+1 is prime, or 0 if no such number exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A303121 Least k>1 such that k^n + n is prime, 0 if no such k exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A303122 Least prime of the form k^n + n with k>1, 0 if no such prime exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A130827 Least k >= 1 such that k^n + n is semiprime, or 0 if no such k exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions