Visto que houve muitos desafios normais de Fibonacci, decidi que talvez fosse interessante calcular a constante recíproca de Fibonacci - a saber, a soma dos recíprocos da sequência de Fibonacci.

O desafio é calcular a constante recíproca de Fibonacci com o número de séries de Fibonacci para usar o dígito dado como entrada, ou seja, uma entrada de 10 meios para calcular com base nos recíprocos dos 10 primeiros números de Fibonacci. No provável caso de empate, o código mais curto vence.

O vencedor será escolhido em três semanas através das regras padrão do código de golfe.

K (19)

(ou 17 se você pular a definição como uma função)

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

Testado em Kona.

Basicamente, ele gera os primeiros x valores da sequência de fibonacci em uma matriz (sem o uso de componentes internos), divide 1 por cada valor de toda a matriz, transpõe e resume.

(graças a @tmartin pelo melhor método de soma)

Perl - 35 bytes

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

Uso da amostra:

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

Análise Adicional

É interessante notar que a soma

é convergente. Supondo que desejássemos calcular alguns milhares de dígitos, a abordagem ingênua é quase suficiente. A convergência é bastante lenta no início, mas acelera rapidamente, de modo que 1000 dígitos levam apenas cerca de 4800 termos. Uma implementação de exemplo de Python pode 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 após um segundo ou mais produz:

33598856662431775531720113029189271796889051337319684864955538153251303189966833836154162164567900872970453429288539133041367890171008836795913517330771190785803335503325077531875998504871797778970060395645092153758927752656733540240331694417992939346109926262579646476518686594497102165589843608814726932495910794738736733785233268774997627277579468536769185419814676687429987673820969139012177220244052081510942649349513745416672789553444707777758478025963407690748474155579104200675015203410705335285129792635242062267537568055761955669720848843854407983324292851368070827522662579751188646464096737461572387236295562053612203024635409252678424224347036310363201466298040249015578724456176000319551987905969942029178866949174808096746523682654086938399069873211752166957063859411814553647364268782462926166650100098903804823359519893146150108288726392887669917149304053057745574321561167298985617729731395370735291966884327898022165047585028091806291002444277017460241040417786069190065037142832933

(Os últimos quatro dígitos não convergem completamente, mas vamos ignorá-lo por enquanto.)

Vamos tentar acelerar um pouco a convergência. Um truque padrão é usar a transformação de Euler . Após expansão e simplificação, isso produz um resultado melhor:

Deveria ser bastante claro por que isso converge mais rapidamente; cada termo tem 3 termos no denominador em vez de apenas um. O cálculo de 1000 dígitos requer apenas 1600 (um terço do número) de termos:

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

Resultado:

3598856662431775531720113029189271796889051337319684864955538153251303189966833836154162164567900872970453429288539133041367890171008836795913517330771190785803335503325077531875998504871797778970060395645092153758927752656733540240331694417992939346109926262579646476518686594497102165589843608814726932495910794738736733785233268774997627277579468536769185419814676687429987673820969139012177220244052081510942649349513745416672789553444707777758478025963407690748474155579104200675015203410705335285129792635242062267537568055761955669720848843854407983324292851368070827522662579751188646464096737461572387236295562053612203024635409252678424224347036310363201466298040249015578724456176000319551987905969942029178866949174808096746523682654086938399069873211752166957063859411814553647364268782462926166650100098903804823359519893146150108288726392887669917149304053057745574321561167298985617729731395370735291966884327898022165047585028091806291002444277017460241040417786069190065037142834500

(Aqui, novamente, os últimos 4 dígitos não convergem.)

Ainda não terminamos. Se combinarmos termos adjacentes, terminamos com o seguinte:

A fatoração de cada termo do restante da soma fornece a expressão aninhada:

Agora estamos chegando a algum lugar. Observe que os numeradores seguem OEIS A206351 (com exceção do primeiro termo, que é dobrado):

e os denominadores seguem OEIS A081016 (alterado por um termo):

Cada um deles tem relações de recorrência muito simples, a saber:

e

respectivamente. Juntando tudo, descobrimos que precisamos de apenas 800 iterações para 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

quais saídas:

3598856662431775531720113029189271796889051337319684864955538153251303189966833836154162164567900872970453429288539133041367890171008836795913517330771190785803335503325077531875998504871797778970060395645092153758927752656733540240331694417992939346109926262579646476518686594497102165589843608814726932495910794738736733785233268774997627277579468536769185419814676687429987673820969139012177220244052081510942649349513745416672789553444707777758478025963407690748474155579104200675015203410705335285129792635242062267537568055761955669720848843854407983324292851368070827522662579751188646464096737461572387236295562053612203024635409252678424224347036310363201466298040249015578724456176000319551987905969942029178866949174808096746523682654086938399069873211752166957063859411814553647364268782462926166650100098903804823359519893146150108288726392887669917149304053057745574321561167298985617729731395370735291966884327898022165047585028091806291002444277017460241040417786069190065037142835294

