Números de partición más cercanos

12

El número de particiones de un entero es el número de formas en que ese entero se puede representar como una suma de enteros positivos.

Por ejemplo:

5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

Hay 7 formas de representar el número 5, por lo tanto, 7 es el número de partición correspondiente al número 5.

Números de partición: OEIS: # A000041

Direcciones

Escriba un programa que tome un entero positivo como entrada y genere los dos números que generan los dos números de partición más cercanos al número de entrada.

  • La entrada debe ser 1 entero positivo.
  • Si la entrada no es un número de partición, la salida debe ser los 2 enteros positivos diferentes que generan los dos números de partición más cercanos al número de entrada. (Si dos números de partición son candidatos iguales para uno de los números de salida, no importa cuál elija).
  • Si la entrada es un número de partición, la salida debe ser 1 entero positivo que genere el número de entrada.
  • La entrada y la salida pueden estar en cualquier formato razonable.
  • Puede suponer que la entrada no será mayor que 100 millones (por ejemplo, la salida nunca será mayor que 95).
  • Las funciones incorporadas para calcular los números de partición no están permitidas, junto con otras lagunas estándar .
  • Este es el código de golf , por lo que gana el menor número de bytes.

Números de partición: OEIS: # A000041

Ejemplos

Input: 66
Output: 11, 12

(Los números de partición que corresponden a los números 11 y 12 son 56 y 77, que son los dos números de partición más cercanos a 66.)

Input: 42
Output: 10

(El número 42 ya es un número de partición, por lo tanto, simplemente envíe el número que corresponde al número de partición).

Input: 136
Output: 13, 14

(Los dos números de partición más cercanos a 136 son en realidad MENOS que 136 (por ejemplo, 101 y 135), por lo tanto, la salida es 13 y 14 en lugar de 14 y 15.)

Input: 1
Output: 0   or   1

(Tanto 0 como 1 son salidas válidas en este caso especial).

Input: 2484
Output: 26, 25   or   26, 27

(Ambos de estas salidas son válidas, porque 2484 es igual d i postura de 1958 y 3010.)

Input: 4
Output: 3, 4

(Sip)

code-golf number-theory integer-partitions kukac67
fuente
No
definiste
@proudhaskeller Los números de partición son los números que están vinculados en la secuencia OEIS. La explicación de cuál es el número de partición 5está en la parte superior. (Voy a añadir una aclaración si usted piensa que no es lo suficientemente claro.)
kukac67
1
Esto está muy cerca de ser un engaño de esta pregunta de partición anterior .
Peter Taylor

Respuestas:

2

Pyth , 53

L?!b<b1sm&d*^_1tdy-b/*dt*3d2r_bhbJo^-QyN2U99<J-2qQyhJ

Explicación y más golf para seguir.

isaacg
fuente
4

Python 2, 179 bytes

Z=range(1,99)
R=Z+[1]
for i in Z:R[i]=sum(-(-1)**k*(3*k*k-k<=i*2and R[i-k*(3*k-1)/2])for k in range(-i,i+1)if k)
f=lambda n:zip(*sorted((abs(n-R[i]),i)for i in Z))[1][:2-(n in R)]

Utiliza la fórmula recursiva del teorema pentagonal de Euler .

Llamada con f(2484). La salida es una tupla con uno o dos números.

Sp3000
fuente
2

Mathematica, 124 123 bytes

f@n_:=(p=SeriesCoefficient[1/Product[1-x^k,{k,#}],{x,0,#}]&;s=SortBy[Range@95,Abs[n-p@#]&];If[p@s[[1]]==n,s[[1]],s~Take~2])

Fórmula para los números de partición tomados de la página OEIS . (Puede o no estar engañando ... no pude decidir).

Uso:

In: f[136]

Out: {14, 13}

No estoy respondiendo para ganar. Y estoy seguro de que esto podría jugar más golf.

kukac67
fuente