How many cubes can be built

Your task is to build a structure with $n$ cubes. The volume of cubes follow the following sequence (bottom -> top)

input

The total volume of the structure ($V$).

output

value of ($n$), i.e : The total number of cubes.

$V = n^3 + (n-1)^3 + .... + 1^3$

notes

• Input will always be an integer.
• Sometimes it isn't possible to follow the sequence, i.e : $V$ doesn't represent a specific value for $n$. In that event return -1, or a falsy value of your choosing (consistency is required though).
• This is so shortest answer in bytes for each language wins.
• No answer will be marked accepted for the above mentioned reason.

requests

• This is my first challenge on the site so bear with me, and forgive (and tell me about) any mistakes that I made.
• If you can, kindly write an explanation on how your code works, so others can understand and appreciate your work.

examples

input  : 4183059834009
output : 2022

input  : 2391239120391902
output : -1

input  : 40539911473216
output : 3568


Thanks to @Arnauld for the link to this :

Isn't that nice.

• This is a nicely written first challenge. However, I'd strongly advise to add a few test cases. Aug 26, 2018 at 13:03
• @Arnauld, ok working on it right now and thanks :)
– user82328
Aug 26, 2018 at 13:06
• OEIS A000537 Aug 26, 2018 at 13:10
• Can you please explain how input 4183059834009 gives output 2022? Aug 26, 2018 at 13:10
• @SuperJedi224 AFAIK the default rule is "whatever range the natural integer type of your language has", of course without using a small range for a loophole -- at least that's what I assumed in my answer :o Aug 27, 2018 at 10:15

JavaScript (ES7), 31 bytes

A direct formula. Returns 0 if there's no solution.

v=>(r=(1+8*v**.5)**.5)%1?0:r>>1


Try it online!

How?

The sum $S_n$ of the first $n$ cubes is given by:

$$S_n = \left(\frac{n(n+1)}{2}\right)^2 = \left(\frac{n^2+n}{2}\right)^2$$

(This is A000537. This formula can easily be proved by induction. Here is a nice graphical representation of $S_5$.)

Reciprocally, if $v$ is the sum of the first $x$ cubes, the following equation admits a positive, integer solution:

$$\left(\frac{x^2+x}{2}\right)^2=v$$

Because $(x^2+x)/2$ is positive, this leads to:

$$x^2+x-2\sqrt{v}=0$$

Whose positive solution is given by:

$$\Delta=1+8\sqrt{v}\\ x=\frac{-1+\sqrt{\Delta}}{2}$$

If $r=\sqrt{\Delta}$ is an integer, it is guaranteed to be an odd one, because $\Delta$ itself is odd. Therefore, the solution can be expressed as:

$$x=\left\lfloor\frac{r}{2}\right\rfloor$$

Commented

v =>                    // v = input
( r =                 //
(1 + 8 * v ** .5)   // delta = 1 + 8.sqrt(v)
** .5               // r = sqrt(delta)
) % 1 ?               // if r is not an integer:
0                   //   return 0
:                     // else:
r >> 1              //   return floor(r / 2)


Recursive version, 36 35 bytes

Returns NaN if there's no solution.

f=(v,k=1)=>v>0?1+f(v-k**3,k+1):0/!v


Try it online!

Commented

f = (v,                   // v = input
k = 1) =>         // k = current value to cube
v > 0 ?                 // if v is still positive:
1 +                   //   add 1 to the final result
f(                    //   do a recursive call with:
v - k ** 3,         //     the current cube subtracted from v
k + 1               //     the next value to cube
)                     //   end of recursive call
:                       // else:
0 / !v                //   add either 0/1 = 0 if v is zero, or 0/0 = NaN if v is
//   non-zero (i.e. negative); NaN will propagate all the
//   way to the final output

• Hi, I created an answer (to my own question) link, since you published first I wanted to ask is it ok to publish twice in same language ?
– user82328
Aug 31, 2018 at 11:41
• @Any3nymoususer Posting several answers in the same language is perfectly fine. Answering its own challenge should not be done before a couple of days, but I guess that's now OK. Aug 31, 2018 at 17:31
• Oh, in that case thnx for telling me :)
– user82328
Aug 31, 2018 at 17:41

