A122615 Largest integer which cannot be written as a sum of n-th powers of primes.

0, 1, 23, 154, 1199, 5314, 34928, 256117, 1565279, 6519069, 49304891, 362617861, 1121432591, 13059091501, 34313897584, 202096681135, 1912393561610, 6341902873937, 54356644026512, 175476300288281, 1352729779867857, 5937475586243116, 39152549345560551

Offset: 0

Author

Jonathan Vos Post, Sep 20 2006

Keywords

• nonn

Comments

The powers of only 3 primes are needed, namely 2^n, 3^n and 5^n, which leads to an ultra-fast O(n) execution time. I executed the algorithm in Greenberg (1988) with a PARI/GP program in only a few seconds for 1001 terms. - Mike Oakes, Aug 16 2016

Equivalent definition for this same sequence is "Largest integer which cannot be written as a sum of n-th powers of integers greater than 1". - Mike Oakes, Aug 17 2016

Examples

			a(0) = 0 because all positive integers can be written as a sum of 0th powers of primes, i.e. as sums of 1.
a(1) = 1 because 2^1 = 2, 3^1 = 3, hence all positive integers 2 or larger can be written as a*2 + b*3 for a,b nonnegative integers [2 = 2, 3 = 3, 4 = 2+2, 5 = 2+3, 6 = 2+2+2 = 3+3, 7 = 2+2+3, ...].
a(2) = 23 because all integers 24 or larger can be written as a sum of squares and in fact as a sum of squares of primes.
a(3) = 154 because all integers 155 or larger can be written as a sum of cubes of primes.
		

Links

• Mike Oakes, Table of n, a(n) for n = 0..1000
• H. Greenberg, Solution to a linear diophantine equation for nonnegative integers, Journal of Algorithms, 9 (1988), 343-353

Crossrefs

Cf. A078135, A275743, A275746, A275747.

Programs

Mathematica

a[0] = 0; a[n_] := Block[{k = 4, f}, While[Prime[k]^n <= (f = FrobeniusNumber[ Prime[ Range@ k]^n]), k++]; f]; a /@ Range[0, 10] (* Giovanni Resta, Jun 13 2016 *)

Extensions

a(4)-a(22) from Giovanni Resta, Jun 12 2016