Melihat ada banyak sekali tantangan Fibonacci normal, saya memutuskan bahwa mungkin menarik untuk menghitung konstanta Fibonacci Reciprocal - yaitu, jumlah kebalikan dari urutan Fibonacci.

Tantangannya adalah untuk menghitung konstanta Fibonacci Reciprocal dengan jumlah seri Fibonacci untuk menggunakan digit yang diberikan sebagai input, yaitu input 10 berarti menghitung berdasarkan pada kebalikan dari 10 angka Fibonacci pertama. Dalam kasus kemungkinan seri, kode terpendek menang.

Pemenang akan dipilih dalam tiga minggu melalui aturan standar kode-golf.

K (19)

(atau 17 jika Anda melewatkan mendefinisikannya sebagai fungsi)

f:{+/*+%x(|+\)\|!2}

Diuji pada Kona.

Pada dasarnya, ini menghasilkan nilai x pertama dari urutan fibonacci ke dalam array (tanpa menggunakan builtin), membagi 1 dengan setiap nilai dari seluruh array, mentranspos dan menjumlahkannya.

(terima kasih kepada @tmartin untuk metode penjumlahan yang lebih baik)

Perl - 35 byte

print!map$\-=1/($%+=$.=$%-$.),0..<>

Penggunaan sampel:

$ echo 10 | perl inv-fib-sum.pl
3.34170499581934

Analisis lebih lanjut

Sangat menarik untuk dicatat bahwa jumlahnya

konvergen. Andaikata kita ingin menghitung beberapa ribu digit atau lebih, pendekatan naif itu hampir mencukupi. Konvergensi pada awalnya cukup lambat, tetapi mempercepat dengan cepat, sehingga 1000 digit hanya membutuhkan sekitar 4800 istilah. Contoh implementasi Python mungkin:

a=[1,1]
for i in range(4800):a=[a[0]+a[1]]+a
z=10**1000
print sum(map(lambda i:z/i,a))

yang setelah satu atau dua keluaran:

33598856662431775531720113029189271796889051337319684864955538153251303189966833836154162164567900872970453429288539133041367890171008836795913517330771190785803335503325077531875998504871797778970060395645092153758927752656733540240331694417992939346109926262579646476518686594497102165589843608814726932495910794738736733785233268774997627277579468536769185419814676687429987673820969139012177220244052081510942649349513745416672789553444707777758478025963407690748474155579104200675015203410705335285129792635242062267537568055761955669720848843854407983324292851368070827522662579751188646464096737461572387236295562053612203024635409252678424224347036310363201466298040249015578724456176000319551987905969942029178866949174808096746523682654086938399069873211752166957063859411814553647364268782462926166650100098903804823359519893146150108288726392887669917149304053057745574321561167298985617729731395370735291966884327898022165047585028091806291002444277017460241040417786069190065037142832933

(Empat digit terakhir tidak cukup konvergen, tapi kami akan mengabaikannya untuk saat ini.)

Mari kita coba sedikit mempercepat konvergensi. Trik standar adalah dengan menggunakan Transform Euler . Setelah ekspansi dan penyederhanaan, ini menghasilkan hasil yang lebih bagus:

Seharusnya cukup jelas mengapa ini bertemu lebih cepat; setiap istilah memiliki 3 istilah dalam penyebut daripada hanya satu. Menghitung 1000 digit hanya membutuhkan istilah 1600 (sepertiga lebih banyak):

a=[1,1]
for i in range(1601):a=[a[0]+a[1]]+a
z=10**1000
print sum(map(lambda i:(-1)**i*z/(a[i]*a[i+1]*a[i+2]),range(1601)))

Keluaran:

3598856662431775531720113029189271796889051337319684864955538153251303189966833836154162164567900872970453429288539133041367890171008836795913517330771190785803335503325077531875998504871797778970060395645092153758927752656733540240331694417992939346109926262579646476518686594497102165589843608814726932495910794738736733785233268774997627277579468536769185419814676687429987673820969139012177220244052081510942649349513745416672789553444707777758478025963407690748474155579104200675015203410705335285129792635242062267537568055761955669720848843854407983324292851368070827522662579751188646464096737461572387236295562053612203024635409252678424224347036310363201466298040249015578724456176000319551987905969942029178866949174808096746523682654086938399069873211752166957063859411814553647364268782462926166650100098903804823359519893146150108288726392887669917149304053057745574321561167298985617729731395370735291966884327898022165047585028091806291002444277017460241040417786069190065037142834500

(Di sini lagi, 4 digit terakhir tidak bertemu.)

Kami belum selesai. Jika kami menggabungkan istilah yang berdekatan, kami berakhir dengan yang berikut:

Anjak setiap istilah dari sisa penjumlahan memberikan ekspresi bersarang:

Sekarang kita pergi ke suatu tempat. Perhatikan bahwa pembilang dari mengikuti OEIS A206351 (dengan pengecualian dari istilah pertama, yang dua kali lipat):

dan penyebutnya mengikuti OEIS A081016 (digeser satu istilah):

Masing-masing memiliki hubungan perulangan yang sangat sederhana, yaitu:

dan

masing-masing. Menyatukan semuanya, kami menemukan bahwa kami hanya membutuhkan 800 iterasi untuk 1000 digit:

b,c=[16,3,1],[273,40,3]
for i in range(800):b,c=[7*b[0]-b[1]-4]+b,[7*c[0]-c[1]-1]+c
s=z=10**1000
for x,y in zip(b,c):s=(z+s)*x/y
print s

yang keluaran:

3598856662431775531720113029189271796889051337319684864955538153251303189966833836154162164567900872970453429288539133041367890171008836795913517330771190785803335503325077531875998504871797778970060395645092153758927752656733540240331694417992939346109926262579646476518686594497102165589843608814726932495910794738736733785233268774997627277579468536769185419814676687429987673820969139012177220244052081510942649349513745416672789553444707777758478025963407690748474155579104200675015203410705335285129792635242062267537568055761955669720848843854407983324292851368070827522662579751188646464096737461572387236295562053612203024635409252678424224347036310363201466298040249015578724456176000319551987905969942029178866949174808096746523682654086938399069873211752166957063859411814553647364268782462926166650100098903804823359519893146150108288726392887669917149304053057745574321561167298985617729731395370735291966884327898022165047585028091806291002444277017460241040417786069190065037142835294

(Di sini, akhirnya, 4 digit terakhir bertemu dengan benar.)

Tapi itu masih belum semuanya. Jika kita mengamati nilai-nilai perantara untuk s , kami menemukan bahwa nilai itu konvergen ke nilai yang berbeda sepenuhnya sebelum konvergen pada titik konvergensi yang sebenarnya. Alasan untuk ini adalah sebagai berikut:

Pemecahan untuk stabil s , kita menemukan bahwa:

Karena ini adalah root sederhana, kita dapat menggunakan Metode Newton untuk membawa kita ke sebagian besar jalan ke sana, dan kemudian melompat pada titik yang jauh lebih belakangan dalam iterasi. Hanya diperlukan sekitar 400 digit presisi (karena nilai b dan c tidak lebih besar dari itu), yang dapat dicapai hanya dengan 7 iterasi, sekaligus menghemat 320 iterasi dari loop utama:

b,c=[16,3,1],[273,40,3]
for i in range(480):b,c=[7*b[0]-b[1]-4]+b,[7*c[0]-c[1]-1]+c
z=10**1000;s=z/17
for i in range(7):s-=(s*s+s*z-z*z/16)/(2*s+z)
for x,y in zip(b,c):s=(z+s)*x/y
print s

Output identik dengan yang sebelumnya, runtime sekitar 0,02s pada sistem saya menggunakan PyPy v2.1. Meskipun perlu sepersepuluh jumlah iterasi seperti aslinya, ini jauh lebih cepat dari 10x karena mengalikan dan membaginya dengan istilah yang jauh lebih kecil. Saya tidak berpikir banyak yang bisa diubah, meskipun saya akan senang ditampilkan salah.

Mathematica (32 karakter tanpa Fibonacci bawaan)

Tr[1/⌈(.5+√5/2)^Range@#/√5-.5⌉]&

Di sini saya menggunakan rumus pembulatan untuk angka Fibonacci

di mana φrasio emas.

Kona ( 25 21)

{+/%(x(|+\)\1 1)[;1]}

Mungkin bisa dibuat lebih kecil oleh para ahli, tetapi saya masih belajar bahasa.

  f 10
3.341705
  f 3
2.8333
  f 25
3.359872
  f 400
3.359886

Yang terakhir sebenarnya tidak membutuhkan waktu lebih lama daripada yang lain.

Mathematica 30 24

Dengan 6 karakter tersimpan, terima kasih kepada ybeltukov.

 Tr[1/Fibonacci@Range@#]&

Sebelum menambahkan persyaratan:

1/Fibonacci@Range@#&[20]

Dengan tambahan termasuk:

 Tr[1/Fibonacci@Range@#]&[20]

APL, 21 karakter / byte *

{+/÷{↑+\∘⌽⍣⍵⊢0 1}¨⍳⍵}

Contoh

      {+/÷{↑+\∘⌽⍣⍵⊢0 1}¨⍳⍵} 10
3.330469041
      ⍪{+/÷{↑+\∘⌽⍣⍵⊢0 1}¨⍳⍵}¨⍳10
1          
2          
2.5        
2.833333333
3.033333333
3.158333333
3.23525641 
3.282875458
3.312287223
3.330469041
      {+/÷{↑+\∘⌽⍣⍵⊢0 1}¨⍳⍵} 100
3.359885666

⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
^{*: APL dapat ditulis dalam charset byte tunggal (lama) yang memetakan simbol APL ke nilai 128 byte atas. Oleh karena itu, untuk tujuan penilaian, program karakter N yang hanya menggunakan karakter ASCII dan simbol APL dapat dianggap sebagai panjang N byte.}

Javascript, 33

Memasukkan: n = 10

s=f=t=1;for(;n--;)t+=1/(s+=f=s-f)

Berbasis di posting pertama saya di Perl, ini adalah hasil langsung dari Google Chrome Console .

K, 22

...

{+/%x#x{x,+/-2#x}/1 1}

GTB , 35

Berjalan pada kalkulator TI-84

1→Y:0→X`N4;N,1,N~1/X:Y→Z:X+Y→Y:Z→X&

• Simpan 1di Ydan 0diX
• Ambil Nsebagai masukan
• Inisialisasi Forloop
• Tampilan X
• Simpan Ydi Zdan X+YdiY
• Simpan ZdiX
• Akhiri Forloop

BC - 116

define f(n){if(n < 2){return n;}else{return f(n-1)+f(n-2);}}
define r(n){for(i=1;i<n;++i){m=m+(1/f(i));};return m;}

panggil r (n) dengan n untuk menyelesaikannya. Ketepatan dapat diatur secara sewenang-wenang, jadi ini adalah solusi paling akurat.

PERL, 62 43

$s=$t=1;$t+=1/($a=$f+$s),$f=$s,$s=$a,for 0..<>;say $t

Edit:

Setelah beberapa waktu melihat kode saya, saya dapat menyimpan 19 karakter:

$s=1;$t+=1/($s+=$f=$s-$f)for 0..<>;say $t+2

input: 10
> 3.35294128575734

Keempat, 64

: r 1 1 rot 1e 0 do 2dup - nip tuck + dup s>f 1/f f+ swap loop ;

pemakaian:

10 r f. 3.34170499581934  ok
100 r f. 3.35988566624318  ok
1000 r f. 3.35988566624318  ok

Python ( 55 51)

i,r=p=1,1
while i<n+1:r+=1./p[-1];p=p[1],sum(p);i+=1
r

i,r,a,b=[1]*4
while i<n+1:r+=1./b;a,b=b,b+a;i+=1
r

Dalam mode interaktif:

n=10
3.341704995819338

n=100

3.3598856429940778

3.359885666243178

n=400

3.3598855578800064

3.359885666243178

Perl 6 , 27 byte

{sum 1 X/(1,&[+]...*)[^$_]}

Cobalah online!

kalau tidak

{sum 1 xx$_ Z/(1,&[+]...*)}

Cobalah online!

Japt -mx, 6 byte

1/MgUÄ

Cobalah

C # (.NET Core) , 66 byte

a=>{double r=1,x=1,y=1,i=0;for(;++i<a;y+=x,x=y-x)r+=1/y;return r;}

Cobalah online!

Tidak dapat menggunakan pelampung karena ketidaktepatan.

Contoh di mana input = 8:

• ganda: 3.28287545787546 (putaran ke 3.282875)
• float: 3.282876 (dinonaktifkan oleh 0,000001)

Tidak Disatukan:

a => {
    double r = 1,                       // initialize r (sum of reciprocals) - start at 1 to save one byte in for loop
            x = 1, y = 1,                   // initialize x (2nd largest Fibonacci) and y (largest Fibonacci)
            i = 0;                          // initialize i (loop counter)
    for(; ++i < a; y += x, x = y - x)   // from 1 to a, while incrementing the Fibonacci numbers
        r += 1 / y;                         // increment the reciprocal Fibonacci
    return r;                           // return the reciprocal Fibonacci
}

RPL (HP 49G / G + / 50g), 50 byte

« 0. 1. DUP2 5. ROLL
  START SWAP OVER + ROT OVER INV + UNROT
  NEXT DROP2
»

Contoh:

10 -> 3.33046904076

11 -> 3.34170499582

30 -> 3.35988372158

55 -> 3.35988566622

Secara teori, jumlah dari 55 digit pertama akan memberikan 12 digit yang benar. Digit terakhir harus '4' bukan '2'. Ini harus diperbaiki dengan menambahkan syarat mundur, tetapi kode akan sedikit lebih lama.

Jika konstanta dihitung hingga 1000 tempat desimal menggunakan definisi, jumlah harus dilakukan setidaknya 4747 istilah pertama, yang akan memakan terlalu banyak waktu pada HP 50g, jika mungkin sama sekali. Untuk tugas ini diperlukan metode yang lebih efisien, seperti yang digunakan dalam program RPL berikut (464 bytes, checksum # 207Eh) yang argumennya adalah jumlah tempat desimal yang diinginkan:

%%HP: T(3)A(R)F(.);
\<< PUSH RAD -105 CF -3 CF R\->I DUP 1 + 2 INV SWAP 100 LN * 5 LN + OVER ASINH / \v/ * CEIL DUP 2 MOD + DUP 0 ROT
[[ 1 1 ]
 [ 1 0 ]] SWAP DUP2 ^ 3 GETI UNROT GET 4 ROLLD 4 ROLLD DUP + ^ 1 GETI UNROT GET 1 + 0 1 8 ROLL 2 /
  START PICK3 + DUP PICK3 * NEG 6 PICK SQ + / 4 PICK SQ * EXPAND ROT PICK3 - ROT OVER - ROT 6 ROLL 6 ROLL 6 ROLL + LASTARG * LASTARG 5 ROLLD 5 ROLLD / + ROT PICK3 - ROT OVER - 6 ROLL 6 ROLL 6 ROLL
  NEXT ROT + INV 5 ROLL + EXPAND 4 ROLLD 3 DROPN FXND PICK3 ALOG OVER - PICK3 * SWAP IQUOT + \->STR DUP HEAD -51 FC? { "." } { "," } IFTE + SWAP TAIL + 1 ROT 2 + SUB POP
\>>

'RFC' STO

1000 RFC ->

3.3598856662431775531720113029189271796889051337319684864955538153251303189966833836154162164567900872970453429288539133041367890171008836795913517330771190785803335503325077531875998504871797778970060395645092153758927752656733540240331694417992939346109926262579646476518686594497102165589843608814726932495910794738736733785233268774997627277579468536769185419814676687429987673820969139012177220244052081510942649349513745416672789553444707777758478025963407690748474155579104200675015203410705335285129792635242062267537568055761955669720848843854407983324292851368070827522662579751188646464096737461572387236295562053612203024635409252678424224347036310363201466298040249015578724456176000319551987905969942029178866949174808096746523682654086938399069873211752166957063859411814553647364268782462926166650100098903804823359519893146150108288726392887669917149304053057745574321561167298985617729731395370735291966884327898022165047585028091806291002444277017460241040417786069190065037142835294

(22 menit 23 detik, pada HP 50g asli)

Untuk seribu digit, 50 syarat pertama dari seri tersebut ditambah 50 syarat dari fraksi lanjutan dievaluasi, dua sekaligus dalam hanya 25 iterasi (48 syarat masing-masing akan mencukupi, meskipun). Program DECIMAL BASIC yang setara hanya membutuhkan 10 milidetik pada komputer saya (Intel (R) Core (TM) Duo CPU E4700 @ 2.6 GHz).

JAEL, 9 7 byte

Mengubah diakritik dari satu karakter ke karakter lain memberi saya 1 byte

Masih bekerja pada pengkodean SBCS.

#`&@uȦ

Penjelasan (dihasilkan secara otomatis):

./jael -u explain '#`&@uȦ'

ORIGINAL CODE:
#`&@uȦ

EXPANDING EXPLANATION:
Ȧ => .a!

EXPANDED CODE:
#`&@u.a!

COMPLETED CODE:
#`&@u.a!,


#       ,               repeat (p1) times:
 `                              stack 1
  &                             push number of iterations of this loop
   @                            push nth fibonacci number
    u                           push p2 / p1
     .                          push the value under the tape head
      a                         push p1 + p2
       !                        write p1 to the tapehead
         ␄              print machine state

Jeli , 5 byte

RÆḞİS

Cobalah online!

Bagaimana itu bekerja

RÆḞİS    Main link (monad). Input: integer
R        Range
 ÆḞ      nth Fibonacci number
   İ     Reciprocal
    S    Sum

Pertanyaan , 13 11 byte

;/b$
=1:Z+Y

Cobalah online!

Penjelasan

;          The sum of the first n terms of the sequence
 /         which are 1 divided by
  b$       the nth term in the sequence on the second line

=1:Z+Y     Fibonacci with starting indexes 1,1