La tarea
Dado un entero positivo de entrada n
(desde 1 hasta el límite de su idioma, inclusive), devuelve o genera el número máximo de enteros positivos distintos que suman n
.
Casos de prueba
Dejemos f
definir una función válida de acuerdo con la tarea:
La secuencia para f
, comenzando en 1:
1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, ...
Como un caso de prueba más grande:
>>> f(1000000000) // Might not be feasible with brute-forcers
44720
Código de prueba
Para cualquier caso de prueba que no se indique explícitamente, la salida de su código debe coincidir con el resultado de lo siguiente:
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
System.out.println((int) Math.floor(Math.sqrt(2*x + 1./4) - 1./2));
}
}
code-golf
math
number-theory
integer
integer-partitions
Addison Crump
fuente
fuente
Respuestas:
05AB1E , 4 bytes
Pruébalo en línea!
Herramienta perfecta para el trabajo.
ÅT
Los rendimientos de la lista de Å ll t números riangular hasta e incluyendo N (por desgracia incluye 0 también, de lo contrario, sería de 3 bytes),g<
recupera el len g º y decrementa ella.fuente
Gelatina ,
65 bytesPruébalo en línea!
Algo eficiente. Esta secuencia se incrementa en números triangulares, por lo que solo cuenta cuántos números triangulares son más pequeños que n .
Explicación:
fuente
Haskell , 26 bytes
-2 bytes gracias a H.PWiz.
Pruébalo en línea!
Esto devuelve el enésimo elemento de los números enteros donde cada i se replica i + 1 veces.
fuente
succ
representasuccessor
.Brain-Flak , 36 bytes
Pruébalo en línea!
Esto usa la misma estructura que el algoritmo de división estándar, excepto que el "divisor" se incrementa cada vez que se lee.
fuente
Pari / GP , 19 bytes
Pruébalo en línea!
fuente
Brain-Flak , 82 bytes
Espacio en blanco agregado para "Legibilidad"
Pruébalo en línea!
fuente
Jalea , 7 bytes
Pruébalo en línea!
Jalea , 9 bytes
Pruébalo en línea!
Esto es más largo que el de
Dennisy DJ, pero esta vez a propósito . Muy, muy eficiente .fuente
M
.R , 28 bytes
Pruébalo en línea!
Crea el vector de tiempos
1
repetidos2
, tiempos2
repetidos3
, ..., tiemposn
repetidosn+1
y toma elnth
elemento. Esto generará un error de memoria porque1:n
es demasiado grande o porque la lista repetida conn*(n+1)/2 - 1
elementos es demasiado grande.R , 29 bytes
Pruébalo en línea!
Calcula el valor directamente, usando la fórmula que se encuentra en la respuesta de alephalpha . Esto debería ejecutarse sin problemas, aparte de la posible precisión numérica.
R , 30 bytes
Pruébalo en línea!
Cuenta los números triangulares menores o iguales que
n
. Esto posiblemente provocará un error de memoria si1:n
es lo suficientemente grande, por ejemplo,1e9
arrojaError: cannot allocate vector of size 3.7 Gb
.fuente
APL (Dyalog) , 8 bytes
Pruébalo en línea!
fuente
TI-Basic, 12 bytes
fuente
JavaScript (Node.js) , 18 bytes
Pruébalo en línea!
fuente
floor((sqrt(8x+4)-1)/2)
(su fórmula) yfloor((sqrt(8x+1)-1)/2)
(fórmula correcta) dan el mismo resultado para todosx
.Japt , 8 bytes
Solución de fórmula cerrada.
Intentalo
Explicación
Multiplique por 8, sume 1 (
Ä
), obtenga la raíz cuadrada (¬
), reste 1 (É
) y el piso divida el resultado por 2 (z
).Alternativa, 8 bytes
Puerto de la solución Jelly de DJMcMayhem .
Intentalo
Genere una matriz de enteros (
õ
) de 1 a entrada, reduzca acumulativamente (å
) mediante la suma (+
) y cuente (è
) los elementos que son menores o iguales que (§
) la entrada (U
).fuente
Befunge,
3220 bytesPruébalo en línea!
fuente
Brain-Flak ,
705648 bytesPruébalo en línea!
Explicación
La parte principal de esto es el siguiente fragmento que he escrito:
Esto no hará nada si el TOS es positivo y cambiará las pilas de lo contrario. Es super apilado impuro pero funciona. Ahora, la parte principal del programa resta números cada vez más grandes de la entrada hasta que la entrada no sea positiva. Comenzamos el acumulador en 1 cada vez restando 1 más que el acumulador de la entrada.
Podemos poner eso dentro del fragmento de arriba
Eso se coloca en un bucle para que se ejecute hasta que cambiemos las pilas. Una vez que finaliza el ciclo, recuperamos el acumulador cambiando las pilas y eliminando la basura.
fuente
Pyth , 7 bytes
Pruébalo en línea!
Filtrar-mantener las particiones enteras que son
I
variables sobre la deduplicación, agarrar elh
ead y obtener sul
profundidad.Prueba de validez
No muy riguroso ni bien redactado.
Deje que A = a 1 + a 2 + ... + a n y B = b 1 + b 2 + ... + b m sea dos particiones distintas del mismo entero N . Asumiremos que A es la partición única más larga . Después de que deduplicar B , es decir, reemplazar múltiples ocurrencias de un mismo número entero con sólo uno de ellos, sabemos que la suma de B es menor que N . Pero también sabemos que el resultado de la función está aumentando (no estrictamente), por lo que podemos deducir que la partición única más larga A siempre tiene al menos la misma cantidad de elementos que el recuento de elementos únicos en otras particiones.
fuente
Triangularidad , 49 bytes.
Pruébalo en línea!
Cómo funciona
La triangularidad requiere que el código tenga una distribución triangular de los puntos. Es decir, la longitud de cada fila debe ser igual al número de filas multiplicado por 2 y decrementado, y cada fila debe tener (en cada lado) un número de puntos igual a su posición en el programa (la fila inferior es la fila 0, el de arriba es la fila 1 y así sucesivamente). Solo hay un par de comandos, y cualquier carácter distinto de los enumerados en la página 'Wiki / Comandos' se trata como no operativo (los puntos extraños no afectan el programa de ninguna manera, siempre que la forma general del programa permanece rectangular).
Tenga en cuenta que para los comandos de dos argumentos, he usado una y B a lo largo de la explicación. Teniendo esto en cuenta, veamos qué hace el programa real, después de eliminar todos los caracteres extraños que compensan el relleno:
Una solución alternativa, y más corta si el relleno no fuera necesario:
Pruébalo en línea!
fuente
PowerShell 3.0, 45 bytes
La llamada matemática duele y el redondeo del banquero de PS es el verdadero demonio (por lo tanto, necesita regex para truncar para salvar un byte), pero esto parece bastante bien.
fuente
Java (JDK) , 28 bytes
Pruébalo en línea!
Debido a que el ejemplo realmente no estaba bien jugado: p
Créditos
fuente
Jalea , 7 bytes
Se ejecuta aproximadamente en O (2 n ) tiempo.
Pruébalo en línea!
Cómo funciona
fuente
JavaScript (ES7),
2219 bytes-3 bytes gracias a ETHproductions.
Intentalo
Explicación
Multiplique la entrada por 8 y agregue 1, aumente eso a la potencia de .5, dándonos la raíz cuadrada, reste 1 y cambie el resultado a la derecha por 1.
fuente
n=>(8*n+1)**.5-1>>1
para guardar 3 bytes? (no lo he probado)Python 2/3, 32 bytes
Implementación de Python de la fórmula de formulario cerrado
La división entera se
//2
redondea hacia cero, por lo que no sefloor( )
requierefuente
from math import sqrt
funcionar? Si es así, debe incluirse en el bytecount. (En ese casolambda n:int((math.sqrt(1+8*n)-1)//2) import math
es un poco más corto. )Haskell , 28 bytes
Es un poco aburrido, pero
es bastante más corto que la otra solución de Haskell ytiene una expresión realmente agradable. Desafortunadamente no pude acortarlo sin que el sistema de tipos se interpusiera:Pruébalo en línea!
Punto libre, 33 bytes
Alternativamente, 33 bytes
Misma longitud que la versión sin puntos, pero mucho más interesante.
fuente
Vía Láctea , 12 bytes
Explicación
fuente
Pyt ,
75 bytesExplicación:
Más rápido, pero más largo
Pyt ,
119 bytesExplicación:
Manera alternativa - puerto de la respuesta de Shaggy
Pyt ,
87 bytesfuente
J , 11 bytes
Pruébalo en línea!
fuente
*
para producir 1Espacio en blanco , 111 bytes
Se agregaron letras
S
(espacio),T
(tabulación) yN
(nueva línea) solo como resaltado.[..._some_action]
agregado solo como explicación.Pruébelo en línea (solo con espacios en bruto, pestañas y nuevas líneas).
Explicación en pseudocódigo:
Utiliza la fórmula:
NOTA: El espacio en blanco no tiene una raíz cuadrada incorporada, por lo que debemos hacerlo manualmente.
fuente
Vitsy , 16 bytes
Pruébalo en línea!
También podría agregar mi propia contribución a la mezcla. Esto es más corto que la solución de iteraciones de partición en Vitsy.
fuente
Oasis , 14 bytes
Pruébalo en línea!
¿Cómo?
Esta es una solución recursiva que incrementa el resultado cuando encuentra un índice triangular, comenzando con 0 para la entrada 0.
fuente
Perl 5
-p
, 19 (++) bytesPruébalo en línea!
fuente
Rubí , 27 bytes
Tres por el precio de uno. Estoy decepcionado de que no puedo ir más corto.
Pruébalo en línea! (para seleccionar la función, agregue f = delante de ella)
fuente