8
\$\begingroup\$

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

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>

\$\endgroup\$
  • 10
    \$\begingroup\$ So normal Fibonacci and then reversing the output? \$\endgroup\$ – TheLethalCoder Jul 27 '17 at 15:12
  • 1
    \$\begingroup\$ Closely related. \$\endgroup\$ – AdmBorkBork Jul 27 '17 at 15:23
  • 1
    \$\begingroup\$ @AdmBorkBork isn't that the 'inverse Fibonacci function' and not 'return the fibonacci sequence, reversed'? \$\endgroup\$ – Giuseppe Jul 27 '17 at 15:24
  • 1
    \$\begingroup\$ I'd say it's actually the reversed inverse Fibonacci function. (Sort of ...) \$\endgroup\$ – Arnauld Jul 27 '17 at 15:27
  • 1
    \$\begingroup\$ @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). \$\endgroup\$ – Jonathan Allan Jul 27 '17 at 16:46

14 Answers 14

2
\$\begingroup\$

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

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

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

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

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.

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

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!

\$\endgroup\$
  • \$\begingroup\$ 61 bytes \$\endgroup\$ – Mr. Xcoder Jul 27 '17 at 15:24
  • \$\begingroup\$ 59 bytes for input()-print format \$\endgroup\$ – officialaimm Jul 27 '17 at 15:44
  • \$\begingroup\$ This gives [1, 1, 0] for input 1, the correct output is [1, 0]. \$\endgroup\$ – Zgarb Aug 2 '17 at 7:33
  • \$\begingroup\$ 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]. \$\endgroup\$ – Arnold Palmer Aug 2 '17 at 12:06
  • \$\begingroup\$ 62 bytes cause I was stupid and had extra parenthesis. \$\endgroup\$ – Arnold Palmer Aug 2 '17 at 12:24
2
\$\begingroup\$

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

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

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

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

Mathematica, 46 bytes

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

Try it online!

thanx to @JungHwan Min for -16 bytes

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

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.

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

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]&
\$\endgroup\$
2
\$\begingroup\$

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

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

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
\$\endgroup\$
  • 1
    \$\begingroup\$ You can use the built-in İf for the list of Fibonacci numbers (I realized that this is not yet documented anywhere). \$\endgroup\$ – Zgarb Aug 2 '17 at 6:25
  • \$\begingroup\$ The part ´o↓=3 doesn't work like you describe. It's interpreted as argdup (.) . dropWhile . (==) $ 3, which drops leading 3s twice. Try it. \$\endgroup\$ – Zgarb Aug 2 '17 at 7:07
  • \$\begingroup\$ This seems to work for 13 bytes. \$\endgroup\$ – Zgarb Aug 2 '17 at 7:25
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Zgarb Aug 2 '17 at 7:51
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Outputs 1 1 0 for 1 it should be 1 0 \$\endgroup\$ – TheLethalCoder Jul 27 '17 at 16:17
  • \$\begingroup\$ 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. \$\endgroup\$ – jkelm Jul 27 '17 at 16:42
  • \$\begingroup\$ You did not misread the spec, it got changed. I have commented about it. \$\endgroup\$ – Jonathan Allan Jul 27 '17 at 16:48
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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