# Sum powers to n

Each natural number (including 0) can be written as a sum of distinct powers of integers (with a minimum exponent of 2). Your task is to output the smallest power required to represent $$\n\$$.

For example:

2 = 1^2 + 1^3 // Output 3
9 = 1^2 + 2^3 = 3^2 // Output 2
15 = 2^2 + 2^3 + 1^4 + 1^5 + 1^6 // Output 6
20 = 2^2 + 0^3 + 2^4 // Output 4


Ungolfed slow reference implementation (js):

function f(x){
for (let maxPower = 2; true; maxPower++){
let bases = Array(maxPower - 1).fill(0);
let sum = 0;
while (sum != x && bases[0] ** 2 <= x){
sum = bases.reduce((a, c, i) => a + c ** (i + 2), 0);
let nextIncr = bases.length - 1;
do {
if (nextIncr < bases.length - 1) bases[nextIncr + 1] = 0;
bases[nextIncr]++;
} while (nextIncr && bases[nextIncr] ** (nextIncr--) > x)
}
if (sum == x) return maxPower;
}
}


This is a challenge. The sequence is naturally 0-indexed, so you may not 1-index it. You may...

• Take a positive integer $$\n\$$ and output the first $$\n\$$ values.
• Take a positive integer $$\n\$$ and output the value for $$\n\$$.
• Take no input and output values indefinitely.

The sequence starts: 2,2,3,4,2,3,4,5,3,2,3,4,3,4,5,6,2,3,4,5

This is , so the shortest code in bytes wins.

--

Honestly, I'm surprised this isn't on the OEIS. I'm also uncertain whether there's any number above 6 in the sequence - not that I've searched that far.

• Wait, so do the exponents have to increase by 1 each time? Or do they just have to be distinct? Dec 6 '21 at 17:40
• @RedwolfPrograms They just have to be distinct. That being said, the two cases are equivalent because you can have 0^x for all of the missing ones. Dec 6 '21 at 17:41
• Numbers which are not of the form $a^2+b^3+c^4+d^5$ are listed in A111151. (These are the 6's in your sequence.) Dec 6 '21 at 18:09
• If this really isn't in OEIS, you should submit it! It'd be good for them to have, and good to have linked to this question once it is up :) Dec 6 '21 at 18:34
• Can we use negative integers? e.g. 0 = 8² + (-4)³
– Stef
Dec 7 '21 at 10:17

# JavaScript (Node.js), 63 bytes

f=(n,m=2,i=0,p=n-i**m)=>p<0?f(n,m+1):!p||i&&f(p)<m?m:f(n,m,i+1)


Try it online!

Time out for not so large n as its terrible recursion design. It could be fast if we apply memorize to it (70 bytes).

f=(n,m=2,i=0,p=n-i**m)=>f[n]??=p<0?f(n,m+1):!p||i&&f(p)<m?m:f(n,m,i+1)

o.value = [...Array(50000)].map((_, i) => i).filter(v => f(v) > 5).join(', ')
<a href="https://oeis.org/A111151">A111151</a>: <output id=o></output>

# Python 3.8, 109 bytes

This could probably be a bit shorter, but I tried to make it fast. Prints the sequence indefinitely.

a=[i:=1]
k=2
while[print(k),k:=2]:
while all(k<=a[i-b**k]for b in range(1,1+int(i**(1/k)))):k+=1
a+=k,;i+=1


Try it online!

• A trivial -2 bytes in Python 3.8: Try it online! (although that means we can't use PyPy on TIO) Dec 6 '21 at 18:48
• @pxeger thanks, I was able to save a few more bytes based on this, and it still floods the output fast enough
– ovs
Dec 6 '21 at 18:58
• what exactly does a=[i:=1] do? Dec 7 '21 at 17:15
• @Eumel i:=1 is an assignment expression, which assign i the value 1 and returns 1. The entire thing is equivalent to i=1;a=[i]
– ovs
Dec 7 '21 at 17:44

# JavaScript (ES7), 79 bytes

Returns the n-th term (0-indexed).

f=(n,q=2)=>(g=(k,t=n,i=0)=>t?i>t|k<2||g(k-1,t-i**k)*g(k,t,i+1):0)(q)?f(n,q+1):q


Try it online!

### Commented

f = (            // f is the outer recursive function taking:
n,             //   n = input
q = 2          //   q = upper bound for the exponent
) =>             //
(                //
g = (          // g is the inner recursive function taking:
k,           //   k = exponent
t = n,       //   t = remainder
i = 0        //   i = base
) =>           //
t ?            //   if t is not equal to 0:
i > t |      //     abort if i is greater than t
//     (this is slower but shorter than i ** k > t)
k < 2 ||     //     or k = 1
g(           //     otherwise, do a recursive call:
k - 1,     //       decrement k
t - i ** k //       subtract i ** k from t
) *          //     end of recursive call
g(           //     do another recursive call:
k,         //       leave k unchanged
t,         //       leave t unchanged
i + 1      //       increment i
)            //     end of recursive call
:              //   else:
0            //     success: return 0
)(q)             // initial call with k = q
?                // if it failed:
f(n, q + 1)    //   try again with q + 1
:                // else:
q              //   success: return q


# 05AB1E, 17 bytes

Very inefficient brute force approach. Prints $$\a(n)\$$ given $$\n\$$.

∞>.ΔIÝy<ãεā>mO}Iå


Try it online!

A more efficient recursive version that is similar to my Python answer is 23 bytes long:

λNU∞>.ΔXyzmLymXα₅ß›]Y0ǝ


Try it online!

Commented:

