Calculate to how many cubes one cube can be cut

Question

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.

Answer 1

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.

Short answer (43 bytes):

{:/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 ;)

Answer 2

Mathematica, 62 bytes (or 52)

It's hardcoded answer, nothing interesting.

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^#]&]

Answer 3

Ruby, 44 bytes

->n{1.upto(n){|i|i/7<777159>>i%7*3&7||p(i)}}

Try it online!

Takes advantage of the fact that solutions occur modulo 7 (as a result of the fact that a cube can be dissected into 8 cubes, adding 7.)

Below are all solutions below 49 (there is a solution for all numbers over 49.) The magic number 777159 decimal = 2755707 octal encodes the lowest value of i/7 for which a solution exists for each possible value of i%7.

n%7=0                         not possible where i/7<7
n%7=1    1,8,15,22,29,36,43                      i/7<0
n%7=2                                            i/7<7 
n%7=3                 38,45                      i/7<5   
n%7=4                 39,46                      i/7<5
n%7=5                                            i/7<7
n%7=6        20,27,34,41,48                      i/7<2

Answer 4

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!