Reverse Fibonacci

Question

Your task

You must write a program, to print a reverse Fibonacci series, given a number.

Input

A non-negative integer N.

Output

You must output all the Fibonacci numbers from F_k to F₀, where k is the smallest non-negative integer such that F_k ≤ N ≤ F_k+1.

Example

IN: 5

OUT: 5 3 2 1 1 0

If input isn't a Fibonacci number, the series should begin from the closest Fibonacci number less than the input.

IN:  15

OUT: 13 8 5 3 2 1 1 0

If input is 1, the series should be.

IN:  1

OUT: 1 0

Scoring:

This is code-golf, lowest byte count wins.

Leaderboard

var QUESTION_ID=136123,OVERRIDE_USER=60869;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&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(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.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(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;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="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <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><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><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

Answer 1

Haskell, 52 bytes

p=0:scanl(+)1p
f 1=[1,0]
f n=reverse$takeWhile(<=n)p

Second line is necessary for the n = 1 edge-case. I wasn't able to get around it.

Answer 2

Jelly,  9  8 bytes

ḤḶÆḞṚ>Ðḟ

A monadic link taking a number and returning the list of numbers.

Try it online!

Note: I am assuming 1s are not both required, if they are the previous 9 byter works: +2ḶµÆḞṚfṖ

How?

ḤḶÆḞṚ>Ðḟ - Link: number, n
Ḥ        - double n (this is to cater for inputs less than 6)
 Ḷ       - lowered range of that -> [0,1,2,...,2*n-1]
  ÆḞ     - nth Fibonacci number for €ach -> [0,1,1,...,fib(2*n-1)]
    Ṛ    - reverse that
      Ðḟ - filter discard if:
     >   -   greater than n?

...the reason this only outputs [1,0] for an input of 1 is that the unfiltered list does not contain fib(2), the second 1.

The 9 byter works by adding two, +2, to form the lowered range [0,1,2,...,n,(n+1)] rather than doubling and then filter keeping, f, any results which are in a popped, Ṗ, version of that same list, [0,1,2,...,n] (the value accessed by making a monadic chain, µ).

Answer 3

Python 2, 62 59 bytes

n,l,a,b=input(),[],0,1
while a<=n:l=[a]+l;a,b=b,a+b
print l

Try it online!

Answer 4

Neim, 5 bytes

f₁>𝕖𝐫

Try it online!

Explanation

f            infinite list of fibonacci numbers
 ₁>          get input and increment it
   𝕖         first b elements of a
    𝐫        reverse the list 

I feel like this could be golfed more. ₁> feels a bit inefficient...

Answer 5

Dyalog APL, 28 bytes

{x/⍨⍵≥x←⌽{1∧+∘÷/0,⍵/1}¨⍳2×⍵}

Requires ⎕IO←0.

Try it online!

How?

{1∧+∘÷/0,⍵/1} - apply fibonacci

    ¨⍳2×⍵ - to the range 0 .. 2n

x←⌽ - reverse and assign to x

x/⍨ - filter x with

    ⍵≥x - the function x <= n

Answer 6

Python 2, 58 bytes

Note: invalidated by recent specification change (1 -> (1, 1, 0))

n=input()
r=1,0
while r[0]<=n:r=(r[0]+r[1],)+r
print r[1:]

A full program accepting from stdin and printing (a tuple representation of) the numbers in the reversed order.

Try it online! or see a test suite

Answer 7

Mathematica, 46 bytes

Reverse@Select[Array[Fibonacci,t=1+#,0],#<t&]&

Try it online!

thanx to @JungHwan Min for -16 bytes

Answer 8

Perl 6, 40 bytes

{[R,] 0,1,*+*...^{2>$_??$^a==1!!$^b>$_}}

Test it

Explanation:

• {…} create a bare block lambda with implicit parameter $_
• [R,] LIST is a Left fold using the reverse meta-op R combined with the comma op ,.
  (shorter than reverse)
• 0, 1, *+* ...^ Callable produces a Fibonacci sequence that stops on the value before Callable returns a True value.

The remaining code is a bit complicated as it has to return True if the original input is 1 and the second to latest value is 1. This is so that the full lambda returns (1,0) instead of (1,1,0).

{ # bare block lambda with two placeholder params ｢$a｣ and ｢$b｣

    2 > $_    # is the original input smaller than 2

  ??          # if it is
    $^a == 1  # check if the second to latest value is 1

  !!          # otherwise
    $^b > $_  # check if the latest value is bigger than the original input
}

---

If the code was allowed to return (1,1,0) when given the value 1, it can be dramatically shorter at 22 bytes:

{[R,] 0,1,*+*...^*>$_}

Test it

In this case * > $_ creates a WhateverCode lambda that in this use-case will return True if the generated value is greater than the original input.

Everything else is the same as above.

Answer 9

Mathematica, 52 41 bytes

{1,0}//.{a_,b_,c___}/;a+b<#:>{a+b,a,b,c}&

Fibonacci@Range[Floor[Log[GoldenRatio,1+√5#]],0,-1]&

Answer 10

05AB1E, 9 bytes

ÎÅF)˜RIi¦

Try it online!

If [1, 1, 0] is valid output for 1 this would be ÎÅF)˜R at 6 bytes

Answer 11

Husk, 20 18 17 13 bytes

Thanks a lot @Zgarb for telling me about İf which is a built-in for Fibonacci numbers, this saved me 4 bytes:

§↓=1ȯ↔`↑:0İf≤

Try it online!

Ungolfed/Explanation

               -- implicit input N
          İf   -- get all Fibonacci numbers,
        :0     -- prepend 0,
      `↑    ≤  -- take as as long as the number is ≤ N,
    ȯ↔         -- reverse and
§ =1           -- if input == 1:
 ↓             --   drop 1 element else no element

---

Old answer without built-in (17 bytes)

The old answer is quite similar to shooqie's Haskell answer:

§↓=1ȯ↔`↑ȯƒo:0G+1≤

Try it online!

Ungolfed/Explanation

A really short way to compute Fibonacci numbers in Haskell is to define a recursive function like this (also see the Haskell answer):

fibos = 0 : scanl (+) 1 fibos

Essentially that code computes the fixpoint of the function \f -> 0 : scanl (+) 1 f, so you can rewrite fibos in an anonymous way like this:

fix (\f -> 0 : scanl (+) 1 f)

Try it online!

This corresponds to the Husk code (ƒo:0G+1), here's the remaining code annotated:

                   -- implicit input N
        ȯƒo:0G+1   -- generate Fibonacci numbers (ȯ is to avoid brackets),
      `↑        ≤  -- take as as long as the number is ≤ N,
    ȯ↔             -- reverse and
§ =1               -- if input == 1:
 ↓                 --   drop 1 element else no element

Answer 12

C# (.NET Core), 70 bytes

n=>{var t="0";for(int a=0,b=1,c;b<=n;c=a,a=b,b+=c)t=b+" "+t;return t;}

Try it online!

Input is an integer into the Lambda. Output is a space-delimited string of the fibonacci sequence in reverse.

Answer 13

Javascript (ES6), 42 bytes

f=(n,a=0,b=1)=>b>n|a>=n?a:f(n,b,a+b)+" "+a

Alternative, if f(1) = 1 1 0

f=(n,a=0,b=1)=>b>n?a:f(n,b,a+b)+" "+a

Example code snippet:

f=(n,a=0,b=1)=>b>n|a>=n?a:f(n,b,a+b)+" "+a

console.log(f(5))
console.log(f(15))
console.log(f(1))

Answer 14

Röda, 58 bytes

{|k|a=0;b=1{{[a];b=a+b;a=b-a}while[a<k,b<=k];[a]}|reverse}

Try it online!