Nomor partisi terdekat

12

Jumlah partisi integer adalah jumlah cara integer dapat direpresentasikan sebagai jumlah bilangan bulat positif.

Sebagai contoh:

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

Ada 7 cara untuk mewakili angka 5, oleh karena itu 7 adalah nomor partisi yang sesuai dengan angka 5.

Nomor partisi: OEIS: # A000041

Petunjuk arah

Tulis sebuah program yang mengambil bilangan bulat positif sebagai input, dan output dua angka yang menghasilkan dua nomor partisi terdekat dengan nomor input.

  • Input harus 1 bilangan bulat positif.
  • Jika input bukan nomor partisi, output harus berupa 2 bilangan bulat positif berbeda yang menghasilkan dua nomor partisi terdekat dengan nomor input. (Jika dua nomor partisi adalah kandidat yang sama untuk salah satu nomor output, tidak masalah yang mana yang Anda pilih.)
  • Jika input adalah nomor partisi, output harus 1 bilangan bulat positif yang menghasilkan nomor input.
  • Input dan output mungkin dalam format yang masuk akal.
  • Anda dapat mengasumsikan bahwa input tidak akan lebih besar dari 100 juta (mis. Output tidak akan pernah lebih besar dari 95).
  • Fungsi bawaan untuk menghitung nomor partisi tidak diperbolehkan, bersama dengan celah Standar lainnya .
  • Ini adalah kode-golf , jadi paling tidak jumlah byte yang menang.

Nomor partisi: OEIS: # A000041

Contohnya

Input: 66
Output: 11, 12

(Nomor partisi yang sesuai dengan angka 11 dan 12 adalah 56 dan 77, yang merupakan dua nomor partisi terdekat dengan 66.)

Input: 42
Output: 10

(Angka 42 sudah merupakan nomor partisi, jadi cukup masukkan angka yang sesuai dengan nomor partisi.)

Input: 136
Output: 13, 14

(Dua nomor partisi terdekat dengan 136 sebenarnya KURANG dari 136 (mis. 101 dan 135), oleh karena itu outputnya adalah 13 dan 14 dibandingkan dengan 14 dan 15.)

Input: 1
Output: 0   or   1

(Baik 0 dan 1 adalah output yang valid dalam kasus khusus ini.)

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

(Kedua output ini valid, karena 2484 sama dengan saya dari tahun 1958 dan 3010.)

Input: 4
Output: 3, 4

(Ya)

code-golf number-theory integer-partitions kukac67
sumber
Anda tidak menentukan apa nomor partisi
haskeller bangga
@proudhaskeller Nomor partisi adalah angka yang ada dalam urutan OEIS yang ditautkan. Penjelasan untuk apa nomor partisi 5adalah di bagian atas. (Saya akan menambahkan klarifikasi jika Anda pikir itu tidak cukup jelas.)
kukac67
1
Ini hampir menjadi dupe dari pertanyaan partisi sebelumnya .
Peter Taylor

Jawaban:

2

Pyth , 53

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

Penjelasan dan lebih banyak golf untuk diikuti.

isaacg
sumber
4

Python 2, 179 byte

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

Menggunakan rumus rekursif dari teorema pentagonal Euler .

Panggil dengan f(2484). Output adalah tupel dengan satu atau dua angka.

Sp3000
sumber
2

Mathematica, 124 123 byte

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

Formula untuk nomor partisi yang diambil dari halaman OEIS . (Mungkin atau mungkin tidak curang ... Saya tidak bisa memutuskan.)

Pemakaian:

In: f[136]

Out: {14, 13}

Saya tidak menjawab untuk menang. Dan saya yakin ini bisa bermain golf lebih lanjut.

kukac67
sumber