22
\$\begingroup\$

About Zeckendorf Representations/Base Fibonacci Numbers

This is a number system which uses Fibonacci numbers as its base. The numbers consist of 0 and 1's and each 1 means that the number contains the corresponding Fibonacci number, and 0 means it does not.

For example, let's convert all natural numbers <=10 to base Fibonacci.

  • 1 will become 1, because it is the sum of 1, which is a Fibonacci number,

  • 2 will become 10, because it is the sum of 2, which is a Fibonacci number, and it does not need 1, because we already achieved the desired sum.

  • 3 will become 100, because it is the sum of 3, which is a Fibonacci number and it does not need 2 or 1 because we already achieved the desired sum.

  • 4 will become 101, because it is the sum of [3,1], both of which are Fibonacci numbers.
  • 5 will become 1000, because it is the sum of 5, which is a Fibonacci number, and we do not need any of the other numbers.
  • 6 will become 1001, because it is the sum of the Fibonacci numbers 5 and 1.
  • 7 will become 1010, because it is the sum of the Fibonacci numbers 5 and 2.
  • 8 will become 10000, because it is a Fibonacci number.
  • 9 will become 10001, because it is the sum of the Fibonacci numbers 8 and 1.
  • 10 will become 10010, because it is the sum of the Fibonacci numbers 8 and 2.

Let's convert a random Base Fibonacci number, 10101001010 to decimal: First we write the corresponding Fibonacci numbers. Then we compute the sum of the numbers under 1's.

 1 0 1 0 1 0 0 1 0 1 0
 144 89 55 34 21 13 8 5 3 2 1 -> 144+たす55+たす21+たす5+たす2 =わ 227.

Read more about Base Fibonacci numbers: link, it also has a tool which converts regular integers to base Fibonacci. You can experiment with it.

Now the Question:

Your task is to take a number in the Zeckendorf Representation, and output its decimal value.

Input is a string which contains only 0 and 1's (although you can take the input in any way you want).

Output one number in decimal.

Test cases: (in the format input->output)

 1001 -> 6
 100101000 -> 73
 1000000000 -> 89
 1001000000100100010 -> 8432
 1010000010001000100001010000 -> 723452

This is code-golf, so the shortest answer in bytes wins.

Note: The input will not contain any leading 0's or consecutive 1's.

Wheat Wizard ♦
103k23 gold badges299 silver badges697 bronze badges
asked Oct 7, 2018 at 17:54
\$\endgroup\$
7
  • \$\begingroup\$ Can we take input as a list of bits? \$\endgroup\$ Commented Oct 7, 2018 at 18:27
  • \$\begingroup\$ Like, take the input ascii encoded then convert it to binary or something like that? \$\endgroup\$ Commented Oct 7, 2018 at 18:31
  • 4
    \$\begingroup\$ Can we take input in LSB-first order? \$\endgroup\$ Commented Oct 8, 2018 at 0:52
  • 1
    \$\begingroup\$ Subset of codegolf.stackexchange.com/questions/54287/…, inverse of codegolf.stackexchange.com/questions/2677/… . \$\endgroup\$ Commented Oct 8, 2018 at 1:06
  • 1
    \$\begingroup\$ @Mego Yes, you can \$\endgroup\$ Commented Oct 8, 2018 at 3:55

25 Answers 25

19
\$\begingroup\$

Taxi, (削除) 1987 (削除ここまで) 1927 bytes

-60 bytes due to the realization that linebreaks are optional.

