Diberi angka n> 77 , tulis sebuah program atau fungsi yang menemukan satu set bilangan bulat positif yang berbeda sehingga jumlah himpunan sama dengan n , dan jumlah kebalikan dari himpunan sama dengan 1.

Contoh untuk 80:

80 = 2 + 4 + 10 + 15 + 21 + 28 ⟶ 1/2 + 1/4 + 1/10 + 1/15 + 1/21 + 1/28 = 1

Program atau fungsi Anda harus (secara teoritis) bekerja untuk n <2 ³² , dan tidak diizinkan untuk kesalahan pembulatan titik mengambang. Perhatikan bahwa solusi ada untuk semua n> 77 .

Kode terpendek dalam byte menang.

Ada insentif bonus: Saya akan memberikan hadiah untuk solusi terkecil yang bekerja untuk semua n dan menjalankan log (n) . Untuk n kecil harus cepat (ditentukan atas kebijaksanaan saya). Ya, ini mungkin.

Mathematica, 54 byte

Select[IntegerPartitions@#,Unequal@@#&&Tr[1/#]==1&,1]&

Tentang tidak efisien karena mendapat, tetapi itu menyelesaikan n = 78dalam waktu sekitar 9 detik.

Hasilnya dikembalikan sebagai daftar yang dibungkus dalam daftar tunggal, misalnya:

{{45, 12, 9, 5, 4, 3}}

Python 3, 7306 1995 Bytes

Solusi ini berjalan dalam kompleksitas log (n) (sejauh yang saya tahu).

def i(s,t):
 for n in s[::-1]:t=t.replace(*n)
 return [[]]*78+[list(bytearray.fromhex(a))for a in t.split(",")]
def f(n):
 g,h=lambda c,n:c+[[[2],[3,7,78,91]][n[len(c)]%2]+[i*2for i in c[-1]]],lambda n:[]if n<78 else h((n-[2,179][n%2])//2)+[n]
 v=h(n);c=[i([['g',',03040'],['h',',,0306080'],['i',',020'],['j','b0c1'],['k','21'],['l','60'],['m','30'],['n','141'],['o','k24'],['p',',g'],['q','618'],['r','0c0'],['s','1e'],['t',',0ml'],['u','283c'],['v','e0f1'],['w','2a38'],['x','80'],['y','a0'],['z','01'],['A','50'],['B','24'],['C','i40'],['D','plb1'],['E','gl'],['F','48'],['G','bre1'],['H','28'],['I','6k'],['J','416s'],['K',',040Al'],['L','90'],['M','2a'],['N','54'],['O','k6o'],['P','3c'],['Q','il'],['R','18'],['S','px'],['T','im'],['U','70'],['V','b1'],['W','23'],['X','pj'],['Y','hj'],['Z','0n']],'020lxycHTaRHCyf1517CyfneC91k51cCLdneQU912MCyf0dBiALyf2dClfPEyfneT9s2dELdneEjIgmLydHg5rd14BKLardsE3n8sQ9rd1517Q9rdneplmdRBgUmcRMC5sPEyf102bgA6sPE91z2miAj41IQmc0dRBQUen7spl31z82bT9RFT3wE7neMgmyf0dRBgUmaHMELc1b36EUdBMQLyfs2d,C710M2bgLardRHT3BFQ9rf0dPQ7rdBMQm9Rs2d,0mAl9100d142bE710M2bQmc0fRPtxarfn8sEc1k4sBTfnePExcwtxarf1k8BExcuT3kkT91663C51964,0mAl71k4BMELe12NTcRwQjOT820ltmarf1z8mExeRNCqBFtmyjIHKLa100ds2bQU91bM36garf1k4sBTcRBFgxarfwE91keB2dtUxcn8sME9nbs36gm9rduC5R78,0mAUyf0d14BME91kbB36QLc12AB2dgyjqkHEUeMNT9157eQU9RMFT8s78C8neuixLc1zk4AtUxc1z8Mmt8re0fn8sWhLyc1bH36pl8neu,Kxycsw,iAxc1420l,K8ren8NS9n81bs36hc0vz8WmYzqkmhyv2WBHhyVOHXkJoSjIwSjIuSvz4WASVZIAXZ6skmSj6oFXzOmplvcsW46D61csk46plv8WBFDqoF,tarvk8WBH,tyjkqoHhGqkN,tmvZ8sWmhVZqskmpc0vZ8WAXZqkAplbnImASbn6skwSbn6skuSVOwSVOupGONSbn6soFpyVkJk5aSj6sk78YJkuDkIP5aYOuhvzk4WBAhVzk416oA,tyjkJ265a,,0mxyjk41q53sYzIHmPXkqowXkqouhyVqoHFYz6omFhb0e1zqkmNSyVIP78YJ20klpyVOHwYk620olpc0vz8WBmFXzqomFpG61ckH38PhyjIP78Yz620kmlDkImLDzINUhGIuNDzIA78hb0e1ZIANYkqk366chG6oFNXkJkP5ahVZ6somFSb0e1620kNlhVk41qomADzIFLXkqso78pGqoFNXzkImP5a,tyjk620oHlhG620kNlXzqskm78,tjZqskHmPYqouFD6sku78YzqkNU,tjZqsomF')[v[0]]]
 for o in range(len(v)-1):c=g(c,v)
 return c[-1]

Anda dapat menguji yang f(2**32 - 1)berjalan hampir secara instan

Saya menggunakan makalah ini pada metode untuk menghitungnya. Dengan metode ini ada sejumlah besar data untuk nilai yang ditentukan sebelumnya untuk n dari 78 menjadi 334 tanpa angka genap setelah 168. Saya ingin mengubah data ini menjadi sesuatu yang kecil dan saya tidak tahu algoritma kompresi yang baik jadi saya membuat saya sendiri.

Cara saya mengompresnya adalah dengan memiliki daftar aturan ganti string. Saya membuat metode yang menemukan aturan ganti string yang akan mengurangi sebagian besar konten dengan mempertimbangkan mendefinisikan aturan. Saya kemudian menerapkan ini secara rekursif sampai saya tidak dapat membuat aturan lagi (saya menggunakan karakter gz dan AZ). String yang saya buat untuk diganti adalah daftar nilai hex yang dipisahkan koma untuk masing-masing angka. Dalam retrospeksi, mengonversikannya ke nilai hex mereka mungkin bukan pilihan yang paling bijaksana, mungkin akan lebih pendek untuk membiarkannya dalam desimal, karena memiliki hex hanya akan menyimpan untuk angka 3 digit tetapi akan menambahkan 0 untuk angka digit tunggal.

Baris tempat saya atur c Anda dapat melihat daftar aturan ganti dan teks yang menjalankannya. Aturan perlu diterapkan secara terbalik juga karena beberapa aturan menyertakan karakter yang dibuat dari aturan lain.

Ada juga banyak tempat dalam kode ini di mana saya mungkin bisa mengurangi sintaksis, seperti mengubah daftar daftar menjadi satu daftar dan kemudian menggunakan metode berbeda untuk mengakses aturan mengganti teks dengan

Haskell, 93 byte

import Data.List
import Data.Ratio
p n=[x|x<-subsequences[2..n],sum x==n,1==sum(map(1%)x)]!!0

^{1 sangat} lambat tetapi berjalan dalam memori konstan. Solusi sepele: periksa semua urutan [2..n]untuk jumlah dan jumlah timbal balik.

Mengembalikan semua solusi alih-alih satu adalah 3 byte lebih pendek: hapus saja !!0(waspadalah: waktu berjalan akan selalu keluar dari grafik).

¹ Waktu berjalan tergantung pada seberapa awal hasilnya muncul dalam daftar berikutnya. Kemalasan Haskell menghentikan pencarian jika kecocokan pertama ditemukan. Ketika dikompilasi, p 89(hasil [3,4,6,9,18,21,28]:) berjalan di laptop (4 tahun) saya di usia 35-an. Nilai-nilai lain, bahkan yang lebih kecil, bisa memakan waktu berjam-jam.

Julia, 77 byte

n->collect(filter(i->i==∪(i)&&sum(j->Rational(1,j),i)==1,partitions(n)))[1]

Ini adalah fungsi lambda yang tidak efisien yang menerima integer dan mengembalikan array integer. Untuk menyebutnya, tetapkan ke variabel.

Kami mendapatkan partisi menggunakan integer partitions. Kami kemudian memfilter sekumpulan partisi hanya untuk mereka yang memiliki elemen unik yang jumlah balasannya menjadi 1. Untuk memastikan tidak ada kesalahan pembulatan, kami menggunakan Rationaltipe Julia untuk membuat resiprokal. filtermengembalikan sebuah iterator, jadi kita harus collectmengubahnya menjadi sebuah array. Ini memberi kita array array (hanya dengan satu elemen), jadi kita bisa menggunakan yang pertama [1].

Sekarang, ketika saya mengatakan tidak efisien, saya sungguh-sungguh. Menjalankan ini untuk n = 80 membutuhkan 39,113 detik di komputer saya dan mengalokasikan 13,759 GB memori.