28
\$\begingroup\$

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.

\$\endgroup\$
11
  • \$\begingroup\$ Wait, so do the exponents have to increase by 1 each time? Or do they just have to be distinct? \$\endgroup\$ Dec 6, 2021 at 17:40
  • \$\begingroup\$ @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. \$\endgroup\$ Dec 6, 2021 at 17:41
  • 8
    \$\begingroup\$ 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.) \$\endgroup\$
    – Arnauld
    Dec 6, 2021 at 18:09
  • 8
    \$\begingroup\$ 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 :) \$\endgroup\$ Dec 6, 2021 at 18:34
  • 2
    \$\begingroup\$ Can we use negative integers? e.g. 0 = 8² + (-4)³ \$\endgroup\$
    – Stef
    Dec 7, 2021 at 10:17

10 Answers 10

8
\$\begingroup\$

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>

\$\endgroup\$
7
\$\begingroup\$

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!

\$\endgroup\$
4
  • \$\begingroup\$ A trivial -2 bytes in Python 3.8: Try it online! (although that means we can't use PyPy on TIO) \$\endgroup\$
    – pxeger
    Dec 6, 2021 at 18:48
  • \$\begingroup\$ @pxeger thanks, I was able to save a few more bytes based on this, and it still floods the output fast enough \$\endgroup\$
    – ovs
    Dec 6, 2021 at 18:58
  • \$\begingroup\$ what exactly does a=[i:=1] do? \$\endgroup\$
    – Eumel
    Dec 7, 2021 at 17:15
  • \$\begingroup\$ @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] \$\endgroup\$
    – ovs
    Dec 7, 2021 at 17:44
5
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

Vyxal, 18 bytes

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

Try it Online!

Vyxal has become bugless at last.

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

Charcoal, 40 39 bytes

FN⊞υ⊗¬ιF…²χF⮌⌕Aυ⁰F⊙υΣ✂…υ⊕⁻κXμι±¹§≔υκιIυ

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

FN⊞υ⊗¬ι

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

F…²χ

Try from squares up to ninth powers.

F⮌⌕Aυ⁰

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

F⊙υΣ✂…υ⊕⁻κXμι±¹

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.

Iυ

Output all of the values.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.