Sum powers to n

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 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, 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 1

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>

Answer 2

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!

Answer 3

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

Answer 4

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

Answer 5

Vyxal, 18 bytes

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

Try it Online!

Vyxal has become bugless at last.

Answer 6

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!

Answer 7

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.

Answer 8

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.

Answer 9

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.

Answer 10

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!

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.