33
\$\begingroup\$

Given an integer, output five perfect cubes whose sum is that integer. Note that cubes can be positive, negative, or zero. For example,

-10 == -64 - 64 + 64 + 27 + 27

so for input -10 you could output [-64, -64, 64, 27, 27], though other solutions are possible. Note that you should output the cubes, not the numbers being cubed.

A solution always exists -- you might enjoy puzzling this out for yourself. It's further conjectured that four cubes suffice.

\$\endgroup\$
  • \$\begingroup\$ Two questions: Can we output any result, or only the smallest? For -10 another possible solution could be -1000+4574296+4410944-4492125-4492125 for example. And is it allowed to output -- or +- instead of +/- respectively (i.e. 3 = 27+-27+-125--64--64 instead of 3 = 27-27-135+64+64)? \$\endgroup\$ – Kevin Cruijssen Apr 4 '18 at 7:17
  • \$\begingroup\$ @KevinCruijssen Any result is fine. If you mean output like --5, I'd say no, as per usual rules on outputting an expression. \$\endgroup\$ – xnor Apr 4 '18 at 7:18
  • \$\begingroup\$ @KevinCruijssen You don't have to output an expression with + signs, just the numbers. \$\endgroup\$ – xnor Apr 4 '18 at 7:20
  • \$\begingroup\$ -10 = -64 - 64 + 64 + 27 + 27 or -10 = -343 + 0 -8 +125 +216 \$\endgroup\$ – Angs Apr 4 '18 at 7:31
  • 3
    \$\begingroup\$ Interesting note: 3 is not sufficient (some numbers are unrepresentable), but there are some numbers whose representability is unknown (such as 33). \$\endgroup\$ – Esolanging Fruit Apr 5 '18 at 2:11

24 Answers 24

16
\$\begingroup\$

Brachylog, 18 bytes

∧5~lLȧᵐ≥₁∧L^₃ᵐ.+?∧

Try it online!

Explanation

We basically describe the problem, with the additional constraint that we want the output list to be non-increasing in terms of magnitudes: this forces Brachylog to properly backtrack over all possible combinations of 5 values, instead of infinitely backtracking over the value of the last element of the list.

∧                ∧    (disable some implicit stuff)
 5~lL                 L is a list of length 5
    Lȧᵐ≥₁             L must be a non-increasing list in terms of magnitude
         ∧
          L^₃ᵐ.       The output is L with each element cubed
              .+?     The sum of the output is the input

Finding different solutions

By appending a , it's possible to use this predicate to find all solutions with increasing magnitudes: for example, here are the first 10 solutions for 42

\$\endgroup\$
14
\$\begingroup\$

Brachylog, 11 bytes

Thanks Fatalize for saving one byte

~+l₅≥₁.√₃ᵐ∧

Try it online!

Firstly ~+ enforces that the output (.) must sum to the input. l₅ again constrains the output, dictating that it must have a length of 5. ≥₁ declares that the list must be in decreasing order (I believe that this is necessary to stop the program entering an infinite loop)

We explicitly unify this list with ., the output variable, because our next predicate will "change" the values inside the list. We then take the cube root of each value in the list with √₃ᵐ. Since Brachylog is inherently integer-based, this dictates that all the numbers in the list are cube numbers.

Finally, we use because there is an implicit . added to the end of each line. Since we don't want . to be unified with the list of cube roots, we unified it earlier on and use to stop it unifying at the end.

\$\endgroup\$
10
\$\begingroup\$

Python 2, 58 57 54 bytes

def f(n):k=(n**3-n)/6;return[v**3for v in~k,1-k,n,k,k]

Try it online!


  • -2 bytes, thanks to Rod
  • -1 byte, thanks to Neil
\$\endgroup\$
  • 1
    \$\begingroup\$ You can save 2 bytes swapping the signal k=-(n-n**3)/6;[v**3for v in~k,1-k,n,k,k] \$\endgroup\$ – Rod Apr 4 '18 at 19:10
  • 1
    \$\begingroup\$ @Rod For -(n-n**3) can you not use (n**3-n)? \$\endgroup\$ – Neil Apr 4 '18 at 21:43
  • \$\begingroup\$ @Neil yes, you can. \$\endgroup\$ – Rod Apr 4 '18 at 22:03
