Encuentra el mayor número de enteros distintos que suman n

18

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 fdefinir 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));
    }
}

Pruébalo en línea!

Addison Crump
fuente
¿Se puede indexar a 0?
Totalmente humano el
1
@totallyhuman "it" siendo las respuestas? Porque no se trata de una lista ...
Addison Crump
3
@totallyhuman No. Se trata de las distintas particiones de números específicos.
Addison Crump
55
Este es OEIS A003056 .
Jeppe Stig Nielsen
44
Me siento insignificante cada vez que me tropiezo con la pila de codegolf. Las respuestas y los comentarios son mucho más que humildes. Las preguntas también suelen ser interesantes, pero con su comentario @JeppeStigNielsen solo arroja los planos completos cuando todavía estamos contemplando el área del piso.
KalleMP

Respuestas:

9

05AB1E , 4 bytes

ÅTg<

Pruébalo en línea!

Herramienta perfecta para el trabajo.

ÅTLos 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.

Sr. Xcoder
fuente
8

Gelatina , 6 5 bytes

R+\»ċ

Prué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:

        # Main link
R       # Range, generate [1..n]
 +\     # Cumulative sum (returns the first n triangular numbers)
   »    # For each element, return the maximum of that element and 'n'
    ċ   # How many elements are 'n'? (implicit right argument is n)
DJMcMayhem
fuente
En la explicación, seguramente quiere decir "cuántos números son menores o iguales que n "
Luis Mendo
@LuisMendo Vea la nueva explicación.
DJMcMayhem
6

Haskell , 26 bytes

-2 bytes gracias a H.PWiz.

(!!)$do x<-[0..];x<$[0..x]

Pruébalo en línea!

Esto devuelve el enésimo elemento de los números enteros donde cada i se replica i + 1 veces.

totalmente humano
fuente
3
No puedo evitar preguntar qué es "succ"
Addison Crump
Sí, lo sé jajaja. succrepresenta successor.
Totalmente humano el
5

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.

Nitrodon
fuente
3

Brain-Flak , 82 bytes

Espacio en blanco agregado para "Legibilidad"

(())

{
    {}

    ((({})[[]]))

    ([({}<(())>)](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}

}{}{}{}

([]<>)

Pruébalo en línea!

DJMcMayhem
fuente
1
¡Quién hubiera pensado que combinar dos idiomas ilegibles, Whitespace y Brain-Flak, podría considerarse "legible"!
caird coinheringaahing
3

R , 28 bytes

function(n)rep(1:n,1:n+1)[n]

Pruébalo en línea!

Crea el vector de tiempos 1repetidos 2, tiempos 2repetidos 3, ..., tiempos nrepetidos n+1y toma el nthelemento. Esto generará un error de memoria porque 1:nes demasiado grande o porque la lista repetida con n*(n+1)/2 - 1elementos es demasiado grande.

R , 29 bytes

function(n)((8*n+1)^.5-1)%/%2

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

function(n)sum(cumsum(1:n)<=n)

Pruébalo en línea!

Cuenta los números triangulares menores o iguales que n. Esto posiblemente provocará un error de memoria si 1:nes lo suficientemente grande, por ejemplo, 1e9arroja Error: cannot allocate vector of size 3.7 Gb.

Giuseppe
fuente
2

TI-Basic, 12 bytes

int(√(2Ans+1/4)-.5
Timtech
fuente
2

JavaScript (Node.js) , 18 bytes

x=>(x-~x)**.5-.5|0

Pruébalo en línea!

Unihedron
fuente
¿Es esto siempre correcto? No estoy seguro floor((sqrt(8x+4)-1)/2)(su fórmula) y floor((sqrt(8x+1)-1)/2)(fórmula correcta) dan el mismo resultado para todos x.
ETHproductions
@ETHproductions Podría farolear y decir "sí", pero creo que la respuesta más honesta es que debes tratar de desarrollar tu propia hipótesis y descubrir si / por qué refleja la misma fórmula. No se me ocurrió este enfoque por mí mismo (lo aprendí de un sitio diferente) pero jugué un poco con él. Es un enfoque muy interesante y no quiero diseccionar la rana tan temprano.
Unihedron
Hmm No estoy seguro de cómo probarlo directamente, pero escribí una fuerza bruta que no encuentra fallas por debajo de los 100 millones.
ETHproductions
2

Japt , 8 bytes

Solución de fórmula cerrada.

*8Ä ¬É z

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 .

õ å+ è§U

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).

Lanudo
fuente
2

Brain-Flak , 70 56 48 bytes

{([(({}[({}())()])[()])]<>){<>({}())}{}<>{}}<>{}

Prué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.

Asistente de trigo
fuente
1
Algo más de competencia
Nitrodon el
2

Pyth , 7 bytes

lh{I#./

Pruébalo en línea!

Filtrar-mantener las particiones enteras que son Ivariables sobre la deduplicación, agarrar el head 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.

Sr. Xcoder
fuente
2

Triangularidad , 49 bytes.

....)....
...2)2...
..)1/)8..
.)1/)IE/.
@^)1_+/i.

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:

)2)2)1/)8)1/)IE/@^)1_+/i | Input from STDIN and output to STDOUT.

)                        | Push a 0 onto the stack. Must precede integer literals.
 2                       | Push ToS * 10 + 2 (the literal 2, basically).
  )2                     | Again, push a 2 onto the stack. This can be replaced by D
                         | (duplicate), but then the padding would discard the saving.
    )1                   | Literal 1.
      /                  | Division. Push b / a (1 / 2).
       )8)1              | The literal 8 and the literal 1 (lots of these!).
           /             | Division. Push b / a (1 / 8).
            )IE          | Get the 0th input from STDIN and evaluate it.
               /         | Divide it by 1 / 8 (multiply by 8, but there isn't any
                         | operand for multiplication, and I'm not willing to add one).
                @        | Add 1 to the result.
                 ^       | Exponentiation. Here, it serves as a square too.
                  )1_+   | Decrement (add literal -1).
                      /  | Divide (by 2).
                       i | Cast to an integer.

