Dado que ha habido una gran cantidad de desafíos normales de Fibonacci, decidí que podría ser interesante calcular la constante de Fibonacci recíproca , es decir, la suma de los recíprocos de la secuencia de Fibonacci.

El desafío es calcular la constante de Fibonacci recíproca con el número de series de Fibonacci para usar el dígito dado como entrada, es decir, una entrada de 10 medios para calcular en función de los recíprocos de los primeros 10 números de Fibonacci. En el caso probable de un empate, gana el código más corto.

El ganador será elegido en tres semanas a través de reglas estándar de código de golf.

K (19)

(o 17 si omite definirlo como una función)

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

Probado en Kona.

Básicamente, genera los primeros valores x de la secuencia de Fibonacci en una matriz (sin usar componentes integrados), divide 1 por cada valor de toda la matriz, la transpone y la resume.

(gracias a @tmartin por el mejor método de suma)

Perl - 35 bytes

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

Uso de la muestra:

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

Análisis mas extenso

Es interesante notar que la suma

es convergente Suponiendo que quisiéramos calcular unos pocos miles de dígitos, el enfoque ingenuo es casi suficiente. La convergencia es bastante lenta al principio, pero se acelera rápidamente, por lo que 1000 dígitos solo toman alrededor de 4800 términos. Una implementación de Python de muestra podría ser:

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

que después de un segundo más o menos sale:

33598856662431775531720113029189271796889051337319684864955538153251303189966833836154162164567900872970453429288539133041367890171008836795913517330771190785803335503325077531875998504871797778970060395645092153758927752656733540240331694417992939346109926262579646476518686594497102165589843608814726932495910794738736733785233268774997627277579468536769185419814676687429987673820969139012177220244052081510942649349513745416672789553444707777758478025963407690748474155579104200675015203410705335285129792635242062267537568055761955669720848843854407983324292851368070827522662579751188646464096737461572387236295562053612203024635409252678424224347036310363201466298040249015578724456176000319551987905969942029178866949174808096746523682654086938399069873211752166957063859411814553647364268782462926166650100098903804823359519893146150108288726392887669917149304053057745574321561167298985617729731395370735291966884327898022165047585028091806291002444277017460241040417786069190065037142832933

(Los últimos cuatro dígitos no convergen del todo, pero lo ignoraremos por ahora).

Intentemos acelerar un poco la convergencia. Un truco estándar es usar la transformación de Euler . Después de la expansión y la simplificación, esto produce un mejor resultado:

Debería ser bastante evidente por qué esto converge más rápidamente; cada término tiene 3 términos en el denominador en lugar de solo uno. Calcular 1000 dígitos solo requiere 1600 (un tercio de los términos):

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

Salida:

3598856662431775531720113029189271796889051337319684864955538153251303189966833836154162164567900872970453429288539133041367890171008836795913517330771190785803335503325077531875998504871797778970060395645092153758927752656733540240331694417992939346109926262579646476518686594497102165589843608814726932495910794738736733785233268774997627277579468536769185419814676687429987673820969139012177220244052081510942649349513745416672789553444707777758478025963407690748474155579104200675015203410705335285129792635242062267537568055761955669720848843854407983324292851368070827522662579751188646464096737461572387236295562053612203024635409252678424224347036310363201466298040249015578724456176000319551987905969942029178866949174808096746523682654086938399069873211752166957063859411814553647364268782462926166650100098903804823359519893146150108288726392887669917149304053057745574321561167298985617729731395370735291966884327898022165047585028091806291002444277017460241040417786069190065037142834500

(Aquí nuevamente, los últimos 4 dígitos no convergen).

Aún no hemos terminado. Si combinamos términos adyacentes, terminamos con lo siguiente:

Factorizar cada término del resto de la suma da la expresión anidada:

Ahora estamos llegando a alguna parte. Observe que los numeradores de siguen OEIS A206351 (con la excepción del primer término, que se duplica):

y los denominadores siguen OEIS A081016 (desplazado por un término):

Cada uno de estos tiene relaciones de recurrencia muy simples, a saber:

y

respectivamente. En conjunto, descubrimos que solo necesitamos 800 iteraciones por 1000 dígitos:

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

que salidas:

3598856662431775531720113029189271796889051337319684864955538153251303189966833836154162164567900872970453429288539133041367890171008836795913517330771190785803335503325077531875998504871797778970060395645092153758927752656733540240331694417992939346109926262579646476518686594497102165589843608814726932495910794738736733785233268774997627277579468536769185419814676687429987673820969139012177220244052081510942649349513745416672789553444707777758478025963407690748474155579104200675015203410705335285129792635242062267537568055761955669720848843854407983324292851368070827522662579751188646464096737461572387236295562053612203024635409252678424224347036310363201466298040249015578724456176000319551987905969942029178866949174808096746523682654086938399069873211752166957063859411814553647364268782462926166650100098903804823359519893146150108288726392887669917149304053057745574321561167298985617729731395370735291966884327898022165047585028091806291002444277017460241040417786069190065037142835294

(Aquí, finalmente, los últimos 4 dígitos convergen correctamente).

