[Question]
  [
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 [sequence](/questions/tagged/sequence "show questions tagged 'sequence'") 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 [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), 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.
  
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), 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!](https://tio.run/##HclLCoMwEADQq6QbmbExpC7FUXqOUkqwpkwxyRClUPDu6edt39O93Dpllq2J6T6X4gmiDtRqJquFYsN1HZAG6e3of3U8YXeQfeeq8iDYhzF0/9D8rTKluKZlNkt6wMUYc87ZvaG1eDXBCcBNK0ZFg/LAiFg@ "JavaScript (Node.js) – 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>
```
[Answer]
# [Python 3.8](https://docs.python.org/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!](https://tio.run/##HYtBCsMgEADvvmKPRg1l00ux2ZeIBwNps6wYkUDp603aOQ0DU7/Htpf7o7beEwX2hFEJTeqzcV5DbVwOLYMTT1P0Cv4ZUs5aZkqBx8UYia@9wQJcoKXyXjU6tL@PjdF4k@HCiyVUkCyJe/LlvZ8 "Python 3.8 (pre-release) – Try It Online")
[Answer]
# 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!](https://tio.run/##FYxBDoMgEEWvwsLFjGIDLltHr6KxSihmqEq6Ec9OZfdf8t7/jL/xmHb7DTX795zSQsByowapA0PgZCCWltTNobddiK5tYjTgai1DbcvSYWmyJm2l8akQNuyX/JFxS4vfgQUJ9RIsWhJa5VVVKCbPh1/nx@oNDCMUJ194i8V513gNmP4 "JavaScript (Node.js) – 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
```
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 17 bytes
Very inefficient brute force approach. Prints \$a(n)\$ given \$n\$.
```
∞>.ΔIÝy<ãεā>mO}Iå
```
[Try it online!](https://tio.run/##ASUA2v9vc2FiaWX//@KInj4uzpRJw515PMOjzrXEgT5tT31Jw6X//zE1 "05AB1E – 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!](https://tio.run/##ASwA0/9vc2FiaWX//867TlXiiJ4@Ls6UWHl6bUx5bVjOseKChcOf4oC6XVkwx53//w "05AB1E – 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
```
[Answer]
# [Vyxal](https://github.com/Vyxal/Vyxal), 18 bytes
```
λ›⁰ʀnÞẊƛż›e∑;?c;ṅ›
```
[Try it Online!](https://vyxal.pythonanywhere.com/#WyIiLCIiLCLOu+KAuuKBsMqAbsOe4bqKxpvFvOKAumXiiJE7P2M74bmF4oC6IiwiIiwiMjAiXQ==)
Vyxal has become bugless at last.
[Answer]
# [Ruby](https://www.ruby-lang.org/), ~~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!](https://tio.run/##KypNqvyfZvtf1y5PR6uoWsNITy9PSytPUy8tMy@luqaiJtHWwLrI1tC6Qt82T6E8IzMnVaHCzkBNLVHbVqNCNU9TS6tIGyidaGubV2tfZGVU@79AIS3aMJYLRBlBKEsIZWgKFTWI/Q8A "Ruby – Try It Online")
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), 30 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
Åœ¬_æÙδì€`é.Δā>zδmœ€Å\1%_Pà}g>
```
Outputs the value for a *positive* input \$n\$.
[Try it online](https://tio.run/##AT4Awf9vc2FiaWX//8OFxZPCrF/Ot8KvxaHOtMOs4oKsYMOpLs6UxIE@es60bcWT4oKsw4VcMSVfUMOgfWc@//8yMA) or [verify the values in the range \$[1,25]\$](https://tio.run/##AUsAtP9vc2FiaWX/MjVFTj8iIOKGkiAiP07/w4XFk8KsX863wq/Foc60w6zigqxgw6kuzpTEgT56zrRtxZPigqzDhVwxJV9Qw6B9Zz7/LP8) (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.](https://tio.run/##VVJNa9tAEL3nVwyCnmq1UY6FxoSSQA8FQ45pSMfWWFqy2hX74cSGHlrIL2h/QHssGHoJ6d1Orv4R/SPqzMppnIukZd578/Y9WY9jRV2XvTdtDG8gG75d3Q33siOtobVeBTUjUCZQRc5DqDGAjw0Ey9/K82TLWt88fNsyyxLO9gdpcg7Y2GgC2Cnse2ERTmpREM5qebH5s/r98HNzu17@/br81AucWhdgPAdNpgp1Ev/VT06UKXkvwVQ5H@CqVizGLoKLoZ7D1Lokezd8tfm@lwGcxibXipG8eFLT5DLdTyaj6GtASENlkqZDUxGcHQz6vS@Lc0HffzlMhHfWzIh9Jf8sV7yeoY4kkEUCHF@31pAJGJQ1UNo41pTPaBKsUwsqBbi5bfrl5JrYA70kk5JMVvggby9ozlPAH5D9lQora1ALIDlonyQEy@Gtbz72RuWe22jQPXUnsOLFxQ5GbTc/CxCQi@eNaPhpyCU/wh09Z6KZwxU@MlNJP1JJn7MTbrwERz7qnR9qZFsmldBK8ip4eIx5sNOj1PCfVx0Ouq4oujw3Nte4mP8D)
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), ~~40~~ 39 bytes
```
ＦＮ⊞υ⊗¬ιＦ…²χＦ⮌⌕Ａυ⁰Ｆ⊙υΣ✂…υ⊕⁻κＸμι±¹§≔υκιＩυ
```
[Try it online!](https://tio.run/##LY7NCsIwEITvPkWOG4iggidPpSL0YCn2CWK6tsF0I/lR@/QxUY/7zczOqEk6ZaVJ6WYdg4YeMbRxvqIDzlkX/QRRsKONV4MDtDaA5pwfVl/3RdKIsBNsu8nmH8InOo9w0jRUxpRw1v5iRUsBfZyhN1oh1IsyWE/2UXBDyuGMFHLRWVP0cBess688ZRas1HLBWhxlQNiWi7PKez1SFRoa8F1@3IvxsOqcpgC19AFiXpvSbp/WT/MB "Charcoal – 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.
[Answer]
# [R](https://www.r-project.org/), ~~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!](https://tio.run/##VY3RCsIwDAD/ZiQsYqdvw/gjoi7ICoUmKetE/Po6wRef745bWlXJea7rvfhrXrhFjk97rMkNjJQP5Gz9kYRtB2E0vClOKU6gJ@@6LQVB0mRQpZT8BrnIOVwpkvYDOW5s/1UR208I4xDof4rtAw "R – 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](https://www.r-project.org/), 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!](https://tio.run/##VY3RCoMwDAD/ZiSYsSqMgaz@iGwahoVCE0uriF/fOdiLz3fHpZKFQ5jyMsR5m5ItzrpVP4ufFZTENsRWr2Baxbfg6N0I8nxcjgYYSbxC5hjDDtxzZ17kSKoaD3L7eYjlj017N3R@YfkC "R – 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.
[Answer]
# Haskell, 73 bytes
```
f n=head(filter((!)n)[2..])
n!m=n==0||(m>1&&any(\k->(n-k^m)!(m-1))[0..n])
```
[Try it Online!](https://tio.run/##FcqxCsMgEADQvV9xLuFuUEx28xMdEwtCFYPeNSSWUsi/W/rml8NZYq29JxCXY3hi2mqLB6IioWUyxtNNFDtxzl4X8jwOQ5AvrkXPKLo8mBSyHokWa4x46hw2AQf7u93bAXjm1weQww4J/mWynqj/AA)
f(n) returns the nth value in the sequence (0-indexed). n!m calculates whether n can be expressed as the sum of m (or fewer) powers.
]