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>

• TheLethalCoder: So normal Fibonacci and then reversing the output?
• AdmBorkBork: Closely related.
• Giuseppe: @AdmBorkBork isn't that the 'inverse Fibonacci function' and not 'return the fibonacci sequence, reversed'?
• Arnauld: I'd say it's actually the reversed inverse Fibonacci function. (Sort of ...)
• Jonathan Allan: @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).

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!

• Mr. Xcoder: 61 bytes
• 0xffcourse: 59 bytes for input()-print format
• Zgarb: This gives [1, 1, 0] for input 1, the correct output is [1, 0].
• Arnold Palmer: 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: 62 bytes cause I was stupid and had extra parenthesis.

Answer 4

Neim, 5 bytes

f1>er

Try it online!

Explanation

f infinite list of fibonacci numbers
 1> get input and increment it
 e first b elements of a
 r reverse the list 

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

• Emigna: It is output fibonacci numbers up to n, not output the first n numbers.
• space junk: @Emigna of course, my mistake. will revise or delete in a few hours

Answer 5

Dyalog APL, 28 bytes

{x/⍨⍵≥x←⌽{1∧+∘÷/0,⍵/1} ×ばつ⍵}

Requires ⎕IO←0.

Try it online!

How?

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

×ばつ⍵ - 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

• Zgarb: You can use the built-in İf for the list of Fibonacci numbers (I realized that this is not yet documented anywhere).
• Zgarb: 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: This seems to work for 13 bytes.
• Zgarb: 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.

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.

• TheLethalCoder: Outputs 1 1 0 for 1 it should be 1 0
• jkelm: 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.
• Jonathan Allan: You did not misread the spec, it got changed. I have commented about it.

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!