9
\$\begingroup\$

Python 3, 65 bytes

def f(n):k=(n-n**3)//6;return[n**3,(k+1)**3,(k-1)**3,-k**3,-k**3]

Try it online!

I mean, an explicit formula is even here (although he abstracted the construction behind an existential)

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

Java 8, 178 87 73 71 65 bytes

n->new long[]{n*n*n,(n=(n-n*n*n)/6+1)*n*n--,--n*n*n,n=-++n*n*n,n}

-6 bytes thanks to @OlivierGrégoire.

Same explanation at the bottom, but using the base equation instead of the derived one I used before (thanks to @LeakyNun's Python 3 answer for the implicit tip):

k = (n - n3) / 6
n == n3 + (k+1)3 + (k-1)3 - k3 - k3

Try it online.


Old 178 bytes answer:

n->{for(long k=0,a,b,c,d;;){if(n==(a=n*n*n)+(b=(d=k+1)*d*d)+(c=(d=k-1)*d*d)-(d=k*k*k++)-d)return a+","+b+","+c+","+-d+","+-d;if(n==a-b-c+d+d)return-a+","+-b+","+-c+","+d+","+d;}}

Try it online.

Explanation:

I loop k from 0 upwards until a solution is found. In every iteration it will check these two equations:

  • Positive k: n == n3 + (k+1)3 + (k-1)3 - k3 - k3
  • Negative k: n == n3 - (k+1)3 - (k-1)3 + k3 + k3

Why?

Since n - n3 = n*(1-n)*(1+n) and then 6|(n-n3), it can be written as n - n3 = 6k.
6k = (k+1)3 + (k-1)3 - k3 - k3.
And therefore n = n3 + (k+1)3 + (k-1)3 - k3 - k3 for some k.
Source.

\$\endgroup\$
  • 1
    \$\begingroup\$ 65 bytes: n->new long[]{n*n*n,(n=(n-n*n*n)/6+1)*n*n--,--n*n*n,n=-++n*n*n,n} (or 64 using ints for less precise results) \$\endgroup\$ – Olivier Grégoire Apr 4 '18 at 10:43
6
\$\begingroup\$

Jelly, 13 bytes

‘c3µ;;C;~;³*3

Try it online!

Figure out the formula independently. (x+1)3 + (x-1)3 - 2 × x3 == 6 × x.


 === Explanation ===
‘c3µ;;C;~;³*3   Main link. Input: (n).
‘               Increment.
 c3             Calculate (n+1)C3 = (n+1)×n×(n-1)÷6.
   µ            Start a new monadic link. Current value: (k=(n³-n)÷6)
    ;           Concatenate with itself.
     ;C         Concatenate with (1-k).
       ;~       Concatenate with bitwise negation of (k), that is (-1-k)
         ;³     Concatenate with the input (n).
           *3   Raise the list [k,k,1-k,-1-k,n] to third power.
                End of program, implicit print.

Alternative 13 bytes: Try it online!

\$\endgroup\$
  • \$\begingroup\$ ‘c3µ³;;;C;~*3 should save a byte since (n^3-n)/6 = C(n+1, 3) \$\endgroup\$ – miles Apr 5 '18 at 9:05
5
\$\begingroup\$

Octave, 47 40 33 bytes

@(n)[k=(n^3-n)/6,k,-k-1,1-k,n].^3

Try it online!

Saved 6 bytes thanks to Giuseppe, since I had forgotten to remove some old parentheses. Saved another bytes by changing the signs, thanks to rafa11111.

Uses the formula in the linked math.se post:

  1. Since n - n^3 = n(1-n)(1+n) then 6 | (n - n^3) and we can write n - n^3 = 6k.
  2. 6k = (k+1)^3 + (k-1)^3 - k^3 - k^3.

It appears to be longer if I try to solve the equation: (n-n^3)=(k+1)^3 + (k-1)^3 - k^3 - k^3 with regards to k, instead of just using the equation.

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

Minecraft Functions (18w11a, 1.13 snapshots), 813 bytes

perfect cubes in minecraft

Uses six functions:

a

scoreboard objectives add k dummy
scoreboard objectives add b dummy
scoreboard objectives add c dummy
scoreboard players operation x k = x n
function d
function f
scoreboard players operation x k -= x b
scoreboard players set x b 6
scoreboard players operation x k /= x b
scoreboard players set x b 1
function d
scoreboard players operation x c += x b
function f
scoreboard players set x b 1
function d
scoreboard players operation x c -= x b
function f
function d
function e
scoreboard players operation x b -= x c
scoreboard players operation x b -= x c
function c
function b

b

tellraw @s {"score":{"name":"x","objective":"b"}}

c

scoreboard players operation x b *= x c
scoreboard players operation x b *= x c
function b

d

scoreboard players operation x c = x k

e

scoreboard players operation x b = x c

f

function e
function c

"Takes input" from a scoreboard objective named n, create it with /scoreboard objectives add n dummy and then set it using /scoreboard players set x n 5. Then call the function using /function a

Uses the formula from this math.se answer

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

JavaScript (Node.js), 48 45 bytes

  • thanks to @Arnauld for reducing 3 bytes
n=>[n,1-(k=(n**3-n)/6|0),~k,k,k].map(x=>x**3)

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Why |0? n**3-n must be a multiple of 6 for integer n. \$\endgroup\$ – Neil Apr 4 '18 at 21:45
2
\$\begingroup\$

MATL, 21 bytes

|_G|&:5Z^3^t!sG=fX<Y)

