A275747 -id:A275747 - cp's OEIS frontend

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

Jonathan Vos Post, Sep 20 2006

nonn

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

			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.

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

Cf. A078135, A275743, A275746, A275747.

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 *)

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

A275746 The number of integers not representable as a sum of n-th powers of odd primes.

Original entry on oeis.org

3, 62, 840, 12350, 99912, 2358913, 12173587, 120900206, 1224812108, 20439317893, 130357794430, 1534358290778, 13544972574336, 142155007727976, 1648210755327790, 14816750258004918, 151900144117560355, 1525977077403654254, 16185530587326104490

Offset: 1

Mike Oakes, Aug 07 2016

nonn

I executed the algorithm in Boecker et al. (2007) with a PARI/GP program, which needed 36 GB RAM and 2 hours to run for n=19. Results checked by an independent algorithm. - Mike Oakes, Aug 17 2016

			For n=2, there are 62 integers that cannot be written as a sum of squares of odd primes.

S. Boecker and Z. Liptak, A Fast and Simple Algorithm for the Money Changing Problem, Algorithmica, 48 (2007), 413-432.

Cf. A275747. For all primes, including 2, see A275743, A122615.

More terms from Mike Oakes, Aug 17 2016

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions