A sequência de prisma retangular de Fibonacci

Question

O que é a sequência do prisma retangular de Fibonacci ?

A Sequência de Prisma Retangular de Fibonacci é uma sequência derivada da sequência de Fibonacci começando com um. Os primeiros 3 números da sequência de Fibonacci (começando com um) são 1, 1 e 2, então o primeiro número da Sequência de Prisma Retangular de Fibonacci é o quadrado do comprimento diagonal de um prisma retangular (X nesta imagem ) com o dimensões 1x1x2. O próximo número da Sequência do Prisma Retangular de Fibonacci é o quadrado do comprimento diagonal de um prisma com as dimensões 1x2x3, seguido pelo quadrado da diagonal de 2x3x5 e assim por diante. A fórmula para cada número da série seria A127546 :$$a(n)={F_n}^2 + {F_{n+1}}^2 + {F_{n+2}}^2$$onde \$F_n\$é o enésimo número da sequência de Fibonacci. A convenção é que \$F_0\$é 0 e \$F_1\$é 1. (Consulte A000045 para obter mais informações sobre a sequência de Fibonacci.)

Seu Desafio:

Escreva o código que leva um índice \$n\$e produz o \$n\$'ésimo elemento da sequência. É o código de golfe , então o código mais curto vence!

Casos de teste:

0 ==> 2
1 ==> 6
2 ==> 14
3 ==> 38
4 ==> 98
5 ==> 258
6 ==> 674
7 ==> 1766
8 ==> 4622
9 ==> 12102
10 ==> 31682

Entre os melhores:

var QUESTION_ID=214423,OVERRIDE_USER=98932,ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;function answersUrl(d){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+d+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(d,e){return"https://api.stackexchange.com/2.2/answers/"+e.join(";")+"/comments?page="+d+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(d){answers.push.apply(answers,d.items),answers_hash=[],answer_ids=[],d.items.forEach(function(e){e.comments=[];var f=+e.share_link.match(/\d+/);answer_ids.push(f),answers_hash[f]=e}),d.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(d){d.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),d.has_more?getComments():more_answers?getAnswers():process()}})}getAnswers();var SCORE_REG=function(){var d=String.raw`h\d`,e=String.raw`\-?\d+\.?\d*`,f=String.raw`[^\n<>]*`,g=String.raw`<s>${f}</s>|<strike>${f}</strike>|<del>${f}</del>`,h=String.raw`[^\n\d<>]*`,j=String.raw`<[^\n<>]+>`;return new RegExp(String.raw`<${d}>`+String.raw`\s*([^\n,]*[^\s,]),.*?`+String.raw`(${e})`+String.raw`(?=`+String.raw`${h}`+String.raw`(?:(?:${g}|${j})${h})*`+String.raw`</${d}>`+String.raw`)`)}(),OVERRIDE_REG=/^Override\s*header:\s*/i;function getAuthorName(d){return d.owner.display_name}function process(){var d=[];answers.forEach(function(n){var o=n.body;n.comments.forEach(function(q){OVERRIDE_REG.test(q.body)&&(o="<h1>"+q.body.replace(OVERRIDE_REG,"")+"</h1>")});var p=o.match(SCORE_REG);p&&d.push({user:getAuthorName(n),size:+p[2],language:p[1],link:n.share_link})}),d.sort(function(n,o){var p=n.size,q=o.size;return p-q});var e={},f=1,g=null,h=1;d.forEach(function(n){n.size!=g&&(h=f),g=n.size,++f;var o=jQuery("#answer-template").html();o=o.replace("{{PLACE}}",h+".").replace("{{NAME}}",n.user).replace("{{LANGUAGE}}",n.language).replace("{{SIZE}}",n.size).replace("{{LINK}}",n.link),o=jQuery(o),jQuery("#answers").append(o);var p=n.language;p=jQuery("<i>"+n.language+"</i>").text().toLowerCase(),e[p]=e[p]||{lang:n.language,user:n.user,size:n.size,link:n.link,uniq:p}});var j=[];for(var k in e)e.hasOwnProperty(k)&&j.push(e[k]);j.sort(function(n,o){return n.uniq>o.uniq?1:n.uniq<o.uniq?-1:0});for(var l=0;l<j.length;++l){var m=jQuery("#language-template").html(),k=j[l];m=m.replace("{{LANGUAGE}}",k.lang).replace("{{NAME}}",k.user).replace("{{SIZE}}",k.size).replace("{{LINK}}",k.link),m=jQuery(m),jQuery("#languages").append(m)}}