05AB1E, 6 bytes

ÝÝOnIk


Try it online!

Port of Jonathan's Jelly answer. Take the cumulative sum of [0 ... n], square each and find the index of V.

05AB1E, 7 bytes

ÝÝ3mOIk


Try it online!

How it works

ÝÝ3mOIk – Full program.
ÝÝ      – Yield [[0], [0, 1], [0, 1, 2], ... [0, 1, 2, ... V]].
3mO   – Raise to the 3rd power.
Ik – And find the index of the input therein. Outputs -1 if not found.


8-byte alternative: ÝÝÅΔ3mOQ.

• I have no idea why both 3mO and nO work... Probably also mention -1 is the falsy value. Aug 30, 2018 at 16:46

R, 42 40 bytes

-2 bytes thanks to Giuseppe

function(v,n=((1+8*v^.5)^.5-1)/2)n*!n%%1


Try it online!

Port of Arnauld's JavaScript answer. Also returns 0 if there's no solution.

• Good catch @Giuseppe ! Aug 26, 2018 at 22:50
• vote for R as language of the month! Aug 27, 2018 at 18:09
• @Giuseppe done! Aug 27, 2018 at 18:10

Jelly,  5  4 bytes

RÄ²i


A monadic link, yields 0 if not possible.

Try it online! way too inefficient for the test cases! (O(V) space :p)

Here is an 8-byte version that performs a cube-root of V first to make it O(V^(1/3)) instead. Using that 8-byte version here is a test-suite

How?

$$\sum_{i=1}^{i=n}i^3=\left(\sum_{i=1}^{i=n}i\right)^2$$

RÄ²i - Link: integer, V
R    - range of v -> [1,2,3,...,V]
Ä   - cumulative sums -> [1,3,6,...,(1+2+3+...+V)]
²  - square -> [1,9,36,...,(1+2+3++...+V)²] ( =[1³,1³+2³,1³+2³+3³,...,(1³+2³+3³+...+V³)] )

• Is this valid ? since it can't handle input shown in test cases ? (I haven't got any idea)
– user82328
Aug 26, 2018 at 13:26
• It is valid, it's just the range that gives a memory error for those test cases. Try smaller values like 36 Aug 26, 2018 at 13:27
• @FiveCrayFish973 yes, it's quite normal to sacrifice usability/efficiency/etc for byte-count in code-golf (unless the spec enforces some limits). See the 9-byte version for one that works for your test cases. Aug 26, 2018 at 13:37
• @JonathanAllan cool, I wasn't aware on what the rules of this community suggest. If it's valid, it's valid. Cheers
– user82328
Aug 26, 2018 at 13:38
• Too bad Ä²i behaves like ²⁼ (Ị, in other words). Aug 26, 2018 at 17:57

Elixir, 53 bytes

&Enum.find_index 0..&1,fn n->&1*4==n*n*(n+1)*(n+1)end


Try it online!

Elixir, 74 bytes

fn v->Enum.find_index 0..v,&v==Enum.sum Enum.map(0..&1,fn u->u*u*u end)end


Try it online!

Definitely sub-optimal. But I am just an Elixir newbie! :) Returns nil for "invalid" values of V.

Japt, 7 bytes

o³å+ bU


Try it

Explanation

            :Implicit input of integer U
o           :Range [0,U)
³          :Cube each
bU     :0-based index of U


Alternative

Çõ³xÃbU


Try it

Cubix, 27 bytes (or volume 27?)

Seems like the right place for this language.

I@.1OW30pWpP<s)s;;q\.>s-.?/


Try it online!

This wraps onto a 3x3x3 cube as follows

      I @ .
1 O W
3 0 p
W p P < s ) s ; ; q \ .
> s - . ? / . . . . . .
. . . . . . . . . . . .
. . .
. . .
. . .


Watch it run

It essential brute forces by taking increasing cubes away from the input. If it results in zero, output n otherwise if there is a negative result, print 0 and exit.

Perl 6, 3029 26 bytes

-4 bytes thanks to Jo King

{first :k,.sqrt,[\+] ^1e4}


Try it online!

