A275746 -id:A275746 - 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

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

Original entry on oeis.org

1, 12, 83, 600, 3058, 18222, 130411, 783480, 3418488, 24857930, 181308931, 610675758, 6529545751, 18840405540, 102444103996, 956394012747, 3188347929974, 27288773879397, 96923972375603, 702926766993950, 2980668206142664, 20046633698159181, 88137290213079355, 502113072640777785

Offset: 1

Mike Oakes, Aug 07 2016

nonn

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

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

Mike Oakes, Table of n, a(n) for n = 1..30
S. Boecker and Z. Liptak, A Fast and Simple Algorithm for the Money Changing Problem, Algorithmica, 48 (2007), 413-432.

Cf. A122615, A275746.

More terms from Mike Oakes, Aug 17 2016

a(16) corrected by Andrew Howroyd, Feb 23 2018

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

Original entry on oeis.org

4, 114, 1595, 24195, 190463, 4613167, 23815950, 240951477, 2448240688, 40379465440, 258630935725, 3044619003271, 26232953378021, 264066033166293, 3218396161633945, 29248021240625765, 302064442857973298, 3027736057187540859, 32207709908667683204

Offset: 1

Mike Oakes, Aug 07 2016

nonn

Except for n=6, only the powers of 3 primes are needed, namely 3^n, 5^n and 7^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 1000 terms. - Mike Oakes, Aug 16 2016

			For n=2, 114 is the largest integer which cannot be written as a sum of squares of odd primes.

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

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

With[{prs=Prime[Range[2,5]]},Table[FrobeniusNumber[prs^n],{n,20}]] (* Harvey P. Dale, Sep 19 2018 *)

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica