Najbliższe numery partycji

12

Liczba partycji liczby całkowitej jest liczbą sposobów, w jakie liczba całkowita może być reprezentowana jako suma liczb całkowitych dodatnich.

Na przykład:

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

Istnieje 7 sposobów przedstawienia liczby 5, dlatego 7 jest numerem podziału odpowiadającym liczbie 5.

Numery partycji: OEIS: # A000041

Kierunki

Napisz program, który przyjmuje na wejściu dodatnią liczbę całkowitą i wypisuje dwie liczby, które generują dwie najbliższe liczby partycji do liczby wejściowej.

  • Dane wejściowe muszą być 1 dodatnią liczbą całkowitą.
  • Jeśli wejście nie jest numerem partycji, wyjściem muszą być 2 różne liczby całkowite dodatnie, które generują dwa numery najbliższe partycji do numeru wejścia. (Jeśli dwa numery partycji są równymi kandydatami na jedną z liczb wyjściowych, nie ma znaczenia, który wybierzesz.)
  • Jeśli wejście jest numerem partycji, wyjściem musi być 1 dodatnia liczba całkowita, która generuje numer wejścia.
  • Dane wejściowe i wyjściowe mogą być w dowolnym rozsądnym formacie.
  • Możesz założyć, że dane wejściowe nie będą większe niż 100 milionów (np. Dane wyjściowe nigdy nie będą większe niż 95).
  • Wbudowane funkcje do obliczania liczb działowe są nie dozwolone, wraz z innymi standardowymi otworami strzelniczymi .
  • To jest golf golfowy , więc wygrywa najmniejsza liczba bajtów.

Numery partycji: OEIS: # A000041

Przykłady

Input: 66
Output: 11, 12

(Numery podziału odpowiadające liczbom 11 i 12 to 56 i 77, które są dwoma najbliższymi numerami podziału od 66.)

Input: 42
Output: 10

(Liczba 42 jest już numerem partycji, więc po prostu wypisz numer, który odpowiada numerowi partycji).

Input: 136
Output: 13, 14

(Dwie najbliższe liczby partycji do 136 są w rzeczywistości MNIEJSZE niż 136 (np. 101 i 135), dlatego dane wyjściowe wynoszą 13 i 14, a nie 14 i 15.)

Input: 1
Output: 0   or   1

(Zarówno 0, jak i 1 są poprawnymi danymi wyjściowymi w tym specjalnym przypadku.)

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

(Oba z tych wyjść jest ważny, ponieważ 2484 jest równa d i stanowisko od 1958 i 3010.)

Input: 4
Output: 3, 4

(Tak)

code-golf number-theory integer-partitions kukac67
źródło
Nie zdefiniowałeś, jaki jest numer partycji
dumny haskeller
@proudhaskeller Numery partycji to numery w połączonej sekwencji OEIS. Wyjaśnienie, dla którego numeru partycji 5jest na górze. (Dodam wyjaśnienie, jeśli uważasz, że nie jest wystarczająco jasne.)
kukac67,
1
Jest to bardzo bliskie bycia duplikatem tego wcześniejszego pytania dotyczącego partycji .
Peter Taylor,

Odpowiedzi:

2

Pyth , 53

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

Wyjaśnienie i więcej golfa do naśladowania.

isaacg
źródło
4

Python 2, 179 bajtów

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

Wykorzystuje rekurencyjną formułę z pięciokątnego twierdzenia Eulera .

Zadzwoń z f(2484). Dane wyjściowe to krotka z jedną lub dwiema liczbami.

Sp3000
źródło
2

Mathematica, 124 123 bajty

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

Wzór na numery partycji pobrane ze strony OEIS . (Może lub nie oszukuje ... Nie mogłem się zdecydować.)

Stosowanie:

In: f[136]

Out: {14, 13}

Nie odpowiadam na wygraną. I jestem pewien, że można by dalej grać w golfa.

kukac67
źródło