login
A274459
Least number of perfect powers that add up to n.
3
1, 2, 3, 1, 2, 3, 4, 1, 1, 2, 3, 2, 2, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 1, 2, 1, 2, 2, 3, 2, 1, 2, 2, 2, 1, 2, 3, 3, 2, 2, 3, 2, 2, 2, 3, 3, 2, 1, 2, 3, 2, 2, 2, 3, 3, 2, 2, 2, 3, 2, 3, 2, 1, 2, 3, 3, 2, 3, 3, 3, 2, 2, 2, 3, 2, 3, 3, 3, 2, 1, 2, 3, 3, 2
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
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
Cf. A063275 (indices for which a(n)=3), A113505 (indices for which a(n)=4).
Sequence in context: A096137 A282905 A063274 * A225926 A354761 A351064
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