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.

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.

JosiahRyanW 10/08/2018.

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

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

Jo King 10/08/2018.

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

Anonymous codeblock that takes a list of `1`

s and `0`

s in LSB ordering and returns a number.

```
{ } # 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
```

nixpower 10/08/2018.

Jonathan Allan 10/08/2018.

Post Left Garf Hunter 10/09/2018.

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

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

`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 `reverse`

s it the multiplies each entry by the corresponding entry in `f`

, then `sum`

s the results.

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

If we take input in with the least significant bit first we don't need `reverse`

so we can save 8 bytes.

xnor 10/11/2018.

Steven H. 10/07/2018.

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

Bubbler 10/09/2018.

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

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} \$

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

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

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

.

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

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

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

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

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} \$

Post Left Garf Hunter 10/11/2018.

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

maxb 10/08/2018.

`{î)f*+`

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

Arnav Borborah 10/09/2018.

`vyiNÌÅfO`

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!

JosiahRyanW 10/07/2018.

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

Takes input through STDIN as a string.

Galen Ivanov 10/08/2018.

```
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]
```

Multi 10/08/2018.

Rogem 10/08/2018.

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;}`

0 ' 10/09/2018.

```
\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}.
```

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

Neil 10/07/2018.

```
0?
;
+`1;(1*);
;1$1;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*);
;1$1;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`

. `1`

s 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 `1`

s.

Arnauld 10/08/2018.

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

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`

Mego 10/08/2018.

`;r⌐@░♂FΣ`

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

mazzy 10/08/2018.

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

Luke Stevens 10/09/2018.

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;}`

**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
}
```

Logern 10/10/2018.

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

- Convert to and from the factorial number system
- Generate cyclic numbers in decimal
- Write a Number as a Fibonacci Sum
- Convert from base 10 to base 2 without built-in base conversions
- In what base this string equals the following decimal value?
- Summation under Zeckendorf Representation
- Have you learned your fib-abc?
- Convert to and from the backwards-factorial number base
- Find the closest Fibonacci Number
- Is this number secretly Fibonacci?
- The minimum fibonacci challenge!
- Summation under Zeckendorf Representation

- As a course lecturer, should I excuse late assignment submissions if I wrote the assignment deadline slightly wrong?
- How to avoid being labelled as paranoid when sharing concerns?
- How do I make around-the-room shelves for a seriously skewed room?
- Aren't the guidelines of async/await usage in C# contradicting the concepts of good architecture and abstraction layering?
- What is the formula for pi used in the Python decimal library?
- Why is <= slower than < in V8?
- What does the Verb きれる mean here?
- How to compare parts of files by hash?
- Is intraspecies genetic incompatibility possible?
- An object that is gold in one specific area but becomes worthless if you leave that area?
- Why would an attacker ever want to sit on a zero-day exploit?
- How can the common citizen defend democracy principles?
- Can my players abuse this homebrew Blade of the Thirst magic item?
- Should the UPS output be exactly same in normal and battery backup modes ? Or it is normal to have a slight variation in voltage or something?
- Can I resubmit my accepted paper after I withdraw it from the same journal?
- How can I measure the weight of my cat?
- What is the meaning of "Rumgejuxe"?
- Changing colour of imported SVG icon in QGIS 3.4
- Should log files be kept secret?
- How to know which command is being executed without stopping it?
- A simple finite combinatorial sum I found, that seems to work, would have good reasons to work, but I can't find in the literature.
- What was the first mainstream advanced debugger?
- Why doesn't a braking car move backwards?
- Is it acceptable to publish student names with the label 'stupid question', on a publicly-visible website?