Una solución alternativa, y más corta si el relleno no fuera necesario:

....)....
...2)1...
../DD)I..
.E/)4)1/.
+^s_+i...

Pruébalo en línea!

Sr. Xcoder
fuente
2

PowerShell 3.0, 45 bytes

[math]::Sqrt(2*$args[0]+.25)-.5-replace'\..*'

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.

Veskah
fuente
2

Java (JDK) , 28 bytes

n->~-(int)Math.sqrt(8*n+1)/2

Pruébalo en línea!

Debido a que el ejemplo realmente no estaba bien jugado: p

Créditos

Olivier Grégoire
fuente
1
28 bytes " Debido a que su código realmente no estaba bien "; p
Kevin Cruijssen
@KevinCruijssen Bueno, ahora lo es! : o
Olivier Grégoire
1

Jalea , 7 bytes

ŒPfŒṗṪL

Se ejecuta aproximadamente en O (2 n ) tiempo.

Pruébalo en línea!

Cómo funciona

ŒPfŒṗṪL  Main link. Argument: n

ŒP       Powerset; yield all subarrays of [1, ..., n], sorted by length.
   Œṗ    Yield all integer partitions of n.
  f      Filter; keep subarrays that are partitions.
     Ṫ   Tail; extract the last result.
      L  Compute its length.
Dennis
fuente
1

JavaScript (ES7), 22 19 bytes

n=>(8*n+1)**.5-1>>1

-3 bytes gracias a ETHproductions.


Intentalo

o.innerText=(f=
n=>(8*n+1)**.5-1>>1
)(i.value=1000000000);oninput=_=>o.innerText=f(+i.value)
<input id=i type=number><pre id=o>


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.

Lanudo
fuente
¿Puedes incluir una explicación? No he hecho Javascript en mucho tiempo
FantaC
¿Qué tal n=>(8*n+1)**.5-1>>1para guardar 3 bytes? (no lo he probado)
ETHproductions
Superé esto en JS: codegolf.stackexchange.com/a/152558/21830
Unihedron
@ETHproductions: parece que funciona, gracias.
Shaggy
@tfbninja, habría pensado t bastante explicativo, pero se agregó la explicación.
Shaggy
1

Python 2/3, 32 bytes

Implementación de Python de la fórmula de formulario cerrado

