# Reverse Fibonacci

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 Fk to F0, where k is the smallest non-negative integer such that FkNFk+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 , lowest byte count wins.

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>

• So normal Fibonacci and then reversing the output? – TheLethalCoder Jul 27 '17 at 15:12
• – AdmBorkBork Jul 27 '17 at 15:23
• @AdmBorkBork isn't that the 'inverse Fibonacci function' and not 'return the fibonacci sequence, reversed'? – Giuseppe Jul 27 '17 at 15:24
• I'd say it's actually the reversed inverse Fibonacci function. (Sort of ...) – Arnauld Jul 27 '17 at 15:27
• @Arnauld you have changed the spec to invalidate multiple answers I believe. I'd suggest allowing ...1,0 or ...1,1,0 for any n>0, as that was what was implied by the original spec (see my comment above). – Jonathan Allan Jul 27 '17 at 16:46

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

• It is output fibonacci numbers up to n, not output the first n numbers. – Emigna Jul 28 '17 at 16:22
• @Emigna of course, my mistake. will revise or delete in a few hours – space junk Jul 30 '17 at 0:33

# 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
>   -   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, µ).

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. # 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! • 61 bytes – Mr. Xcoder Jul 27 '17 at 15:24 • 59 bytes for input()-print format – officialaimm Jul 27 '17 at 15:44 • This gives [1, 1, 0] for input 1, the correct output is [1, 0]. – Zgarb Aug 2 '17 at 7:33 • 64 bytes but I feel like this definitely isn't the best way to do this... Note: this properly handles 1 -> [1, 0] and not [1, 1, 0]. – Arnold Palmer Aug 2 '17 at 12:06 • 62 bytes cause I was stupid and had extra parenthesis. – Arnold Palmer Aug 2 '17 at 12:24 # 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 # 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 # Mathematica, 46 bytes Reverse@Select[Array[Fibonacci,t=1+#,0],#<t&]&  Try it online! thanx to @JungHwan Min for -16 bytes # 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.

# 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]&


# 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

# Husk, 201817 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)

§↓=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

• You can use the built-in İf for the list of Fibonacci numbers (I realized that this is not yet documented anywhere). – Zgarb Aug 2 '17 at 6:25
• The part ´o↓=3 doesn't work like you describe. It's interpreted as argdup (.) . dropWhile . (==) \$ 3, which drops leading 3s twice. Try it. – Zgarb Aug 2 '17 at 7:07
• This seems to work for 13 bytes. – Zgarb Aug 2 '17 at 7:25
• No problem. In general, you should use Ṡab instead of ´oab when the intended meaning is \x -> a (b x) x. It's shorter and has fewer possible types. – Zgarb Aug 2 '17 at 7:51

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

• Outputs 1 1 0 for 1 it should be 1 0 – TheLethalCoder Jul 27 '17 at 16:17
• I must have missed that in the specc. I would think that N=0 would give 1 0. There are other solutions here that output 1 1 0 as well for N=1. Anyway, I will work on making it conform with the specc. – jkelm Jul 27 '17 at 16:42
• You did not misread the spec, it got changed. I have commented about it. – Jonathan Allan Jul 27 '17 at 16:48

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

# 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!