Calcule a cuántos cubos se puede cortar un cubo

9

Imagine un cubo que podamos cortar en cubos más pequeños sin piezas restantes.

Averigua cuántos cubos puede cortar un cubo.

Por ejemplo, un cubo se puede cortar en 8, 27 (obviamente 3er potencias de enteros) y 20 (19 cubos pequeños más uno ocho veces el tamaño de los otros, ver imagen).
Vea aquí algo de ayuda: http://mathworld.wolfram.com/CubeDissection.html

ingrese la descripción de la imagen aquí El programa debe tomar como entero de entrada n( 0 <= n <= 1 000) e imprimir todos los números menores o iguales para nque un cubo se pueda cortar en ese número de cubos. Suponga que el cubo se puede cortar en 1 cubo y no se puede cortar en 0 cubos.

Puede usar solo tipos de datos integrales (sin matrices, objetos, etc.) de tamaño no mayor a 64 bits. El código más corto gana.

Somnium
fuente
Esto tiene potencial pero necesita especificarlo más claramente. De hecho, un cubo se puede cortar en 20 cubos: en lugar de cortarlo en 27 cubos del lado 1/3 del original, córtelo en 19 cubos del lado 1/3 del original y uno que sea 8 veces más grande (lado 2/3 del original.) Sí, creo que una imagen sería útil
Level River St
Ese es un cubo bastante áspero que he dibujado, no dudes en cambiarlo. A primera vista, esto parece trivial, pero creo que hay un rango interesante alrededor de 125-216 (5 ^ 3-6 ^ 3.) Es probable que para números muy grandes sea posible casi todas las divisiones.
Level River St
Veremos si todos los números después de cierto umbral serán posibles.
Somnium
3
La respuesta está realmente aquí: mathworld.wolfram.com/CubeDissection.html
Level River St
1
Dado que ahora tenemos una solución bastante trivial, es posible que desee cambiar esto de nuevo al código de golf o poner una restricción realmente dura en las presentaciones.
Martin Ender

Respuestas:

1

Golfscript, 55 (o 43 42)

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

Puede probarse aquí (solo cambie el número en la línea 2) y solo usa la matriz (dos últimos caracteres de código) para una impresión limpia, no para ninguna colección o resolución de problemas. Si lo deja, todos los resultados serán concatenados.

Método: Iterar hacia abajo desde n dado: Si el número actual es mayor que 47 o de la forma 1 + 7x, 20 + 7x, 38 + 7x, o 39 + 7x donde x = cualquier número entero no negativo, manténgalo en la pila , de lo contrario colóquelo.

Respuesta corta (43 bytes):

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

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

Método: similar, pero con algunas operaciones de teoría de conjuntos. Esto usa matrices, por lo que técnicamente no es una respuesta aceptable. Se puede probar aquí . Por cierto: nadie dijo que tenían que estar en un orden particular;)

Kyle McCormick
fuente
1

Mathematica, 62 bytes (o 52)

Es una respuesta codificada, nada interesante.

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

Este tiene 52 bytes de longitud pero viola mis reglas: utiliza enteros grandes (potencias de 2) y listas (Rango).

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

Somnium
fuente
0

C, 72

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

Otra respuesta codificada. Esto cuenta hacia abajo (no hay nada en las reglas sobre el orden en que los números tienen que salir). En teoría, debería funcionar. La constante tiene un bit establecido en 1 para todos los números en los que NO se puede cortar un cubo, y un 0 para los números que sí se pueden cortar. En teoría, la constante cuando se desplaza a la derecha por un número muy grande debe ser cero, por lo que el número grande siempre debe imprimirse.

Lo interesante es que en la práctica esto no funciona. El código anterior compila y funciona bien en GCC hasta 65. Pero por encima de ese número hay un error (o "característica") en el compilador. se interpreta 0x952BD7AF7EFC>>icomo 0x952BD7AF7EFC>>i%64. Por lo tanto, omite (por ejemplo) los números del 66 al 71 (64 + 2 a 64 + 7).

Para ejecutarse en Visual Studio, se necesita un poco más repetitivo (no le permite salirse con la suya con números enteros implícitos y #includes). Una vez que el programa está en funcionamiento, está bien hasta 257 ... Luego se salta 258 263 (256 + 2 a 256 + 7.) Por lo tanto, está tomandoi%256.

Puedo arreglarlo más tarde (si me molestan). Moral: los manuales del compilador normalmente no le indican el límite superior de los cambios de bits. ¡Hay una razón para eso!

Level River St
fuente
Esto usa exactamente el mismo principio que la respuesta mía)
Somnium
De hecho, incluso tenemos básicamente la misma constante (con el bit cero sin usar y el bit 1 representando el número 1.) En CI, guarde un solo byte especificando la constante en hexadecimal. Tengo un 0bit cero, podría cambiarlo por el 1tuyo para el caso i = 0. Pero nunca se muestra de todos modos.
Level River St
@steveverrill por favor explique cómo NUM>>icambia a NUM>>i%64. Además, si un 64-bitnúmero es correcto desplazado más de 64 veces que debe convertirsezero
manav mn
@Manav, de hecho, debería convertirse en cero. Como digo, el compilador tiene un error. NUM>>ise convierte NUM>>(i%64)o equivalente NUM>>(i&63)porque el compilador está truncando los bits más a la izquierda de iantes de realizar el desplazamiento de bits. GCC solo considera los 6 bits más a la derecha. Visual Studio tiene el mismo error pero es ligeramente mejor, considerando solo los 8 bits más a la derecha NUM>>(i%256). Por curiosidad intentaré Ideone cuando llegue a casa del trabajo.
Level River St
La ideona se comporta exactamente como el CCG. ideone.com/EpKTpO
Level River St