Go to Post Office:w 1 l 1 r 1 l.Pickup a passenger going to Chop Suey.Go to Chop Suey:n 1 r 1 l 4 r 1 l.[B]Switch to plan C if no one is waiting.Pickup a passenger going to Cyclone.Go to Cyclone:n 1 l 3 l.Pickup a passenger going to Narrow Path Park.Pickup a passenger going to Sunny Skies Park.Go to Zoom Zoom:n.Go to Sunny Skies Park:w 2 l.Go to Narrow Path Park:n 1 r 1 r 1 l 1 r.Go to Chop Suey:e 1 r 1 l 1 r.Switch to plan B.[C]1 is waiting at Starchild Numerology.1 is waiting at Starchild Numerology.Go to Starchild Numerology:n 1 l 3 l 3 l 2 r.Pickup a passenger going to Addition Alley.Pickup a passenger going to Cyclone.Go to Cyclone:w 1 r 4 l.[D]Pickup a passenger going to Addition Alley.Pickup a passenger going to Cyclone.Go to Addition Alley:n 2 r 1 r.Go to Cyclone:n 1 l 1 l.Pickup a passenger going to Multiplication Station.Go to Zoom Zoom:n.Go to Narrow Path Park:w 1 l 1 l 1 r.Switch to plan E if no one is waiting.Pickup a passenger going to The Babelfishery.Go to The Babelfishery:e 1 r.Pickup a passenger going to Multiplication Station.Go to Multiplication Station:n 1 r 2 l.Pickup a passenger going to Joyless Park.Go to Joyless Park:n 2 l 1 r 1 r.Go to Addition Alley:w 1 r 2 l 1 l.Pickup a passenger going to Cyclone.Go to Cyclone:n 1 l 1 l.Pickup a passenger going to Addition Alley.Switch to plan D.[E]Go to Addition Alley:w 1 l 1 r 1 l.Pickup a passenger going to Riverview Bridge.Go to Riverview Bridge:n 1 r.Go to Joyless Park:e 1 r 2 l.Pickup a passenger going to Addition Alley.[F]Switch to plan G if no one is waiting.Pickup a passenger going to Addition Alley.Go to Fueler Up:w 1 l.Go to Addition Alley:n 3 l 1 l.Pickup a passenger going to Addition Alley.Go to Joyless Park:n 1 r 1 r 2 l.Switch to plan F.[G]Go to Addition Alley:w 1 r 2 l 1 l.Pickup a passenger going to The Babelfishery.Go to The Babelfishery:n 1 r 1 r.Pickup a passenger going to Post Office.Go to Post Office:n 1 l 1 r.

Try it online!

Because I don't return to the Taxi Garage at the end, my boss fires me, so it exits with an error.

answered Oct 7, 2018 at 23:07
\$\endgroup\$
2
  • \$\begingroup\$ Joyless Park seems a nice place to visit \$\endgroup\$ Commented Oct 8, 2018 at 12:00
  • \$\begingroup\$ Well, it IS fewer characters than Sunny Skies Park. \$\endgroup\$ Commented Oct 8, 2018 at 17:52
11
\$\begingroup\$

Perl 6, (削除) 28 (削除ここまで) 23 bytes

{[+] (1,2,*+*...*)Z*$_}

Try it online!

Anonymous codeblock that takes a list of 1s and 0s in LSB ordering and returns a number.

Explanation:

{ } # Anonymous codeblock
 [+] # The sum of
 (1,2,*+*...*) # The infinite Fibonacci sequence starting from 1,2
 Z* # Zip multiplied by
 $_ # The input list in LSB form
answered Oct 8, 2018 at 2:41
\$\endgroup\$
0
7
\$\begingroup\$

Jelly, 5 bytes 

T‘ÆḞS

A monadic link accepting a list in Little-endian form (i.e. from the LSB at the left to MSB at the right).

Try it online!

answered Oct 7, 2018 at 18:06
\$\endgroup\$
1
  • \$\begingroup\$ Nice, I had an alternative 6-byter: J‘ÆḞḋṚ. \$\endgroup\$ Commented Oct 7, 2018 at 19:55
7
\$\begingroup\$

Wolfram Language (Mathematica), (削除) 35 (削除ここまで) (削除) 32 (削除ここまで) (削除) 29 (削除ここまで) 28 bytes

