18
\$\begingroup\$

What is the Fibonacci Rectangular Prism Sequence?

The Fibonacci Rectangular Prism Sequence is a sequence derived from the Fibonacci sequence starting with one. The first 3 numbers of the Fibonacci sequence (starting with one) are 1, 1, and 2, so the first number of the Fibonacci Rectangular Prism Sequence is the square of the diagonal length of a rectangular prism (X in this picture) with the dimensions 1x1x2. The next number of the Fibonacci Rectangular Prism Sequence is the square of the diagonal length of a prism with the dimensions 1x2x3, followed by the square of the diagonal of 2x3x5, and so on. The formula for each number in the series would be A127546: $$a(n)={F_n}^2 + {F_{n+1}}^2 + {F_{n+2}}^2$$ where \$F_n\$ is the nth number of the Fibonacci sequence. The convention is that \$F_0\$ is 0, and \$F_1\$ is 1. (See A000045 for more information about the Fibonacci sequence.)

Your Challenge:

Write code that takes an index \$n\$ and outputs the \$n\$'th element of the sequence. It’s , so the shortest code wins!

Test cases:

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

Leaderboard:

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> 

\$\endgroup\$
3
  • 7
    \$\begingroup\$ By the way, a closed form is $$a(n) = 4\cdot\text{round}\left(\frac{\phi^{2n+2}}{5}\right)-2(-1)^n$$ where \$\phi\$ is the golden ratio. \$\endgroup\$
    – Lynn
    Oct 30, 2020 at 16:26
  • 2
    \$\begingroup\$ I'll be pedantic and say \$F_n^2 + F_{n_1}^2 + F_{n_2}^2\$ is not a formula, it's a number. Would you consider writing \$a(n) = F_n^2 + F_{n_1}^2 + F_{n_2}^2\$ instead? \$\endgroup\$
    – Stef
    Oct 31, 2020 at 8:56
  • \$\begingroup\$ @Stef That's probably more clear; I'll do that. \$\endgroup\$
    – nthnchu
    Oct 31, 2020 at 11:42

19 Answers 19

11
\$\begingroup\$

MathGolf, 6 bytes

This is not really interesting (but it is the shortest answer).

3r+f²Σ

Explanation

3, range, +, Fibonacci, square, sum.

Try it online!

\$\endgroup\$
2
  • 6
    \$\begingroup\$ Surprisingly readable for a golfing language! \$\endgroup\$ Oct 30, 2020 at 15:06
  • \$\begingroup\$ Ah, I forgot MathGolf had a Fibonacci builtin. Btw, not sure if you're aware, but you can add more than one input-lines and it will run each as a separated program: try it online. \$\endgroup\$ Oct 30, 2020 at 23:03
8
\$\begingroup\$

Python 2, 33 bytes

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

Try it online!

34 bytes

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

Try it online!

Outputs floats. Based on the closed form by Lynn, simplified to:

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

We further convert \$\phi^{2n+2} = (\phi^2)^{n+1} = (\phi+1)^{n+1}\$, writing \$\phi+1\$ as \$\frac{\sqrt{5}}{2}+1.5\$. We could also try writing it out as \$2.61803398875...\$ to some precision. The limited precision of floats will cause deviations for large enough outputs for any version of this solution.

44 bytes

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

Try it online!

An alternative recursive formula that gets rid of the \$(-1)^n\$ term by recursing one step further back.

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

where \$f(n)=2\$ for \$n<1\$.

44 bytes

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

Try it online!

Uses a recursive formula, with base case \$f(-1)=f(0)=2\$. Writes n%2*4-2 for -2*(-1)**n.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Cool! Is there an obvious reason why you can seemingly "replace" the 2(-1)^n term with floor? \$\endgroup\$
    – Lynn
    Oct 31, 2020 at 11:14
  • 1
    \$\begingroup\$ @Lynn I'm not quite sure, but the exponential estimate alternates undershooting and overshooting so rounding alternates up and down, I think because like the Fibonacci formula, the omitted conjugate term \$c^n\$ where \$c\$ is negative and has absolute value less than one. And the 2(-1)^n was contributing the opposite alternation (\$\frac{1}{2} (-1)^n \$ inside the multiplier of 4), so they canceled to flooring which just goes down. \$\endgroup\$
    – xnor
    Oct 31, 2020 at 19:47
