|
%I #45 Aug 03 2022 23:28:56
%S 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,
%T 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,
%U 3,3,3,2,2,2,3,2,3,3,3,2,1,2,3,3,2
%N Least number of perfect powers that add up to n.
%C Least number of perfect powers (A001597) needed to add up to n.
%C This sequence is close to but not exactly equal to A063274.
%C 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.
%C 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]
%H David A. Corneth, <a href="/A274459/b274459.txt">Table of n, a(n) for n = 1..10000</a>
%e 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.
%t 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 *)
%o (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
%Y Cf. A001597, A002376, A002377, A002828, A002804, A079611, A063274, A188462, A225926.
%Y Cf. A063275 (indices for which a(n)=3), A113505 (indices for which a(n)=4).
%K nonn
%O 1,2
%A _Sergio Pimentel_, Jun 23 2016
%E More terms from _Michael De Vlieger_, Jun 23 2016
%E Terms from a(74) from _David A. Corneth_, Jun 24 2016
|