(Aqui, finalmente, os últimos 4 dígitos convergem corretamente.)

Mas isso ainda não é tudo. Se observarmos os valores intermediários para s , descobrimos que ele converge para um valor completamente diferente antes de convergir no ponto de convergência real. O motivo para isso é o seguinte:

Resolvendo para um s estável , descobrimos que:

Como essa é uma raiz simples, podemos usar o Método de Newton para chegar até lá e depois pular em um ponto muito mais tarde na iteração. Apenas cerca de 400 dígitos de precisão são necessários (como as de b e c valores não são maiores do que qualquer que de qualquer forma), que pode ser alcançada com apenas 7 iterações, enquanto poupando 320 iterações do ciclo 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

A saída é idêntica à anterior, o tempo de execução é de cerca de 0,02s no meu sistema usando o PyPy v2.1. Embora precise de um décimo do número de iterações que o original, é significativamente mais rápido que 10x devido à multiplicação e divisão por termos muito menores. Eu não acho que muito mais possa ser alterado, embora eu ficaria feliz em ser mostrado errado.

Mathematica (32 caracteres sem Fibonacci interno)

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

Aqui eu usei a fórmula de arredondamento para números de Fibonacci

Onde φestá a proporção áurea.

Kona ( 25 21)

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

Provavelmente poderia ser reduzido por especialistas, mas ainda estou aprendendo o idioma.

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

O último não demorou mais que os outros.

Mathematica 30 24

Com 6 caracteres salvos, graças a ybeltukov.

 Tr[1/Fibonacci@Range@#]&

Antes de adicionar os termos:

1/Fibonacci@Range@#&[20]

Com adição incluída:

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

APL, 21 caracteres / bytes *

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

Exemplo

      {+/÷{↑+\∘⌽⍣⍵⊢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 pode ser escrito na sua própria (legado) de conjunto de caracteres de byte único que mapeia símbolos APL para os 128 valores de bytes superiores. Portanto, para fins de pontuação, um programa de N caracteres que usa apenas caracteres ASCII e símbolos APL pode ser considerado como N bytes.}

Javascript, 33

Entrada: n = 10

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

Baseado no meu primeiro post no Perl, aqui está o resultado diretamente do Google Chrome Console .

K, 22

...

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

GTB , 35

É executado em uma calculadora TI-84

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

• Armazenar 1dentro Ye 0dentroX
• Tome Ncomo entrada
• Inicializar um Forloop
• Exibição X
• Armazenar Ydentro Ze X+YdentroY
• Armazenar ZemX
• Terminar o 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;}

chame r (n) com n para resolver. A precisão pode ser definida arbitrariamente, portanto, esta é a solução mais precisa.

PERL, 62 43

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

Editar:

Depois de mais algum tempo analisando meu código, pude salvar 19 caracteres:

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

entrada: 10
> 3.35294128575734

Quarto, 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

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

No modo interativo:

n=10
3.341704995819338

n=100

3.3598856429940778

3.359885666243178

n=400

3.3598855578800064

3.359885666243178

Perl 6 , 27 bytes

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

Experimente online!

alternativamente

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

Experimente online!

Japonês -mx, 6 bytes

1/MgUÄ

Tente

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

Experimente online!

Não é possível usar carros alegóricos por imprecisão.

Exemplo em que input = 8:

• duplo: 3,28287545787546 (arredonda para 3,282875)
• float: 3.282876 (off por 0.000001)

Ungolfed:

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
»

Exemplos:

10 -> 3.33046904076

11 -> 3.34170499582

30 -> 3.35988372158

55 -> 3.35988566622

Em teoria, a soma dos primeiros 55 dígitos daria 12 dígitos corretos. O último dígito deve ser '4' em vez de '2'. Isso deve ser corrigido adicionando os termos ao contrário, mas o código seria um pouco mais longo.

Se a constante fosse calculada com 1000 casas decimais usando a definição, a soma deveria ser realizada pelo menos nos primeiros 4790 termos, o que levaria muito tempo no HP 50g, se possível. Para esta tarefa, é necessário um método mais eficiente, como o usado no seguinte programa RPL (464 bytes, soma de verificação # 207Eh) cujo argumento é o número desejado de casas decimais:

%%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 s, na verdadeira HP 50g)

Para mil dígitos, os 50 primeiros termos da série e outros 50 termos de uma fração contínua são avaliados, dois de cada vez em apenas 25 iterações (48 termos de cada um seriam suficientes). Um programa DECIMAL BASIC equivalente leva apenas 10 milissegundos no meu computador (CPU Intel® Core® Duo E4700 a 2,6 GHz).

JAEL, 9 7 bytes

Alterar os diacríticos de um caractere para outro me deu 1 byte

Ainda trabalhando na codificação SBCS.

#`&@uȦ

Explicação (gerada automaticamente):

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

Gelatina , 5 bytes

RÆḞİS

Experimente online!

Como funciona

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

cQuents , 13 11 bytes

;/b$
=1:Z+Y

Experimente online!

Explicação

;          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