OFFSET
0,3
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
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
EXAMPLE
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.
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 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Jonathan Vos Post, Sep 20 2006
EXTENSIONS
a(4)-a(22) from Giovanni Resta, Jun 12 2016
STATUS
approved