# Calculate to how many cubes one cube can be cut

Imagine some cube which we can cut into smaller cubes without remaining pieces.

Find to how many cubes a cube can be cut.

For example, a cube can be cut into 8, 27 (obviously 3rd powers of integers) and 20 (19 small cubes plus one eight times the size of the others, see image).
See here some help: http://mathworld.wolfram.com/CubeDissection.html

Program should take as input integer n (0 <= n <= 1 000) and print all numbers less or equal to n so that a cube can be cut into that number of cubes. Suppose that cube can be cut into 1 cube and cannot into 0 cubes.

You can use only integral data-types (no arrays, objects etc) of size no greater than 64-bits. Shortest code wins.

• This has potential but you need to specify it more clearly. A cube can indeed be cut into 20 cubes: instead of cutting it into 27 cubes of side 1/3 the original, cut it into 19 cubes of side 1/3 the original and one which is 8 times larger (side 2/3 the original.) Yes I think a picture would be helpful – Level River St Jul 21 '14 at 20:12
• That's a pretty rough cube I've drawn, feel free to change it. At first sight this seems trivial but I think there's an interesting range around 125-216 (5^3-6^3.) It's probable that for very large numbers nearly all divisions are possible. – Level River St Jul 21 '14 at 20:29
• We will see whether all numbers after some threshold will be possible. – Somnium Jul 21 '14 at 20:33
• The answer is actually here: mathworld.wolfram.com/CubeDissection.html – Level River St Jul 21 '14 at 21:33
• Since we have a fairly trivial solution now, you might want to change this back to code golf or put some really hard restriction on the submissions. – Martin Ender Jul 21 '14 at 22:08

# Golfscript, 55 (or 43 42)

{.:^}{.47>20{.^>^@- 7%|!|}:/~1/38/39/{}{;}if^(}while;]


Can be tested here (just change the number on line 2) and only uses the array (last two chars of code) for clean printing, not for any collection or problem solving. If you leave it off, all results will be concatenated.

Method: Iterate down from given n: If current number is greater than 47 or of the form 1+7x, 20+7x, 38+7x, or 39+7x where x = any non-negative integer, then keep it on the stack, otherwise drop it.

{:/6+,{7*/+}%|}:&;):a,48,^1&20&38&39&{a<},

):a,48,^1{:/6+,{7*/+}%|}:&~20&38&39&{a<},


Method: Similar, but with a few set theory ops. This uses arrays so it's technically not an acceptable answer. Can be tested here. Btw: nobody ever said they had to be in any particular order ;)

Mathematica, 62 bytes (or 52)

If[EvenQ@BitShiftRight[164015534735101,n],Print@n]~Do~{n,1000}

This one is 52 bytes long but violates my rules - it uses large integers (powers of 2) and lists (Range).

Select[Range@1000,EvenQ@Floor[164015534735101/2^#]&]

# C, 72

i;main(){for(scanf("%d",&i);i;i--)0x952BD7AF7EFC>>i&1||printf("%d ",i);}


Another hardcoded answer. This counts downwards (there's nothing in the rules about the order the numbers have to be output in.) In theory it should work. The constant has a bit set to 1 for all the numbers into which a cube can NOT be cut, and a 0 for the numbers which can. In theory, the constant when right shifted by a very large number should be zero, so the large number should always be printed.

What's interesting is that in practice this does not work. The code above compiles and runs fine on GCC up to 65. But above that number there is a bug (or "feature") in the compiler. it interprets 0x952BD7AF7EFC>>i as 0x952BD7AF7EFC>>i%64. So it skips (for example) the numbers 66 through 71 (64+2 through 64+7).

To run in Visual Studio, a bit more boilerplate is needed (it doesn't let you get away with things like implied integers and #includes.) Once the program's up and running, it's fine up to 257... Then it skips 258 through 263 (256+2 through 256+7.) So it's taking i%256.

I may fix it later (if I can be bothered.) Moral: compiler manuals don't normally tell you the upper limit on bitshifts. There's a reason for that!

• This uses exactly the same principle as mine answer) – Somnium Jul 22 '14 at 20:15
• Indeed, we even have basically the same constant (with bit zero unused and bit 1 representing the number 1.) In C I save a single byte by specifying the constant in hex. I have a 0 for bit zero, I could change it for a 1 like yours for the case i=0. But it never gets displayed anyway. – Level River St Jul 22 '14 at 20:27
• @steveverrill please explain how NUM>>i changes to NUM>>i%64. Also if a 64-bit number is right shifted more than 64 times it should become zero – manav m-n Jul 23 '14 at 5:56
• @Manav indeed it should become zero. As I say, the compiler has a bug. NUM>>i becomes NUM>>(i%64) or equivalently NUM>>(i&63)because the compiler is truncating the leftmost bits of i before performing the bitshift. GCC only considers only the rightmost 6 bits. Visual Studio has the same bug but is slightly better, considering only the rightmost 8 bits NUM>>(i%256)`. Out of curiosity I will try Ideone when I get home from work. – Level River St Jul 23 '14 at 8:01
• ideone behaves exactly like GCC. ideone.com/EpKTpO – Level River St Jul 23 '14 at 22:17