cp's OEIS Frontend

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

%I A122615 #41 Mar 03 2024 09:28:45
%S A122615 0,1,23,154,1199,5314,34928,256117,1565279,6519069,49304891,362617861,
%T A122615 1121432591,13059091501,34313897584,202096681135,1912393561610,
%U A122615 6341902873937,54356644026512,175476300288281,1352729779867857,5937475586243116,39152549345560551
%N A122615 Largest integer which cannot be written as a sum of n-th powers of primes.
%C A122615 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
%C A122615 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
%H A122615 Mike Oakes, <a href="/A122615/b122615.txt">Table of n, a(n) for n = 0..1000</a>
%H A122615 H. Greenberg, <a href="http://dx.doi.org/10.1016/0196-6774(88)90025-9">Solution to a linear diophantine equation for nonnegative integers</a>, Journal of Algorithms, 9 (1988), 343-353
%e A122615 a(0) = 0 because all positive integers can be written as a sum of 0th powers of primes, i.e. as sums of 1.
%e A122615 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, ...].
%e A122615 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.
%e A122615 a(3) = 154 because all integers 155 or larger can be written as a sum of cubes of primes.
%t A122615 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 *)
%Y A122615 Cf. A078135, A275743, A275746, A275747.
%K A122615 nonn
%O A122615 0,3
%A A122615 _Jonathan Vos Post_, Sep 20 2006
%E A122615 a(4)-a(22) from _Giovanni Resta_, Jun 12 2016