7
\$\begingroup\$

JavaScript (ES6), 34 bytes

Saved 2 bytes thanks to @user and 3 more bytes thanks to @xnor

The following recursive formula is given for \$n>3\$ on OEIS, but it actually works for \$n>1\$:

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

As noticed by xnor, we can also make it work for \$a(1)\$ by defining \$a(-1)=a(0)=2\$.

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

Try it online!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ I think you can get 37 bytes by doing -1^n in a different way \$\endgroup\$
    – user
    Oct 30, 2020 at 16:03
  • \$\begingroup\$ @user Thank you! That 2*(-1)**n was looking terribly wrong indeed. \$\endgroup\$
    – Arnauld
    Oct 30, 2020 at 16:29
  • 2
    \$\begingroup\$ Shorter base case: TIO \$\endgroup\$
    – xnor
    Oct 30, 2020 at 22:23
5
\$\begingroup\$

05AB1E, 9 7 bytes

2Ý+ÅfnO

Try it online or verify all test cases.

Explanation:

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)


For funsies and since I was curious, here are the ports of the approaches used in @Razetime's Husk and @Arnauld's JavaScript answers:

10 bytes:

∞<Åfü3nOIè

Try it online or verify all test cases.

11 bytes

₂Sλè3*₂®Nm·Æ

Try it online or verify all test cases.

Explanation:

∞            # 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
\$\endgroup\$
5
\$\begingroup\$

Husk, 8 bytes

ṁ□↑3↓Θİf

Try it 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
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Oh, come ONNNN! \$\endgroup\$
    – Razetime
    Oct 30, 2020 at 13:24
5
\$\begingroup\$

Haskell, 34 bytes

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

Try it online!

Uses the \$a(n)=4F^2_{n+1}-2(-1)^n\$ formula.

Haskell, 34 bytes

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

Try it online!

Uses the \$a(n)=F_n^2+F_{n+1}^2+F_{n+2}^2\$ formula.

\$\endgroup\$
5
\$\begingroup\$

J, 20 bytes

-3 thanks to FrownyFrog

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

Try it online!

  • 2& f &1 1 Execute f n times with 2 as left argument and 1 1 as right argument.
  • +/@$,$ Sum first 2 elements of the list, and prepend it to itself
  • 1#.2^~ Square and sum.
\$\endgroup\$
2
  • \$\begingroup\$ 1#.2^~2&(+/@$,$)&1 1 \$\endgroup\$
    – FrownyFrog
    Nov 1, 2020 at 5:03
  • \$\begingroup\$ @FrownyFrog that's clever! Thanks. \$\endgroup\$
    – xash
    Nov 1, 2020 at 9:44
4
\$\begingroup\$

Husk, 9 bytes

!Ẋoṁ□ėΘİf

Try it online!

1-indexed.

Explanation

!Ẋ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
\$\endgroup\$
1
4
\$\begingroup\$

K (ngn/k), 27 25 bytes

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

Try it 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  
                      
                    

I managed to shave off 2 bytes after seeing @xash's J solution - please upvote their solution!

\$\endgroup\$
2
  • 2
    \$\begingroup\$ To make this work with other k's that don't support |2\6, 011b can be used instead. Here is a port to oK. \$\endgroup\$
    – coltim
    Oct 31, 2020 at 16:11
  • \$\begingroup\$ @coltim Thank you for your port to oK! \$\endgroup\$ Oct 31, 2020 at 17:58
4
\$\begingroup\$

R, 37 35 31 bytes

Nothing original, given the previous answers:

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

was 35 bytes, but Guiseppe got rid of four parentheses

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

Try it online!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ 35 bytes... \$\endgroup\$ Oct 31, 2020 at 10:44
  • \$\begingroup\$ @DominicvanEssen: darn, I first tried this version and it did not work on Tio...! \$\endgroup\$ Oct 31, 2020 at 13:46
  • 2
    \$\begingroup\$ I think you'd accidentally left a f= in the header (probably from a previous version), which can interfere with scan()-based golfs...? \$\endgroup\$ Oct 31, 2020 at 13:49
  • 1
    \$\begingroup\$ 31 bytes \$\endgroup\$
    – Giuseppe
    Oct 31, 2020 at 14:01
4
\$\begingroup\$

