Números de partição mais próximos

12

O número de partições de um número inteiro é o número de maneiras pelas quais o número inteiro pode ser representado como uma soma de números inteiros positivos.

Por exemplo:

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

Existem 7 maneiras de representar o número 5, portanto 7 é o número da partição correspondente ao número 5.

Números da partição: OEIS: # A000041

instruções

Escreva um programa que use um número inteiro positivo como entrada e emita os dois números que geram os dois números de partição mais próximos para o número de entrada.

  • A entrada deve ser 1 número inteiro positivo.
  • Se a entrada não for um número de partição, a saída deverá ser os 2 números inteiros positivos diferentes que geram os dois números de partição mais próximos do número de entrada. (Se dois números de partição são candidatos iguais a um dos números de saída, não importa qual deles você escolher.)
  • Se a entrada for um número de partição, a saída deverá ser 1 número inteiro positivo que gere o número de entrada.
  • A entrada e a saída podem estar em qualquer formato razoável.
  • Você pode assumir que a entrada não será maior que 100 milhões (por exemplo, a saída nunca será maior que 95).
  • Funções internas para calcular números de partição não são permitidas, juntamente com outras brechas padrão .
  • Isso é , portanto, o menor número de bytes vence.

Números da partição: OEIS: # A000041

Exemplos

Input: 66
Output: 11, 12

(Os números da partição que correspondem aos números 11 e 12 são 56 e 77, que são os dois números de partição mais próximos de 66.)

Input: 42
Output: 10

(O número 42 já é um número de partição, portanto, basta gerar o número que corresponde ao número da partição.)

Input: 136
Output: 13, 14

(Os dois números de partição mais próximos de 136 são, na verdade, MENOS que 136 (por exemplo, 101 e 135); portanto, a saída é 13 e 14, em oposição a 14 e 15.)

Input: 1
Output: 0   or   1

(0 e 1 são saídas válidas neste caso especial.)

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

(Ambas as saídas são válidas, porque 2484 é igual d i postura entre 1958 e 3010.)

Input: 4
Output: 3, 4

(Sim)

kukac67
fonte
Você não definiu o que é um número de partição
proud haskeller
@proudhaskeller Os números de partição são os números que estão na sequência OEIS vinculada. A explicação para qual é o número da partição 5está no topo. (Vou acrescentar esclarecimentos se você acha que não é clara o suficiente.)
kukac67
1
Isso está muito perto de ser um engodo dessa questão de partição anterior .
Peter Taylor

Respostas:

2

Pyth , 53

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

Explicação e mais golfe a seguir.

isaacg
fonte
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)]

Usa a fórmula recursiva do teorema pentagonal de Euler .

Ligue com f(2484). A saída é uma tupla com um ou dois números.

Sp3000
fonte
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 números de partição extraídos da página OEIS . (Pode ou não estar trapaceando ... não consegui decidir.)

Uso:

In: f[136]

Out: {14, 13}

Eu não estou respondendo para ganhar. E tenho certeza de que isso poderia ser ainda mais jogado.

kukac67
fonte