OFFSET
1,2
COMMENTS
Least number of perfect powers (A001597) needed to add up to n.
This sequence is close to but not exactly equal to A063274.
a(n) is at most 4 since any number can be written as a sum of 4 squares (Lagrange's theorem), but it is possible that for a sufficiently large n, a(n) < 4.
a(n) <= a(i) + a(n-i) for 1 <= i <= n-1. (for computational ease, the maximum value for i can be chosen as floor(n/2)). a(1991) = 4. for 1992 <= k <= 20000, there is no k such that a(k) = 4. - David A. Corneth, Jun 24 2016 [Next such k is 25887, see A113505. - Vaclav Kotesovec, Jun 25 2016]
LINKS
David A. Corneth, Table of n, a(n) for n = 1..10000
EXAMPLE
a(31) = 2 since 31 can be written as the sum of two (31 = 3^3 + 2^2 = 27 + 4) but no fewer than two perfect powers.
MATHEMATICA
nn = 72; t = Select[Range@ nn, # == 1 || GCD @@ FactorInteger[#][[All, 2]] > 1 &]; Table[Min@ Map[Length, Select[IntegerPartitions@ n, AllTrue[#, MemberQ[t, #] &] &]], {n, nn}] (* Michael De Vlieger, Jun 23 2016, after Ant King at A001597 *)
PROG
(PARI) lista(n) = {my(v = vector(n)); for(i = 2, sqrtint(n), for(j = 2, logint(n, i), v[i^j] = 1)); v[1]=1; v[2]=2; for(i=3, #v, if(v[i]==0, v[i] = vecmin(vector( i\2, k, v[k] + v[i-k])))); v} \\ David A. Corneth, Jun 24 2016; corrected by Peter Schorn, Jun 09 2022
CROSSREFS
KEYWORD
nonn
AUTHOR
Sergio Pimentel, Jun 23 2016
EXTENSIONS
More terms from Michael De Vlieger, Jun 23 2016
Terms from a(74) from David A. Corneth, Jun 24 2016
STATUS
approved