Charcoal, 24 23 bytes

F²⊞υ²FN⊞υ⁻⊗Σ…⮌υ²§υ±³I⊟υ

Try it online! Link is to verbose version of code Uses @xnor's recurrence relation. Explanation:

F²⊞υ²

Start with the -1th and 0th terms of the sequence.

FN

Generate as many additional terms as required.

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

Push twice the sum of the last two terms minus the previous. (On the first loop, there aren't enough terms, but Charcoal indexes cyclically, so it still finds 2 as desired. I could have just started with 3 terms; it makes no difference.)

I⊟υ

Output the final term, which is the desired result.

Alternative 23-byte solution generates the Fibonacci series:

⊞υ⁰F⁺²N⊞υ⊕↨…υι¹IΣXE³⊟υ²

Try it online! Link is to verbose version of code. Explanation:

⊞υ⁰

Start with the first term of the sequence.

F⁺²N

Extend the sequence until we have all the necessary terms.

⊞υ⊕↨…υι¹

Each term is one more than the sum of all the terms except the previous. I use base conversion from base 1 to avoid the edge case of the empty list.

IΣXE³⊟υ²

Pop the last three terms, square them, and print the sum.

\$\endgroup\$
3
\$\begingroup\$

Jelly, 8 bytes

3Ḷ+µÆḞ²S

Try it online!

I feel like it's possible to save a byte here, but I'm not sure how. (EDIT: Apparently the answer was to use 05AB1E; @Kevin Cruijssen's answer, which was written in parallel with this one, uses the same builtins in the same order but 05AB1E happens to parse it the way we'd want.)

You probably shouldn't upvote this answer; it's just a direct translation of the specification and contains no clever golfing tricks. I was just interested in how long it would come out to in Jelly.

Explanation

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}
\$\endgroup\$
3
  • \$\begingroup\$ why community wiki? \$\endgroup\$
    – Razetime
    Oct 30, 2020 at 12:26
  • 4
    \$\begingroup\$ @Razetime ais always does that. He doesn't want any rep for some reason. xD Before he used to delete his account every few weeks. :) \$\endgroup\$ Oct 30, 2020 at 12:27
  • \$\begingroup\$ An alternative 8 byter that avoids the µ issue, but doesn’t save any bytes \$\endgroup\$ Oct 31, 2020 at 2:01
3
\$\begingroup\$

Python 2, 47 bytes

I tried a few other methods, like the recurrence realtion used by Arnauld and the formaula provided by Emeric Deutsch on the OEIS page, but a literal implemention seems to be the shortest.

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Japt -x, 9 bytes

3ÆMgX+U ²

Try it

\$\endgroup\$
3
\$\begingroup\$

C (gcc), 42 38 bytes

Saved 4 bytes thanks to xnor!!!

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

Try it online!

Uses Arnauld's formula from his JavaScript answer.

\$\endgroup\$
2
  • \$\begingroup\$ A shorter base case with \$f(-1)=f(0)=2\$: f(n){n=n<1?2:3*f(n-1)-f(n-2)+n%2*4-2;} TIO \$\endgroup\$
    – xnor
    Oct 30, 2020 at 22:40
  • \$\begingroup\$ @xnor Nice one - thanks! :D \$\endgroup\$
    – Noodle9
    Oct 30, 2020 at 22:43
3
\$\begingroup\$

Arn, 16 bytes

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

Try it!

Explained

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

Uses the same closed-form variant @xnor uses.

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

Also for fun:

Arn -l, 22 bytes

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

Try it!

Explained

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

Sequence definition, the -l flag returns the last entry

\$\endgroup\$
3
\$\begingroup\$

Scala, 53 bytes

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

Try it online

This one uses the method used in @Arnauld's answer.


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}

Try it online

\$\endgroup\$
2
\$\begingroup\$

Retina, 39 bytes

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

Try it online! No test suite because of the way the program uses history. Explanation:

K`_¶_

Replace the input with the first terms (in unary) of the Fibonacci sequence.

"$+"+`

Repeat n times...

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

... sum the first two terms and drop terms after the third.

%`_
$=

Square each term separately.

_

Take the sum and convert to decimal.

\$\endgroup\$
2
\$\begingroup\$

Perl 5, 51 bytes

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

Try it online!

Just a translation of Arnaulds Javascript answer.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.