Fibonacci[Range@Tr[#!]+1].#&

Try it online!

answered Oct 8, 2018 at 2:45
\$\endgroup\$
0
5
\$\begingroup\$

Python 2, 43 bytes

a=b=0
for x in input():b+=a+x;a=b-a
print b

Try it online!

Takes input as a list. The update is a shorter version of a,b=b+x,a+b+x, which is like the Fibonacci update a,b=b,a+b if you ignore x.

Python 2, 45 bytes

f=lambda n,a=1,b=1:n and n%10*b+f(n/10,b,a+b)

Try it online!

Takes input as decimal numbers.

answered Oct 7, 2018 at 18:06
\$\endgroup\$
4
\$\begingroup\$

Haskell, 38 bytes

f=1:scanl(+)2f
sum.zipWith(*)f.reverse

Try it online!

Takes input as a list of 1s and 0s.

Explanation

f=1:scanl(+)2f

Makes a list of the Fibonacci numbers sans the first one, in variable f.

sum.zipWith(*)f.reverse

Takes the input list reverses it the multiplies each entry by the corresponding entry in f, then sums the results.

Haskell, 30 bytes

f=1:scanl(+)2f
sum.zipWith(*)f

Try it online!

If we take input in with the least significant bit first we don't need reverse so we can save 8 bytes.

answered Oct 7, 2018 at 18:35
\$\endgroup\$
3
\$\begingroup\$

Pyth, 13 bytes

Most of this (8 bytes) is just generating the Fibonacci numbers.

s*V_m=+Z|~YZ1

Try it out with this test suite!

Explanation:

s*V_m=+Z|~YZ1QQ Autofill variables
 m=+Z|~YZ1Q Generate the first length(input) Fibonacci numbers as follows:
 Z Start with Z=0
 ~YZ And Y=[] (update it to Y=Z, return old Y)
 | 1 if Y is [], then replace with 1
 + Sum Z and Y
 = Replace Z with sum
 m Repeat process
 Q once for each element of the input
 _ Reverse the order of the Fibonacci numbers
 *V Vectorize multiplication
s Sum
answered Oct 7, 2018 at 19:28
\$\endgroup\$
3
\$\begingroup\$

Brain-Flak, (削除) 110 (削除ここまで), (削除) 102 (削除ここまで), (削除) 96 (削除ここまで), (削除) 94 (削除ここまで), (削除) 78 (削除ここまで), 74 bytes

([[]]<>((()))){({}()<([({})]({}({})))>)}{}{}({<>{<{}><>({})(<>)}{}<><{}>})

Try it online!

answered Oct 7, 2018 at 18:57
\$\endgroup\$
3
\$\begingroup\$

J, (削除) 24 (削除ここまで) 14 bytes

#.~2+&%&1~#-#\

Try it online!

Golfed down the 24-byte version that uses the mixed base for Fibonacci.

How it works

#.~2+&%&1~#-#\ Example input: y=1 0 0 1 0
 #-#\ Length minus 1-based indices; 4 3 2 1 0
 2 ~ Starting from 2, run the following (4,3,2,1,0) times:
 +&%&1 Given y, compute 1 + 1 / y
 The result is 13/8 8/5 5/3 3/2 2
#.~ Mixed base conversion of y into base above; 2+8=10

J, 21 bytes

1#.|.*[:+/@(!~#-])\#\

Try it online!

Refined version of Galen Ivanov's 25-byte solution.

Uses the diagonal sum of Pascal's triangle, which is equivalent to the sum of binomial coefficients:

\$ F_n = \sum\limits_{i=0}^{n} {}_{n-i}C_{i} \$

How it works

1#.|.*[:+/@(!~#-])\#\
 Example input: 1 0 0 1 0
 #\ Generate 1-based index; 1 2 3 4 5
 [: \ For each prefix of above... (ex. 1 2 3)
 #-] Subtract each element from the length (ex. 2 1 0)
 (!~ ) Compute binomial coefficient (ex. 3C0 + 2C1 + 1C2)
 +/@ Sum
 The result is Fibonacci numbers; 1 2 3 5 8
 |.* Multiply with mirrored self; 0 2 0 0 8
1#. Sum; 10

J, 24 bytes

3 :'y#.~|.(1+%)^:(<#y)2'

Try it online!

Monadic explicit verb. Generates the mixed base that represents the Fibonacci base, and then feeds into base conversion #..

How it works

y#.~|.(1+%)^:(<#y)2 Explicit verb, input: y = Fibonacci digit array, n = length of y
 (1+%) x -> 1 + 1/x
 ^:(<#y)2 Apply the above 0..n-1 times to 2
 The result looks like 2/1, 3/2, 5/3, 8/5, 13/8, ...
 |. Reverse
 Now, if it is fed into #. on the left, the digit values become
 ...(8/5 * 5/3 * 3/2 * 2/1), (5/3 * 3/2 * 2/1), (3/2 * 2/1), 2/1, 1
 which is ... 8 5 3 2 1 (Yes, it's Fibonacci.)
y#.~ Convert y to a number using Fibonacci base

Alternatives

J, 27 bytes

}.@(+#{.3#{.)^:(<:@#)@(,&0)

Try it online!

The idea:

 1 0 0 1 0 1
-1 +1 +1
------------------
 1 1 1 0 1
 -1 +1 +1
------------------
 2 2 0 1
 -2 +2 +2
------------------
 4 2 1
 -4 +4 +4
------------------
 6 5
 -6 +6 +6 <- Add an imaginary digit that has value 1
---------------------
 11 6
 -11+11
---------------------
 17 <- the answer

J, 30 bytes

0.5<.@+(%:5)%~(-:>:%:5)#.,&0 0

Try it online!

This one took the most effort to build. Uses the closed-form expression with rounding trick. In the expression, 0th and 1st values are 0 and 1 respectively, so the actual digit power must start with 2.

0.5<.@+(%:5)%~(-:>:%:5)#.,&0 0 Tacit verb.
 ,&0 0 Add two zeroes at the end
 (-:>:%:5)#. Convert to a number using base phi (golden ratio)
 (%:5)%~ Divide by sqrt(5)
0.5<.@+ Round to nearest integer

While the error (((1-sqrt(5))/2)^n terms) may build up, it never exceeds 0.5, so the rounding trick works up to infinity. Mathematically:

\$ \max(|error|) = \frac{1}{\sqrt{5}} \sum\limits_{1}^{\infty} (\frac{1-\sqrt{5}}{2})^{2n} = \frac{1}{\sqrt{5}} \sum\limits_{0}^{\infty} (\frac{1-\sqrt{5}}{2})^{n} = \frac{\sqrt{5}-1}{2\sqrt{5}} < \frac{1}{2} \$

answered Oct 8, 2018 at 6:52
\$\endgroup\$
4
  • \$\begingroup\$ Nice solution! I'm glad to see an explicit verb beating the tacit solution. \$\endgroup\$ Commented Oct 8, 2018 at 7:43
  • \$\begingroup\$ I'm trying to find a shorter tacit solution, but without success. 25 bytes for now. I use Pascal's triange. \$\endgroup\$ Commented Oct 8, 2018 at 11:28
  • \$\begingroup\$ @GalenIvanov Revisiting the challenge after a year, I got a new, super short tacit solution :) \$\endgroup\$ Commented Nov 15, 2019 at 2:09
  • \$\begingroup\$ That's great! I'll look at it in more details soon. \$\endgroup\$ Commented Nov 15, 2019 at 4:42
2
\$\begingroup\$

MathGolf, (削除) 8 (削除ここまで) 6 bytes

{î)f*+

Try it online!

Explanation

{ Start block (foreach in this case)
 î) Push loop index (1-based) and increment by 1
 f Get fibonacci number of that index
 * Multiply with the array value (0 or 1)
 + Add top two elements of stack. This implicitly pops the loop index the first iteration, which makes the addition become 0+a, where a is the top of the stack.

Saved 1 byte thanks to JoKing, and another byte thanks to LSB ordering.

answered Oct 8, 2018 at 11:52
\$\endgroup\$
2
  • \$\begingroup\$ LSB order is indeed allowed. also, -1 byte \$\endgroup\$ Commented Oct 8, 2018 at 12:17
  • \$\begingroup\$ @JoKing Of course, I even implemented the implicit addition just last week... Nice touch, now MathGolf is at a tied first place! \$\endgroup\$ Commented Oct 8, 2018 at 13:34
2
\$\begingroup\$

05AB1E, (削除) 11 (削除ここまで) (削除) 9 (削除ここまで) 8 bytes

vyiNÌÅfO

Try it online!

Explanation:

v : For each character in input string (implicit) in LSB order
 yi : If the current character is truthy (1)
 NÌ : Add 2 to the current index
 ÅfO : Add the fibonacci of this number to the stack
  • -2 bytes: Thanks to @KevinCruijssen for pointing out small ways to shorten this code!
  • -1 byte: Thanks to @JonathanAllan for pointing out LSB order for input!
answered Oct 7, 2018 at 22:09
\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can remove the Θ. 1 is truthy in 05AB1E already. :) Also, 2+ can be Ì. \$\endgroup\$ Commented Oct 8, 2018 at 9:13
  • 1
    \$\begingroup\$ We can take the input in Little-endian form (i.e. reversed), which should save a byte (or two?). \$\endgroup\$ Commented Oct 9, 2018 at 8:51
1
\$\begingroup\$

Retina 0.8.2, 23 bytes

0?
;
+`1;(1*);
;11ドル;1
1

Try it online! Link includes the faster test cases. Explanation:

0?
;

Insert separators everywhere and delete any zeros. For example, 1001 becomes ;1;;;1;.

+`1;(1*);
;11ドル;1

Repeatedly replace each 1 with a 1 in each of the next two places, as the sum of their values equals the value of the original 1. 1s therefore migrate and accumulate until they reach the last two places, which (due to the newly added separator) now both have value 1.

1

Count the 1s.

answered Oct 7, 2018 at 20:28
\$\endgroup\$
1
\$\begingroup\$

Python 3, 63 bytes

a=b=n=1
for i in input()[::-1]:n+=b*int(i);a,b=b,a+b
print(n-1)

Try it online!

Takes input through STDIN as a string.

answered Oct 7, 2018 at 22:20
\$\endgroup\$
1
\$\begingroup\$

Red, (削除) 142, 126 (削除ここまで) 106 bytes

func[a][b: copy[1 1]reverse a s: 0 n: 1
until[s: b/1 * a/:n + s insert b b/1 + b/2(n: n + 1)> length? a]s]

Try it online!

answered Oct 7, 2018 at 20:02
\$\endgroup\$
1
\$\begingroup\$

Ruby, 39 bytes

->n{a,b=0,1;n.digits.sum{|x|x*b=a+a=b}}

Try it online!

answered Oct 8, 2018 at 11:14
\$\endgroup\$
1
\$\begingroup\$

Stax, 6 bytes 

çéC◘0â

Run and debug it 

:1F^|5+ #Full program, unpacked, implicit input as array 
:1 #Get indicies of truthy
 F #Use rest of program to loop through elements
 ^ #Increment current element
 |5+ #Get n-th fib and Add

Pretty straight forward. LSB Ordering.

answered Oct 8, 2018 at 13:09
\$\endgroup\$
1
\$\begingroup\$

Brain-Flak, 40 bytes

([]){{}([({}<>{})]({}{}))<>([])}<>({}{})

Try it online!

answered Oct 8, 2018 at 17:18
\$\endgroup\$
1
\$\begingroup\$

C (gcc), 63 bytes

Takes input as an array of 1's and 0's, along with the length of the array. This solution is a rather straight-forward backwards loop.

f(_,l,a,b,t)int*_;{a=b=1;for(t=0;l--;b=(a+=b)-b)t+=a*_[l];_=t;}

Try it online!

answered Oct 8, 2018 at 20:48
\$\endgroup\$
1
\$\begingroup\$

Prolog (SWI), 74 bytes

\D-->[X,Y],{D is 2*X+Y};[D];a,\D.
a,[A],[B]-->[X,Y,Z],{A is X+Y,B is X+Z}.

Try it online!

Takes input as a list of integers 1 and 0 with the most significant bit first.

answered Oct 9, 2018 at 7:34
\$\endgroup\$
0
\$\begingroup\$

Japt -x, 9 bytes

Ë*MgUÊa ́E

Try it

answered Oct 7, 2018 at 22:23
\$\endgroup\$
0
\$\begingroup\$

JavaScript (Node.js), 41 bytes

A port of xnor's answer. Takes input as a BigInt literal.

f=(n,a=1n,b=a)=>n&&n%10n*b+f(n/10n,b,a+b)

Try it online!

JavaScript (ES6), 44 bytes

Takes input as an array of characters, in LSB-first order.

s=>s.map(k=>t+=k*(z=x,x=y,y+=z),x=t=0,y=1)|t

Try it online!

answered Oct 7, 2018 at 20:20
\$\endgroup\$
0
\$\begingroup\$

Actually, 8 bytes

;r⌐@░♂FΣ

Try it online!

Input is taken as a list of bits in LSB-first order.

Explanation:

;r⌐@░♂FΣ
;r range(0, len(input))
 ⌐ add 2 to every element in range (range(2, len(input)+2))
 @░ filter: take values in range that correspond to 1s in input
 ♂F Fibonacci number at index of each element in list (Actually uses the F(0)=F(1)=1 definition, which is why we needed to add 2 earlier)
 Σ sum
answered Oct 8, 2018 at 1:00
\$\endgroup\$
0
\$\begingroup\$

Powershell, 68 bytes

param($s)$b=1
$s[$s.Length..0]|%{$a,$b=$b,($a+$b)
$x+=($_-48)*$b}
$x

Test script:

$f = {
param($s)$b=1
$s[$s.Length..0]|%{$a,$b=$b,($a+$b)
$x+=($_-48)*$b}
$x
}
@(
 ,("1001", 6)
 ,("100101000", 73)
 ,("1000000000", 89)
 ,("1001000000100100010", 8432)
 ,("1010000010001000100001010000", 723452)
) | % {
 $s,$e = $_
 $r = &$f $s
 "$($r-eq$e): $r"
}

Output:

True: 6
True: 73
True: 89
True: 8432
True: 723452
answered Oct 8, 2018 at 13:36
\$\endgroup\$
0
\$\begingroup\$

Java (OpenJDK 8), 65 bytes

Pretty small for a Java answer to I'm happy with that. Takes input as a LSB-first ordered array of ints.

d->{int s=0,f=1,h=1;for(int i:d){s+=i>0?f:0;f=h+(h=f);}return s;}

Try it online!

Ungolfed

d->{ // Lambda function that takes array of ints
 int s=0,f=1,h=1; // Initialise sum and fibonacci vars
 for(int i:d){ // Loop through each input integer
 s+=i>0?f:0; // If it's 1 add current fibonacci number to sum
 f=h+(h=f); // Increase fibonacci number 
 }return s; // return sum
}
answered Oct 9, 2018 at 10:47
\$\endgroup\$
0
\$\begingroup\$

Z80Golf, 34 bytes

00000000: dde1 f1b7 2819 fe30 2812 4504 aff5 3cf5 ....(..0(.E...<.
00000010: d1f1 82d5 f510 f9c1 f17c 8067 2c18 e3dd .........|.g,...
00000020: e5c9 ..

Example with input 1001-Try it online!

Example with input 100101000-Try it online!

Assembly:

zeck:		; input=push on stack in MSB order (eg top is LSB) output=reg h
pop ix		; save return addr in ix
f:
pop af		; get next digit
or a
jr z, return	; if current digit==0, return
cp 0x30
jr z, skip	; if current digit=='0' (e.g. not '1'), skip loop
ld b, l		; find fib of counter
fib:
	inc b	; 1-indexing for func to work
	xor a	; set a to 0 (1st fibo num)
	push af
	inc a	; set a to 1 (2nd fibo num)
	push af
	fib_loop:
		pop de
		pop af
		add d
		push de
		push af
		djnz fib_loop
pop bc		; get the fibo num just calculated
pop af		; pop just to reset stack frame
ld a, h
add b		; add current fibo number to sum
ld h, a
skip:
inc l		; increment counter reg
jr f		; repeat loop
return:
push ix		; push the return addr to ret to it
ret
answered Oct 10, 2018 at 23:43
\$\endgroup\$

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.