Brute-force solution for n < 10000. Uses the equation from Jonathan Allan's answer. 37 36 bytes solution for larger n (-1 byte thanks to Jo King):

{!.[*-1]&&$_-2}o{{$_,*-$++³...1>*}}  Try it online! Returns False if there's no solution. Explanation  o # Combination of two anonymous Blocks { } # 1st Block { } # Reset anonymous state variable$
$_,*-$++³...1>*    # Sequence n,n,n-1³,n-1³-2³,... while positive
{             }  # 2nd Block
!.[*-1]&&       # Return False if last element is non-zero
$_-2 # Return length of sequence minus two otherwise  • For the brute force, you could do 0..$_ to be valid for all numbers, even if it will time out on larger ones. For normal golfing, you can remove the . from the first one and change the second from 0>=* to 1>*
– Jo King
Aug 27, 2018 at 5:53
• 26 bytes
– Jo King
Aug 28, 2018 at 5:55

JavaScript (Node.js), 28 bytes

a=>a**.5%1?0:(2*a**.5)**.5|0


Try it online!

I know it's my own question and all, but I had a better answer (for this lang) then is present, so I posted. Hope it's ok

APL (Dyalog), 18 bytes

{o×⍵≥o←⍵⍳⍨+\3*⍨⍳⍵}


Try it online!

Matlab, 27 bytes

@(v)find(cumsum(1:v).^2==v)


Returns the n if exists or an empty matrix if not.

How it works

            1:v            % Creates a 1xV matrix with values [1..V]
cumsum(   )           % Cumulative sum
.^2        % Power of 2 for each matrix element
==v     % Returns a 1xV matrix with ones where equal to V
find(                 )    % Returns a base-1 index of the first non-zero element


Try it Online!

Note It fails for large v due to memory limitations.

Python 3, 60 bytes

lambda V:[*[(n*-~n/2)**2for n in range(V+1)],V].index(V)%-~V


Try it online!

-6 thanks to Mr. Xcoder.

If we can throw an error in case there's no $n$ for a particular $V$, we can get this down to 51 bytes:

lambda V:[(n*-~n/2)**2for n in range(V+1)].index(V)


Try it online!

Perl 6, 33 bytes

{$!+>1 if ($!=sqrt 1+8*.sqrt)%%1}


Try it online!

This uses Arnauld's method. Returns an Empty object if the number is not valid.

dc, 19 bytes

4*dvvdddk*+d*-0r^K*


Input and output is from the stack, returns 0 if no solution.

Try it online!

Explanation

If there's a solution n, the input is ((n^2+n)^2)/4. So we'll calculate a trial solution as n=sqrt(sqrt(4*input)), using dc's default 0 decimal place precision for square roots, then compare (n^2+n)^2 to 4*input to see if it's actually a solution.

4*dvv         Calculate a trial solution n (making a copy of 4*input for later use)
dddk          Store the trial solution in the precision and make a couple copies of it
*+d*          Calculate (n^2+n)^2
-             Subtract from our saved copy of 4*input - now we have 0 iff n is a solution
0r^           Raise 0 to that power - we now have 1 if n is a solution, 0 if not
K*            Multiply by our saved trial solution


The penultimate line relies on the non-obvious fact that to dc, 0^x=0 for all nonzero x (even negative x!) but 0^0=1.

Python 3, 53 48 bytes

f=lambda V,n=1:V>0and f(V-n**3,n+1)or(not V)*n-1


Try it online!

-3 bytes from Jo King

Returns -1 for no answer.

Only works up to n=997 with the default recursion limits.

Repeatedly takes bigger and bigger cubes from the volume until it arrives at zero (success, return number of cubes removed), or a negative number (no answer).

Explanation:

f=lambda V,n=1: # f is a recursive lambda taking the volume and the cube size (defaulting to 1)

V>0and               # if the volume is positive
f(V-n**3,n+1) # then we are not to the right cube size yet, try again with n+1, removing the volume of the nth cube

or # if V is not positive
(not V)*n-1
# case V == 0:
# (not V)*n == n; return n-1, the number of cubes
# case V < 0:
# (not V)*n == 0; return -1, no answer

