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.

• 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

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?

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