lambda n:int((sqrt(1+8*n)-1)//2)

La división entera se //2redondea hacia cero, por lo que no se floor( )requiere

Karl der Kaefer
fuente
1
Bienvenido a PPCG! ¿Esto necesita from math import sqrtfuncionar? Si es así, debe incluirse en el bytecount. (En ese caso lambda n:int((math.sqrt(1+8*n)-1)//2) import math es un poco más corto. )
Steadybox
29 bytes
FlipTack
Sí, necesita la importación para funcionar, por lo que debe incluirse en el recuento de bytes.
mbomb007
1

Haskell , 28 bytes

Es un poco aburrido, pero es bastante más corto que la otra solución de Haskell y tiene una expresión realmente agradable. Desafortunadamente no pude acortarlo sin que el sistema de tipos se interpusiera:

g x=floor$sqrt(2*x+0.25)-0.5

Pruébalo en línea!

Punto libre, 33 bytes

ceiling.(-0.5+).sqrt.(0.25+).(2*)

Alternativamente, 33 bytes

Misma longitud que la versión sin puntos, pero mucho más interesante.

g n=sum[1|x<-scanl1(+)[1..n],n>x]
ბიმო
fuente
¡Logré vincular la fórmula arreglando algunos errores tontos!
Totalmente humano el
@totallyhuman: Bien, ahora el tuyo también es mucho mejor :)
ბიმო
1

Vía Láctea , 12 bytes

'8*1+g1-2/v!

Explicación

code         explanation       value

'            push input        n          
 8*          push 8, multiply  8n
   1+        add 1             8n+1
     g       square root       sqrt(8n+1)
      1-     subtract 1        sqrt(8n+1)-1
        2/   divide by 2       (sqrt(8n+1)-1)/2
          v  floor             floor((sqrt(8n+1)-1)/2)
           ! output
ovs
fuente
1

Pyt , 7 5 bytes

Đř△>Ʃ

Explicación:

                      Implicit input
Đř△                   Gets a list of the first N triangle numbers
   >                  Is N greater than each element in the list? (returns an array of True/False)
    Ʃ                 Sums the list (autoconverts booleans to ints)



Más rápido, pero más largo

Pyt , 11 9 bytes

Đ2*√⌈ř△>Ʃ

Explicación:

Đ2*√⌈ř△           Gets a list of triangle numbers up to the ceiling(sqrt(2*N))-th
       >          Is N greater than each element of the list? (returns an array of True/False)
        Ʃ         Sums the array



Manera alternativa - puerto de la respuesta de Shaggy

Pyt , 8 7 bytes

8*⁺√⁻2÷
mudkip201
fuente
1

J , 11 bytes

2&!inv<.@-*

Pruébalo en línea!

2&!inv       solve [x choose 2 = input]
         -*  minus 1
      <.     and floor
FrownyFrog
fuente
Me gusta ese truco *para producir 1
Jonás
1

Espacio en blanco , 111 bytes

[S S S N
_Push_0][S N
S _Duplicate_0][T   N
T   T   _Read_integer_from_STDIN][T T   T   _Retrieve_input][S S S T    S S S N
_Push_8][T  S S N
_Multiply][S S S T  N
_Push_1][T  S S S _Add][S S T   T   N
_Push_n=-1][N
S S N
_Create_Label_SQRT_LOOP][S S S T    N
_Push_1][T  S S S _Add][S N
S _Duplicate_n][S N
S _Duplicate_n][T   S S N
Multiply][S T   S S T   S N
_Copy_0-based_2nd_(the_input)][S S S T  N
_Push_1][T  S S S _Add][T   S S T   _Subtract][N
T   T   N
_If_negative_jump_to_Label_SQRT_LOOP][S S S T   S N
_Push_2][T  S S T   _Subtract][S S S T  S N
_Push_2][T  S T S _Integer_divide][T    N
S T _Print_integer]

Se agregaron letras S(espacio), T(tabulación) y N(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:

Fnorte=8norte+1-12

NOTA: El espacio en blanco no tiene una raíz cuadrada incorporada, por lo que debemos hacerlo manualmente.

Integer i = read STDIN as integer
i = i * 8 + 1
Integer n = -1
Start SQRT_LOOP:
  n = n + 1
  If(n*n < i+1):
    Go to next iteration of SQRT_LOOP
n = (n - 2) integer-divided by 2
Print n as integer to STDOUT
Kevin Cruijssen
fuente
0

Vitsy , 16 bytes

2*14/+12/^12/-_N

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.

Addison Crump
fuente
0

Oasis , 14 bytes

n8*1+1tm1%_b+0

Pruébalo en línea!

¿Cómo?

n8*1+           8n + 1
     1tm        sqrt
        1%_     integer?
           b+   add f(n-1)

             0  f(0) is 0

Esta es una solución recursiva que incrementa el resultado cuando encuentra un índice triangular, comenzando con 0 para la entrada 0.

Uriel
fuente
0

Rubí , 27 bytes

Tres por el precio de uno. Estoy decepcionado de que no puedo ir más corto.

->n{a=0;n-=a+=1while n>a;a}
->n{((8*n+1)**0.5-1).div 2}
->n{((n-~n)**0.5-0.5).to_i}

Pruébalo en línea! (para seleccionar la función, agregue f = delante de ella)

Unihedron
fuente