body{text-align:left!important}#answer-list{padding:10px;float:left}#language-list{padding:10px;float:left}table thead{font-weight:700}table td{padding:5px}

 <script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="https://cdn.sstatic.net/Sites/codegolf/primary.css?v=f52df912b654"> <div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td><a href="{{LINK}}">{{SIZE}}</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td><a href="{{LINK}}">{{SIZE}}</a></td></tr></tbody> </table> 

Answer 1

MathGolf , 6 bytes

Isso não é realmente interessante (mas é a resposta mais curta).

3r+f²Σ

Explicação

3, intervalo, +, Fibonacci, quadrado, soma.

Experimente online!

Answer 2

Python 2 , 33 bytes

lambda n:((3-5**.5)/2)**~n//5*4+2

Experimente online!

34 bytes

lambda n:(5**.5/2+1.5)**-~n//5*4+2

Experimente online!

As saídas flutuam. Baseado no formulário fechado por Lynn , simplificado para:

$$ f(n) = 4 \left \lfloor{\frac{\phi^{2n+2}}{5}}\right \rfloor + 2.$$

Nós ainda convertemos \$\phi^{2n+2} = (\phi^2)^{n+1} = (\phi+1)^{n+1}\$, escrevendo \$\phi+1\$como \$\frac{\sqrt{5}}{2}+1.5\$. Também podemos tentar escrever como \$2.61803398875...\$com alguma precisão. A precisão limitada dos flutuadores causará desvios para saídas grandes o suficiente para qualquer versão desta solução.

44 bytes

f=lambda n:2*(n<1)or(f(n-1)+f(n-2))*2-f(n-3)

Experimente online!

Uma fórmula recursiva alternativa que elimina o \$(-1)^n\$ termo recorrendo um passo para trás.

$$ f(n) = 2f(n-1) + 2f(n-2)-f(n-3)$$

onde \$f(n)=2\$para \$n<1\$.

44 bytes

f=lambda n:2*(n<1)or 3*f(n-1)-f(n-2)+n%2*4-2

Experimente online!

Usa uma fórmula recursiva, com caso base \$f(-1)=f(0)=2\$. Escreve n%2*4-2para -2*(-1)**n.

Answer 3

JavaScript (ES6), 34 bytes

Economizou 2 bytes graças a @user e mais 3 bytes graças a @xnor

A seguinte fórmula recursiva é fornecida para \$n>3\$no OEIS , mas na verdade funciona para \$n>1\$:

$$a(n) = 3a(n-1)-a(n-2)-2(-1)^n$$

Como notado por xnor, também podemos fazer funcionar para \$a(1)\$definindo \$a(-1)=a(0)=2\$.

f=n=>n<1?2:3*f(n-1)-f(n-2)+n%2*4-2

Experimente online!

Answer 4

05AB1E , 9 7 bytes

2Ý+ÅfnO

Experimente online ou verifique todos os casos de teste .

Explicação:

2Ý       # Push list [0,1,2]
  +      # Add each to the (implicit) input-integer: [n,n+1,n+2]
   Åf    # Get the Fibonacci numbers at those indices: [F(n),F(n+1),F(n+2)]
     n   # Square each: [F(n)²,F(n+1)²,F(n+2)²]
      O  # Sum them together: F(n)²+F(n+1)²+F(n+2)²
         # (after which the result is output implicitly)

---

---

Por diversão e como eu estava curioso, aqui estão as portas das abordagens usadas nas respostas Husk do @Razetime e JavaScript do @Arnauld :

10 bytes :

∞<Åfü3nOIè

Experimente online ou verifique todos os casos de teste .

11 bytes

₂Sλè3*₂®Nm·Æ

Experimente online ou verifique todos os casos de teste .

Explicação:

∞            # Push an infinite positive list: [1,2,3,4,5,...]
 <           # Decrease each by 1 to let it start at 0: [0,1,2,3,4,...]
  Åf         # Get the 0-based Fibonacci number: [0,1,1,2,3,...]
    ü3       # Create overlapping triplets: [[0,1,1],[1,1,2],[1,2,3],[2,3,5],[3,5,8],..]
      n      # Square each inner value: [[0,1,1],[1,1,4],[1,4,9],[4,9,25],[9,25,64],...]
       O     # Sum each: [2,6,14,38,98,...]
        Iè   # Index the input-integer into the list
             # (after which the result is output implicitly)

  λ          # Start a recursive environment
   è         # to output the 0-based (implicit) input'th value implicitly afterwards,
