A274459 Least number of perfect powers that add up to n.

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

Author

Sergio Pimentel, Jun 23 2016

Keywords

• nonn

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]

Examples

			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.
		

Links

• David A. Corneth, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A001597, A002376, A002377, A002828, A002804, A079611, A063274, A188462, A225926.

Cf. A063275 (indices for which a(n)=3), A113505 (indices for which a(n)=4).

Programs

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

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

Extensions

More terms from Michael De Vlieger, Jun 23 2016

Terms from a(74) from David A. Corneth, Jun 24 2016