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.
∧5~lLȧᵐ≥₁∧L^₃ᵐ.+?∧
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
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
Thanks Fatalize for saving one byte
~+l₅≥₁.√₃ᵐ∧
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.
def f(n):k=(n**3-n)/6;return[v**3for v in~k,1-k,n,k,k]
def f(n):k=(n-n**3)//6;return[n**3,(k+1)**3,(k-1)**3,-k**3,-k**3]
I mean, an explicit formula is even here (although he abstracted the construction behind an existential)
k and rewriting your equation. Try it online!
\$\endgroup\$
Commented
Apr 5, 2018 at 17:29
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
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;}}
Explanation:
I loop k from 0 upwards until a solution is found. In every iteration it will check these two equations:
k: n == n3 + (k+1)3 + (k-1)3 - k3 - k3k: n == n3 - (k+1)3 - (k-1)3 + k3 + k3Why?
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.
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\$
Commented
Apr 4, 2018 at 10:43
‘c3µ;;C;~;³*3
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!
‘c3µ³;;;C;~*3 should save a byte since (n^3-n)/6 = C(n+1, 3)
\$\endgroup\$
@(n)[k=(n^3-n)/6,k,-k-1,1-k,n].^3
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:
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.
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
n=>[n,1-(k=(n**3-n)/6|0),~k,k,k].map(x=>x**3)
|0? n**3-n must be a multiple of 6 for integer n.
\$\endgroup\$
|_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.
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!
k assignment...
\$\endgroup\$
Commented
Apr 4, 2018 at 21:19
ḟo=⁰Σπ5m^3İZ
Tries all possible lists of 5 cubes, and returns the first one with the correct sum.
ḟ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
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;}
READ*,N
K=(N**3-N)/6
PRINT*,(/N,1-K,-1-K,K,K/)**3
END
Fortran outgolfing Python? What's going on here?
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.
(N**3-N) and [N,1-k,-1-k,k,k]
\$\endgroup\$
Commented
Apr 4, 2018 at 21:13
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
3*⍨⊢,∘(1 ¯1∘+,2⍴-)6÷⍨⊢-*∘3
APL translation of LeakyNun's answer.
Thanks to Adám for 4 bytes by going tacit.
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
m^3m‼:_:→:←;K¹÷6Ṡ-^3
Uses the formula from this post.
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
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
⇒-6-^0+7/0»8
$F:^0%@5-7/0»8^0%@5%@5f1+8^0%@5f1-8^0%
Apparently MDXF forgot to implement the SBCS...
j&3k:**-6/:1-\:1+\0\-::!#@_::**.37*
It uses the popular formula from this math.se answer.
$o,(1-($k=($o*$o-1)*$o/6)),(-$k-1),$k,$k|%{$_*$_*$_}
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.
-10another possible solution could be-1000+4574296+4410944-4492125-4492125for example. And is it allowed to output--or+-instead of+/-respectively (i.e.3 = 27+-27+-125--64--64instead of3 = 27-27-135+64+64)? \$\endgroup\$--5, I'd say no, as per usual rules on outputting an expression. \$\endgroup\$+signs, just the numbers. \$\endgroup\$-10 = -64 - 64 + 64 + 27 + 27or-10 = -343 + 0 -8 +125 +216\$\endgroup\$