Skip to main content
We’ve updated our Terms of Service. A new AI Addendum clarifies how Stack Overflow utilizes AI interactions.
Code Golf

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

Required fields*

Converting a number from Zeckendorf Representation to Decimal

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.

Answer*

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

AltStyle によって変換されたページ (->オリジナル) /