Pero eso todavía no es todo. Si observamos los valores intermedios para s , encontramos que converge a un valor completamente diferente antes de converger en el punto de convergencia real. La razón de esto es la siguiente:

Resolviendo un s estable , encontramos que:

Debido a que esta es una raíz simple, podemos usar el Método de Newton para llevarnos la mayor parte del camino y luego saltar a un punto mucho más tarde en la iteración. Sólo alrededor de 400 dígitos de precisión son necesarios (como los b y c valores no son cualquier mayor que el de todos modos), que se puede conseguir con sólo 7 iteraciones, mientras que el ahorro 320 iteraciones del bucle principal:

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

La salida es idéntica a la anterior, el tiempo de ejecución es de aproximadamente 0.02s en mi sistema usando PyPy v2.1. Aunque necesita una décima parte del número de iteraciones que el original, es significativamente más rápido que 10x debido a la multiplicación y división por términos mucho más pequeños. No creo que se pueda modificar mucho más, aunque estaría feliz de que me muestren mal.

Mathematica (32 caracteres sin Fibonacci incorporado)

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

Aquí utilicé la fórmula de redondeo para los números de Fibonacci

¿Dónde φestá la proporción áurea?

Kona ( 25 21)

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

Probablemente podría ser reducido por expertos, pero todavía estoy aprendiendo el idioma.

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

El último en realidad no tomó más tiempo que los demás.

Mathematica 30 24

Con 6 personajes guardados gracias a ybeltukov.

 Tr[1/Fibonacci@Range@#]&

Antes de agregar los términos:

1/Fibonacci@Range@#&[20]

Con la adición incluida:

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

APL, 21 caracteres / bytes *

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

Ejemplo

      {+/÷{↑+\∘⌽⍣⍵⊢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 puede escribirse en su propio} juego de
^{caracteres de un solo byte (heredado) que asigna símbolos APL a los valores superiores de 128 bytes. Por lo tanto, para fines de puntuación, un programa de N caracteres que solo usa caracteres ASCII y símbolos APL puede considerarse que tiene N bytes de longitud.}

Javascript, 33

Entrada: n = 10

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

Basado en mi primera publicación en Perl, aquí está el resultado directamente de la Consola Google Chrome .

K, 22

...

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

GTB , 35

Se ejecuta en una calculadora TI-84

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

• Almacenar 1en Yy 0enX
• Tomar Ncomo entrada
• Inicializar un Forbucle
• Monitor X
• Almacenar Yen Zy X+YenY
• Almacenar ZenX
• Fin del Forciclo

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;}

llame a r (n) con n para resolver. La precisión se puede establecer de forma arbitraria, por lo que esta es la solución más precisa.

PERL, 62 43

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

Editar:

Después de más tiempo mirando mi código, pude guardar 19 caracteres:

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

entrada: 10
> 3.35294128575734

Adelante, 64

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

uso:

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

Pitón ( 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

En modo interactivo:

n=10
3.341704995819338

n=100

3.3598856429940778

3.359885666243178

n=400

3.3598855578800064

3.359885666243178

Perl 6 , 27 bytes

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

Pruébalo en línea!

Alternativamente

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

Pruébalo en línea!

Japt -mx, 6 bytes

1/MgUÄ

Intentalo

C # (.NET Core) , 66 bytes

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

Pruébalo en línea!

No se pueden usar flotadores debido a la imprecisión.

Ejemplo donde input = 8:

• doble: 3.28287545787546 (se redondea a 3.282875)
• flotante: 3.282876 (apagado por 0.000001)

Sin golf:

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 bytes

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

Ejemplos:

10 -> 3.33046904076

11 -> 3.34170499582

30 -> 3.35988372158

55 -> 3.35988566622

En teoría, la suma de los primeros 55 dígitos daría 12 dígitos correctos. El último dígito debe ser '4' en lugar de '2'. Esto debería solucionarse sumando los términos al revés, pero el código sería un poco más largo.

Si la constante se calculara a 1000 decimales utilizando la definición, la suma debería realizarse al menos a los primeros 4790 términos, lo que tomaría demasiado tiempo en el HP 50g, si es posible. Para esta tarea se requiere un método más eficiente, como el utilizado en el siguiente programa RPL (464 bytes, suma de comprobación # 207Eh) cuyo argumento es el número deseado de lugares decimales:

%%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 min 23 seg, en el HP 50g real)

Para mil dígitos se evalúan los primeros 50 términos de la serie más otros 50 términos de una fracción continua, dos a la vez en solo 25 iteraciones (sin embargo, 48 términos de cada uno habrían sido suficientes). Un programa DECIMAL BASIC equivalente toma solo 10 milisegundos en mi computadora (Intel (R) Core (TM) Duo CPU E4700 @ 2.6 GHz).

JAEL, 9 7 bytes

Cambiar los signos diacríticos de un personaje a otro me dio 1 byte

Todavía estoy trabajando en la codificación SBCS.

#`&@uȦ

Explicación (generada automáticamente):

./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

Jalea , 5 bytes

RÆḞİS

Pruébalo en línea!

Cómo funciona

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

cQuents , 13 11 bytes

;/b$
=1:Z+Y

Pruébalo en línea!

Explicación

;          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