∞>.ΔIÝy<ãεā>mO}Iå   -- Takes input n and prints a(n)
∞>                  -- infinite list [2, 3, 4, ...]
.Δ                -- find the first value y in this list with:
IÝ              --   range from 0 to the input n
y<ã           --   cartesian power [0 .. n] ^ (y-1)
ε    }     --   map over each (y-1)-tuple:
ā>        --     range [2 .. length+1] = [2 .. y]
m       --     exponentiation
O      --     sum the values
Iå   --   is the input in this list?

λNU∞>.ΔXyzmLymXα₅ß›]Y0ǝ -- takes no input and prints the infinite sequence
λ                   -- start recursive environment with a(0)=1
-- for each N in [1, 2, ...], calculate a(N) by:
NU                 --   store N in variable X
∞>.Δ             --   find y in [2, 3, 4, ...] with:
yz          --     1/y
X  m         --     X ^ (1/y)
L        --     [1..floor(X^(1/y))]
ym      --     [1..floor(X^(1/y))]^y
Xα    --     abs([1..floor(X^(1/y))]^y - X)
₅   --     a(abs([1..floor(X^(1/y))]^y - X))
ß› --     y > min(a(abs([1..floor(X^(1/y))]^y - X)))
Y0ǝ                 -- Set the value at index 0 to 2


# Vyxal, 18 bytes

λ›⁰ʀnÞẊƛż›e∑;?c;ṅ›


Try it Online!

Vyxal has become bugless at last.

# Ruby, 84 74 bytes

->n,*r{(2..n**n).find{|x|a=0;r=1;x/=n while x>0&&a+=(x%n)**r+=1;a==n}?r:2}


Try it online!

# 05AB1E, 30 bytes

Åœ¬_æÙδì€é.Δā>zδmœ€Å\1%_Pà}g>


Outputs the value for a positive input $$\n\$$.

Try it online or verify the values in the range $$\[1,25]\$$ (with æÙ replaced with η¯š to speed it up).

Explanation:

Åœ                # Get all possible sum-lists that equal the (implicit) input
# Because these sums lack 0s, we add those as well:
¬               #  Head (without popping), which are an input amount of 1s
_              #  Convert each to a 0
æ             #  Get the powerset of this
Ù            #  Uniquify this list
η¯š           #  Sped-up alternative:
η             #   Get the prefixes of this list
¯š           #   And prepend an additional empty list
δ          #  Apply double-vectorized:
ì         #   Prepend-merge the lists
€       #  Flatten the list of lists one level down
# (we've now added [0,input] amount of 0s to each sum of Åœ)
é                 # Sort this list of lists by length
.Δ               # Find the first/shortest which is truthy for:
ā              #  Push a list in the range [1,length] (without popping)
>             #  Increase each by 1 to make the range [2,length+1]
z            #  Calculate 1/n for each: [1/2,1/3,...,1/(length+1)]
δ           #  Apply double-vectorized:
m          #   Exponentiation
#  Check if at least one of these lists uses each exponent in
#  the range [2,length+1]:
œ         #   Get all permutations of this list of lists
€        #   Map each permutation-matrix to:
Å\      #    Pop and leave its main diagonal
1%    #   Modulo-1 on each
_   #   And check if its decimals are 0 (thus it's an integer)
P  #   Product to check if this is truthy for all
à #   Max to check if this is truthy for any main diagonal
}g>             # When we've found our result: pop and push its length + 1
# (after which it is output implicitly as result)


See this for a step-by-step output with added debug-lines.

# Charcoal, 40 39 bytes

ＦＮ⊞υ⊗¬ιＦ…²χＦ⮌⌕Ａυ⁰Ｆ⊙υΣ✂…υ⊕⁻κＸμι±¹§≔υκιＩυ


Try it online! Link is to verbose version of code. Outputs the first n values. Explanation:

ＦＮ⊞υ⊗¬ι


Start with 0 having been found to have a value of 2 but none of the other values having been found yet.

Ｆ…²χ


Try from squares up to ninth powers.

Ｆ⮌⌕Ａυ⁰


Loop over all of the values that haven't yet been found in reverse order, so the highest index is tested first.

Ｆ⊙υΣ✂…υ⊕⁻κＸμι±¹


Subtract the powers of all the integers up to n from the current index and see if any of those values had previously been found. This is harder than it sounds as it's necessary to defeat Charcoal's cyclic indexing.

§≔υκι


If so then mark this value with the necessary power.

Ｉυ


Output all of the values.

# R, 91 88 bytes

f=function(n,m=2,o=n+3,a=n-(0:n)^m)if(m<o&&all(a),min(sapply(a[a>0],f,m+1,o)),m/(m<o))


Try it online!

Outputs the value for n. Very slow for even moderate n.

f=function(n,        # recursive function with argument n
m=2,                # m=power to use in this iteration
o=n+3,              # o=maximum power: stop when m reaches this
a=n-(0:n)^m         # a=array of values by subtracting 0..n raised to m-th power from n
)
if(m<o,...,Inf)   # if m is too big, stop
if(all(a),...,m) # if there are any zero values in a, then we've got n: stop and return m
# otherwise:
min(              # return the lowest value of
sapply(a[a>0],f,m+1,o)
# recursive calls to f with all positive values of a, using power m+1
)


# R, 79* bytes

(* assuming that there are no values above 6 in the sequence, as conjectured in the comment to A111151)

f=function(n,m=2,a=n-(0:n)^m)if(m<7&all(a),min(sapply(a[a>0],f,m+1)),m/(m<7))


Try it online!

Also outputs the value for n, but somewhat more efficiently than the 91-byte code, as the recursion can stop much sooner.

f n=head(filter((!)n)[2..])