₂S           # starting at a(0)=2,a(1)=6
             # (`₂S`: push builtin 26, convert it to a list of digits)
             # And we calculate every following a(n) as follows:
             #  (implicitly push the value of a(n-1)
    3*       #  Multiply it by 3: 3*a(n-1)
      ₂      #  Push a(n-2)
       ®     #  Push -1
        Nm   #  to the power of the current n: (-1)**n
          ·  #  Double it: 2*(-1)**n
           Æ #  Reduce the three values on the stack by subtracting:
             #   3*a(n-1)-a(n-2)-2*(-1)**n

Answer 5

Husk , 8 bytes

ṁ□↑3↓Θİf

Experimente online!

ṁ□↑3↓Θİf
     Θİf    # fibonacci sequence starting with zero
    ↓       # remove first n elements (n = input)
  ↑3        # get first 3 elements of what's left
ṁ□          # square each of them & sum

Answer 6

Haskell , 34 bytes

f=2:scanl(+)2f
a n=f!!n^2-2*(-1)^n

Experimente online!

Usa o \$a(n)=4F^2_{n+1}-2(-1)^n\$ Fórmula.

Haskell , 34 bytes

(0!1!!)
a!b|c<-a+b=a^2+b^2+c^2:b!c

Experimente online!

Usa o \$a(n)=F_n^2+F_{n+1}^2+F_{n+2}^2\$ Fórmula.

Answer 7

J , 20 bytes

-3 graças a FrownyFrog

1#.2^~2&(+/@$,$)&1 1

Experimente online!

• 2& f &1 1Execute f nvezes com o 2argumento esquerdo e 1 1como o argumento direito.
• +/@$,$Some os primeiros 2elementos da lista e acrescente-a a si mesma
• 1#.2^~ Quadrado e soma.

Answer 8

Husk , 9 bytes

!Ẋoṁ□ėΘİf

Experimente online!

1 indexado.

Explicação

!Ẋoṁ□ėΘİf
       İf infinite fibonacci sequence
      Θ   prepend a 0
 Ẋo       map the following over triplets of values
     ė    make list of 3 elements
   ṁ□     sum their squares
!         index into this list using input

Answer 9

K (ngn / k) , 27 25 bytes

{+/t*t:x({x,+/x}1_)/|2\6}

Experimente online!

{                       } \ function with parameter x
                     2\6  \ 6 to binary -? 1 1 0
                    |     \ reverse -> 0 1 1 
       x(         )/      \ repeat the function in () n times
                1_        \ drop the first number and
         {     }          \ apply this function to the remaining list
            +/x           \ sum
          x,              \ append to the list
     t:                   \ assign to t
   t*                     \ square
 +/                       \ sum  
                      
                    

Consegui cortar 2 bytes depois de ver a solução J de @xash - vote a favor da solução!

Answer 10

R , 37 35 31 bytes

Nada original, dadas as respostas anteriores:

(((3+5^.5)/2)^(scan()+1)/5)%/%1*4+2

tinha 35 bytes, mas Guiseppe se livrou de quatro parênteses

((3+5^.5)/2)^(scan()+1)%/%5*4+2

Experimente online!

Answer 11

Carvão , 24 23 bytes

Ｆ²⊞υ²ＦＮ⊞υ⁻⊗Σ…⮌υ²§υ±³Ｉ⊟υ

Experimente online! O link é para a versão detalhada do código. Usa a relação de recorrência do @xnor. Explicação:

Ｆ²⊞υ²

Comece com o -1º e o 0º termos da seqüência.

ＦＮ

Gere quantos termos adicionais forem necessários.

⊞υ⁻⊗Σ…⮌υ²§υ±³

Empurre duas vezes a soma dos dois últimos termos menos o anterior. (No primeiro loop, não há termos suficientes, mas o carvão é indexado ciclicamente, então ainda encontra 2como desejado. Eu poderia ter apenas começado com 3 termos; não faz diferença.)

Ｉ⊟υ

Produza o termo final, que é o resultado desejado.

A solução alternativa de 23 bytes gera a série Fibonacci:

⊞υ⁰Ｆ⁺²Ｎ⊞υ⊕↨…υι¹ＩΣＸＥ³⊟υ²