This tries all 5-tuples of numbers from the set (-abs(n))^3, (-abs(n)+1)^3, ..., abs(n)^3. So it is very inefficient.

Try it online!

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

Haskell, 43 42 bytes

p n|k<-div(n^3-n)6=map(^3)[n,-k-1,1-k,k,k]

Just the popular answer, translated to Haskell. Thanks to @rafa11111 for saving a byte!

Try it online!

\$\endgroup\$
  • 2
    \$\begingroup\$ You can save one byte changing the sign in the k assignment... \$\endgroup\$ – rafa11111 Apr 4 '18 at 21:19
2
\$\begingroup\$

Husk, 12 bytes

ḟo=⁰Σπ5m^3İZ

Try it online!

Tries all possible lists of 5 cubes, and returns the first one with the correct sum.

Explanation

ḟo=⁰Σπ5m^3İZ
          İZ    List of all integers [0,1,-1,2,-2,3,-3...
       m^3      Cube of each integer [0,1,-1,8,-8,27,-27...
     π5         Cartesian power with exponent 5. This returns a list of all possible
                lists built by taking 5 elements from the input list. This infinite
                list is ordered in such a way that any arbitrary result occurs at a 
                finite index.
ḟo              Find and return the first element where...
    Σ             the sum of the five values
  =⁰              is equal to the input
\$\endgroup\$
1
\$\begingroup\$

C (gcc), 85 81 75 bytes

Saved 4 bytes and then 6 bytes thanks to @ceilingcat's re-ordering of assignments

r[5];f(n){r[1]=(n=(n-(*r=n*n*n))/6+1)*n*n--;r[3]=r[4]=-n*n*n;r[2]=--n*n*n;}

Try it online!

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

Fortran (GFortran), 53 bytes

READ*,N
K=(N**3-N)/6
PRINT*,(/N,1-K,-1-K,K,K/)**3
END

Try it online!

Fortran outgolfing Python? What's going on here?

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

Python 3, 65 61 60 bytes

lambda N:[n**3for k in[(N**3-N)//6]for n in[N,-k-1,1-k,k,k]]

Edit: dropped some unnecessary spaces.

Edit: thanks to rafa11111's smart reordering.

Inspired by this.

Try it online!

\$\endgroup\$
  • \$\begingroup\$ You can save one byte using (N**3-N) and [N,1-k,-1-k,k,k] \$\endgroup\$ – rafa11111 Apr 4 '18 at 21:13
  • 1
    \$\begingroup\$ @rafa11111 smart reordering. Thanks. \$\endgroup\$ – Guoyang Qin Apr 4 '18 at 21:17
1
\$\begingroup\$

R, 40 38 bytes

Makes use of the formula in the linked math.SE post. Down to 2 bytes thanks to Giuseppe.

c(n<-scan(),k<-(n^3-n)/6,k,1-k,-k-1)^3

Try it online!

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

APL (Dyalog Unicode), 30 26 bytes

3*⍨⊢,∘(1 ¯1∘+,2⍴-)6÷⍨⊢-*∘3

Try it online!

APL translation of LeakyNun's answer.

Thanks to Adám for 4 bytes by going tacit.

How?

3*⍨⊢,∘(1 ¯1∘+,2⍴-)6÷⍨⊢-*∘3 ⍝ Tacit function
                   6÷⍨⊢-*∘3 ⍝ (n-n^3)/6 (our k)
                 -)         ⍝ Negate
               2⍴           ⍝ Repeat twice; (yields -k -k)
       (1 ¯1∘+,             ⍝ Append to k+1, k-1
     ,∘                     ⍝ Then append to
    ⊢                       ⍝ n
3*⍨                         ⍝ And cube everything
\$\endgroup\$
  • \$\begingroup\$ Sorry if I missed something, but: 1) since in tio there is an assignment, isn't your answer here just a snippet? 2) although you used 30 characters, since it is in unicode, isn't it using 43 bytes, as pointed in tio? \$\endgroup\$ – rafa11111 Apr 4 '18 at 21:24
  • 1
    \$\begingroup\$ @rafa11111 No and no: APL works weirdly in TIO. The assignment in the “Code” field is actually just a shortcut to use the function in the “Input” field; it’s completely unnecessary for the actual code to work. Also, we count each character as one byte because for Dyalog APL, we use @Adám’s SBCS. I can add the link to the meta post explaining it later but I’m on mobile right now. \$\endgroup\$ – J. Sallé Apr 4 '18 at 21:33
  • \$\begingroup\$ Oh, I see. I didn't knew about these. Thanks for explaining! \$\endgroup\$ – rafa11111 Apr 4 '18 at 21:40
1
\$\begingroup\$

Husk, 20 bytes

m^3m‼:_:→:←;K¹÷6Ṡ-^3

Try it online!

Uses the formula from this post.

Explanation

m^3m‼:_:→:←;K¹÷6Ṡ-^3  Implicit input
                Ṡ-    Subtract itself from it
                   ^3    raised to the third power
              ÷6       Divide by six
   m                   Map over the value with a list of functions:
           ;             Create a singleton list with
            K¹             the function of replace by the input
         :←              Append the function of decrement
       :→                Append the function of increment
    ‼:_                  Append the function of negate twice
m^3                    Cube the numbers of the list
\$\endgroup\$
1
\$\begingroup\$

x86, 41 39 bytes

Mostly straightforward implementation of the formula with input in ecx and output on the stack.

The interesting thing is that I used a cubing function, but since call label is 5 bytes, I store the label's address and use the 2 byte call reg. Also, since I'm pushing values in my function, I use a jmp instead of ret. It's very possible that being clever with a loop and the stack can avoid calling entirely.

I did not do any fancy tricks with cubing, like using (k+1)^3 = k^3 + 3k^2 + 3k + 1.

Changelog:

  • Fix byte count using not instead of neg/dec.

  • -2 bytes by not xoring edx since it is probably 0 from imul.

.section .text
.globl main

main:
        mov     $10, %ecx   # n = 10

start:
        lea     (cube),%edi # save function pointer
        call    *%edi       # output n^3

        sub     %ecx, %eax  # n^3 - n
                            # edx = 0 from cube
        push    $6
        pop     %ebx        # const 6        
        idiv    %ebx        # k = (n^3 - n)/6
        mov     %eax, %ecx  # save k

        call    *%edi       # output k^3
        push    %eax        # output k^3

        not     %ecx        # -k-1        
        call    *%edi       # output (-k-1)^3

        inc     %ecx        
        inc     %ecx        # -k+1
        call    *%edi       # output (-k+1)^3

        ret

cube:                       # eax = ecx^3
        pop     %esi 
        mov     %ecx, %eax
        imul    %ecx
        imul    %ecx

        push    %eax        # output cube
        jmp     *%esi       # ret

Objdump:

00000005 <start>:
   5:   8d 3d 22 00 00 00       lea    0x22,%edi
   b:   ff d7                   call   *%edi
   d:   29 c8                   sub    %ecx,%eax
   f:   6a 06                   push   $0x6
  11:   5b                      pop    %ebx
  12:   f7 fb                   idiv   %ebx
  14:   89 c1                   mov    %eax,%ecx
  16:   ff d7                   call   *%edi
  18:   50                      push   %eax
  19:   f7 d1                   not    %ecx
  1b:   ff d7                   call   *%edi
  1d:   41                      inc    %ecx
  1e:   41                      inc    %ecx
  1f:   ff d7                   call   *%edi
  21:   c3                      ret    

00000022 <cube>:
  22:   5e                      pop    %esi
  23:   89 c8                   mov    %ecx,%eax
  25:   f7 e9                   imul   %ecx
  27:   f7 e9                   imul   %ecx
  29:   50                      push   %eax
  2a:   ff e6                   jmp    *%esi

Here is my testing version that does all the cubing at the end. After the values are pushed on the stack, the cube loop overwrites stack values. It's currently 42 40 bytes but there should be some improvements somewhere.

.section .text
.globl main

main:
        mov     $10, %ecx       # n = 10

start:
        push    %ecx            # output n

        mov     %ecx, %eax
        imul    %ecx
        imul    %ecx
        sub     %ecx, %eax      # n^3 - n
                                # edx = 0 from imul

        push    $6
        pop     %ecx            # const 6        
        idiv    %ecx            # k = (n^3 - n)/6

        push    %eax            # output k
        push    %eax            # output k

        not     %eax            # -k-1        
        push    %eax            # output -k-1

        inc     %eax            
        inc     %eax            # -k+1
        push    %eax            # output -k+1

        dec     %ecx            # count = 5
        add     $20, %esp
cube:           
        mov     -4(%esp),%ebx   # load num from stack
        mov     %ebx, %eax
        imul    %ebx
        imul    %ebx            # cube 
        push    %eax            # output cube
        loop    cube            # --count; while (count)

        ret
\$\endgroup\$
0
\$\begingroup\$

Cubically, 51 characters, 55 bytes

⇒-6-^0+7/0»8
$F:^0%@5-7/0»8^0%@5%@5f1+8^0%@5f1-8^0%

Try it online!

Apparently MDXF forgot to implement the SBCS...

\$\endgroup\$
0
\$\begingroup\$

Unefunge 98, 35 bytes

j&3k:**-6/:1-\:1+\0\-::!#@_::**.37*

Try it online!

It uses the popular formula from this math.se answer.

\$\endgroup\$
0
\$\begingroup\$

Perl 5 -nE, 48 bytes

say$_**3for$i=($_**3-($n=$_))/6,$i,-1-$i,1-$i,$n

hat-tip

\$\endgroup\$
0
\$\begingroup\$

PowerShell Core, 52 bytes

$o,(1-($k=($o*$o-1)*$o/6)),(-$k-1),$k,$k|%{$_*$_*$_}

Try it online!

Uses the equation o=o^3 + (1-k)^3 + (-k-1)^3 + k^3 + k^3, where k=o^3 - o; this is a minor refactoring of the popular l=o-o^3 (with k=-l).

As a side note, the expression l=o-o^3 looks like a cat with a hurt ear.

\$\endgroup\$
0
\$\begingroup\$

Ruby, 43 bytes

->n{[~k=(n**3-n)/6,1-k,n,k,k].map{|i|i**3}}

Try it online!

\$\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.