• and/or or lists are usually shorter than if/else. 50 bytes
– Jo King
Aug 27, 2018 at 6:07
• @JoKing Thanks! I got two more bytes off also. Aug 28, 2018 at 4:53
• not V => V==0 or V>-1
– Jo King
Aug 28, 2018 at 5:33

gvm (commit 2612106) bytecode, 70 59 bytes

(-11 bytes by multiplying in a loop instead of writing the code for multiplying twice)

Hexdump:

> hexdump -C cubes.bin
00000000  e1 0a 00 10 00 1a 03 d3  8a 00 f6 2a fe 25 c8 d3  |...........*.%..|
00000010  20 02 2a 04 0a 01 1a 02  00 00 20 08 4a 01 fc 03  | .*....... .J...|
00000020  d1 6a 02 52 02 cb f8 f4  82 04 f4 e8 d1 6a 03 0a  |.j.R.........j..|
00000030  03 fc d5 a8 ff c0 1a 00  a2 00 c0                 |...........|
0000003b


Test runs:

> echo 0 | ./gvm cubes.bin
0
> echo 1 | ./gvm cubes.bin
1
> echo 2 | ./gvm cubes.bin
-1
> echo 8 | ./gvm cubes.bin
-1
> echo 9 | ./gvm cubes.bin
2
> echo 224 | ./gvm cubes.bin
-1
> echo 225 | ./gvm cubes.bin
5


Not really a low score, just using this nice question for testing gvm here ;) The commit is older than the question of course. Note this is an 8bit virtual machine, so using some code handling only the natural unsigned number range 0-255, the test cases given in the question won't work.

Manually assembled from this:

0100  e1         rud                     ; read unsigned decimal
0101  0a 00      sta     $00 ; store to$00 (target sum to reach)
0103  10 00      ldx     #$00 ; start searching with n = #0 0105 1a 03 stx$03             ; store to $03 (current cube sum) 0107 d3 txa ; X to A loop: 0108 8a 00 cmp$00             ; compare with target sum
010a  f6 2a      beq     result          ; equal -> print result
010c  fe 25      bcs     error           ; larger -> no solution, print -1
010e  c8         inx                     ; increment n
010f  d3         txa                     ; as first factor for power
0110  20 02      ldy     #$02 ; multiply #02 times for ... 0112 2a 04 sty$04             ; ... power (count in $04) ploop: 0114 0a 01 sta$01             ; store first factor to $01 ... 0116 1a 02 stx$02             ; ... and second to $02 for multiplying 0118 00 00 lda #$00            ; init product to #0
011a  20 08      ldy     #$08 ; loop over 8 bits mloop1: 011c 4a 01 lsr$01             ; shift right first factor
011e  fc 03      bcc     noadd1          ; shifted bit 0 -> skip adding
0120  d1         clc                     ;
0121  6a 02      adc     $02 ; add second factor to product noadd1: 0123 52 02 asl$02             ; shift left second factor
0125  cb         dey                     ; next bit
0126  f8 f4      bpl     mloop1          ; more bits -> repeat
0128  82 04      dec     $04 ; dec "multiply counter" for power 012a f4 e8 bne ploop ; not 0 yet -> multiply again 012c d1 clc 012d 6a 03 adc$03             ; add power to ...
012f  0a 03      sta     $03 ; ... current cube sum 0131 fc d5 bcc loop ; repeat unless adding overflowed error: 0133 a8 ff wsd #$ff            ; write signed #$ff (-1) 0135 c0 hlt ; result: 0136 1a 00 stx$00             ; store current n to $00 0138 a2 00 wud$00             ; write \$00 as unsigned decimal
013a  c0         hlt


edit: I just fixed a bug in gvm; without this fix, gvm tried to read binary programs in text mode, which might break (code above doesn't contain any 0xd bytes so won't break on windows without this fix).

K (oK), 21 bytes

{(,_r%2)@1!r:%1+8*%x}


Try it online!

{(,_r%2)@1!r:%1+8*%x} # Main function, argument x

the function will return (_r%2) iff 1!r == 0, else it returns null (0N). That is due to the single element in the list having index 0, and trying to index that list with any number other than 0 will return null.