A396469 Primes not representable as sums of the form q_1^{k_1} + ... + q_r^{k_r}, where q_1,...,q_r are distinct earlier terms of this sequence and k_i >= 1.

2, 3, 23, 37, 47, 61, 223, 233, 743, 1237, 11813, 39209, 518057, 3131537, 7810427, 40481087, 99241183, 637496077, 1520343073, 10683103157, 22935190549

Offset

1,1

Comments

Open problems:

(1) What is the asymptotic growth of this sequence?

(2) Is there any efficient way to calculate the sequence?

The sequence is infinite. See Hartley (2026).

Links

Table of n, a(n) for n=1..21.

Nakul Badjatya, SageMath program

Michael Hartley, Proof that the sequence is infinite, Mathematics Stack Exchange, 2026.

Example

Start with first prime 2. Now as the sequence is empty, 2 is admitted to the sequence.
Now to check whether 3 belongs to the sequence, we have to check if one can have 2^k = 3 with k >= 1. Since this is not possible, 3 is admitted.
The next prime is 5. But 2^1 + 3^1 = 5, so 5 is not admitted to the sequence.

Prog

(SageMath) # See Badjatya link

Crossrefs

Cf. A000040, A000945, A000946, A063884, A099243.

Sequence in context: A213971 A024773 A176892 * A109615 A101001 A231477

Adjacent sequences: A396466 A396467 A396468 * A396470 A396471 A396472

Keyword

nonn,hard,more,changed

Author

Nakul Badjatya, May 27 2026

Extensions

a(16)-a(20) from Michael S. Branicky, Jun 15 2026

a(21) from Michael S. Branicky, Jun 22 2026

Status

approved