Experimente online! O link é para a versão detalhada do código. Explicação:

⊞υ⁰

Comece com o primeiro termo da sequência.

Ｆ⁺²Ｎ

Estenda a sequência até que tenhamos todos os termos necessários.

⊞υ⊕↨…υι¹

Cada termo é um a mais que a soma de todos os termos, exceto o anterior. Eu uso a conversão de base da base 1 para evitar o caso extremo da lista vazia.

ＩΣＸＥ³⊟υ²

Estale os últimos três termos, eleve-os ao quadrado e imprima a soma.

Answer 12

Gelatina , 8 bytes

3Ḷ+µÆḞ²S

Experimente online!

Sinto que é possível salvar um byte aqui, mas não tenho certeza de como. (EDITAR: Aparentemente, a resposta foi usar 05AB1E; a resposta de @Kevin Cruijssen , que foi escrita em paralelo com esta, usa os mesmos builtins na mesma ordem, mas 05AB1E acontece para analisá-lo da maneira que gostaríamos.)

Você provavelmente não deveria votar positivamente nesta resposta; é apenas uma tradução direta das especificações e não contém truques de golfe inteligentes. Eu só estava interessado em saber quanto tempo duraria em Jelly.

Explicação

3Ḷ+µÆḞ²S
3Ḷ         [0,1,2]
  +        add {the input} to {each elemeent}
   µ       (fix for parser ambiguity)
    ÆḞ     take the Fibonacci number whose index is {each element}
      ²    square {each element}
       S   sum the resulting list {and output it}

Answer 13

Python 2 , 47 bytes

Tentei alguns outros métodos, como o realtion de recorrência usado por Arnauld e a formaula fornecida por Emeric Deutsch na página OEIS, mas uma implementação literal parece ser a mais curta.

f=lambda n,a=0,b=1:n+2and(n<2)*b*b+f(n-1,b,a+b)

Experimente online!

Answer 14

Japt -x , 9 bytes

3ÆMgX+U ²

Tente

Answer 15

C (gcc) , 42 38 bytes

Economizei 4 bytes graças ao xnor !!!

f(n){n=n<1?2:3*f(n-1)-f(n-2)+n%2*4-2;}

Experimente online!

Usa a fórmula de Arnauld de sua resposta JavaScript .

Answer 16

Arn , 16 bytes

╗¤û°œJ–¬▀ôƒìÚ„")

Tente!

Explicado

Desempacotado: 2+4*:v(phi^(*2+2)/5

Usa a mesma variante de formato fechado que @xnor usa.

  2
+  Plus
    4
  *  Times
    :v  Floor of
      (
          phi  The golden ratio
        ^  Exponentiated by
          (
                _  Variable ≡ STDIN; implied
              *
                2
            +
              2
          )
        /  Divided by
          5
      )  Implied

Também por diversão:

Arn -l , 22 bytes

ñf©¶─[•«DWLšií▬Xy®┐Vÿ"

Tente!

Explicado

Desempacotado: v:1[2 2{*3- -2*_1^++v}->+2

Definição da sequência, o -lsinalizador retorna a última entrada

Answer 17

Scala, 53 bytes

def f(n:Int):Int=if(n>0)3*f(n-1)+n%2*4-2-f(n-2)else 2

Experimente online

Este usa o método usado na resposta de @Arnauld .

---

Dotty, 84 bytes

n=>{def f:Stream[Int]=0#::1#::f.zip(f.tail).map(_+_);f.slice(n,n+3).map(x=>x*x).sum}

Experimente online

Answer 18

Retina , 39 bytes

K`_¶_
"$+"+L$`(_+¶)(_+)
$2$1$& %`_ $=
_

Experimente online! Sem suíte de teste devido à forma como o programa usa o histórico. Explicação:

K`_¶_

Substitua a entrada pelos primeiros termos (em unário) da sequência de Fibonacci.

"$+"+`

Repetir nvezes ...

L$`(_+¶)(_+)
$2$1$&

... some os dois primeiros termos e elimine os termos após o terceiro.

%`_
$=

Quadrado cada termo separadamente.

_

Pegue a soma e converta em decimal.

Answer 19

Perl 5 , 51 bytes

sub a{my$n=pop;(2)[$n]||3*a($n-1)-a($n-2)+$n%2*4-2}

Experimente online!

Apenas uma tradução da resposta Javascript de Arnaulds.