Converting a number from Zeckendorf Representation to Decimal

Clash Royale CLAN TAG#URR8PPP

up vote
4
down vote

favorite

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.

code-golf fibonacci

share|improve this question

edited 49 mins ago

W W

33.9k10150354

asked 1 hour ago

Windmill Cookies

316211

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Can we take input as a list of bits?
  – W W
  49 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Like, take the input ascii encoded then convert it to binary or something like that?
  – Windmill Cookies
  45 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I mean like taking [1,0,0] instead of "100".
  – W W
  44 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Yes, you can. For example the Jelly answer takes the input as a list
  – Windmill Cookies
  43 mins ago
  

  
  
  
  

add a comment | 

up vote
4
down vote

favorite

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.

code-golf fibonacci

share|improve this question

edited 49 mins ago

W W

33.9k10150354

asked 1 hour ago

Windmill Cookies

316211

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Can we take input as a list of bits?
  – W W
  49 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Like, take the input ascii encoded then convert it to binary or something like that?
  – Windmill Cookies
  45 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I mean like taking [1,0,0] instead of "100".
  – W W
  44 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Yes, you can. For example the Jelly answer takes the input as a list
  – Windmill Cookies
  43 mins ago
  

  
  
  
  

add a comment | 

up vote
4
down vote

favorite

up vote
4
down vote

favorite

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.

code-golf fibonacci

share|improve this question

edited 49 mins ago

W W

33.9k10150354

asked 1 hour ago

Windmill Cookies

316211

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.

code-golf fibonacci

code-golf fibonacci

share|improve this question

edited 49 mins ago

W W

33.9k10150354

asked 1 hour ago

Windmill Cookies

316211

share|improve this question

edited 49 mins ago

W W

33.9k10150354

asked 1 hour ago

Windmill Cookies

316211

share|improve this question

share|improve this question

edited 49 mins ago

W W

33.9k10150354

edited 49 mins ago

W W

33.9k10150354

edited 49 mins ago

W W

33.9k10150354

33.9k10150354

asked 1 hour ago

Windmill Cookies

316211

asked 1 hour ago

Windmill Cookies

316211

asked 1 hour ago

Windmill Cookies

316211

316211

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Can we take input as a list of bits?
  – W W
  49 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Like, take the input ascii encoded then convert it to binary or something like that?
  – Windmill Cookies
  45 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I mean like taking [1,0,0] instead of "100".
  – W W
  44 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Yes, you can. For example the Jelly answer takes the input as a list
  – Windmill Cookies
  43 mins ago
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Can we take input as a list of bits?
  – W W
  49 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Like, take the input ascii encoded then convert it to binary or something like that?
  – Windmill Cookies
  45 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I mean like taking [1,0,0] instead of "100".
  – W W
  44 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Yes, you can. For example the Jelly answer takes the input as a list
  – Windmill Cookies
  43 mins ago
  

  
  
  
  

Can we take input as a list of bits?
– W W
49 mins ago

Can we take input as a list of bits?
– W W
49 mins ago

Like, take the input ascii encoded then convert it to binary or something like that?
– Windmill Cookies
45 mins ago

Like, take the input ascii encoded then convert it to binary or something like that?
– Windmill Cookies
45 mins ago

I mean like taking [1,0,0] instead of "100".
– W W
44 mins ago

I mean like taking [1,0,0] instead of "100".
– W W
44 mins ago

Yes, you can. For example the Jelly answer takes the input as a list
– Windmill Cookies
43 mins ago

Yes, you can. For example the Jelly answer takes the input as a list
– Windmill Cookies
43 mins ago

add a comment | 

4 Answers
4

active

oldest

votes

up vote
1
down vote

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.

share|improve this answer

answered 1 hour ago

xnor

87.5k17181433

add a comment | 

up vote
1
down vote

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.

share|improve this answer

answered 41 mins ago

W W

33.9k10150354

add a comment | 

up vote
1
down vote

Brain-Flak, 110, 102 bytes

()(<>)<>()(<(())>)<>()<>(<((())<([])>)>)<><>(())(<>)()<>(<>)

Try it online!

share|improve this answer

answered 19 mins ago

W W

33.9k10150354

add a comment | 

up vote
0
down vote

Jelly, 6 bytes

ṚT‘ÆḞS

A monadic link accepting a list.

Try it online!

share|improve this answer

answered 1 hour ago

Jonathan Allan

48.8k534161

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "200"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f173601%2fconverting-a-number-from-zeckendorf-representation-to-decimal%23new-answer', 'question_page');

);

Post as a guest

Name Email

4 Answers
4

active

oldest

votes

4 Answers
4

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
1
down vote

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.

share|improve this answer

answered 1 hour ago

xnor

87.5k17181433

add a comment | 

up vote
1
down vote

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.

share|improve this answer

answered 1 hour ago

xnor

87.5k17181433

add a comment | 

up vote
1
down vote

up vote
1
down vote

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.

share|improve this answer

answered 1 hour ago

xnor

87.5k17181433

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.

share|improve this answer

answered 1 hour ago

xnor

87.5k17181433

share|improve this answer

share|improve this answer

answered 1 hour ago

xnor

87.5k17181433

answered 1 hour ago

xnor

87.5k17181433

answered 1 hour ago

xnor

87.5k17181433

87.5k17181433

add a comment | 

add a comment | 

up vote
1
down vote

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.

share|improve this answer

answered 41 mins ago

W W

33.9k10150354

add a comment | 

up vote
1
down vote

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.

share|improve this answer

answered 41 mins ago

W W

33.9k10150354

add a comment | 

up vote
1
down vote

up vote
1
down vote

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.

share|improve this answer

answered 41 mins ago

W W

33.9k10150354

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.

share|improve this answer

answered 41 mins ago

W W

33.9k10150354

share|improve this answer

share|improve this answer

answered 41 mins ago

W W

33.9k10150354

answered 41 mins ago

W W

33.9k10150354

answered 41 mins ago

W W

33.9k10150354

33.9k10150354

add a comment | 

add a comment | 

up vote
1
down vote

Brain-Flak, 110, 102 bytes

()(<>)<>()(<(())>)<>()<>(<((())<([])>)>)<><>(())(<>)()<>(<>)

Try it online!

share|improve this answer

answered 19 mins ago

W W

33.9k10150354

add a comment | 

up vote
1
down vote

Brain-Flak, 110, 102 bytes

()(<>)<>()(<(())>)<>()<>(<((())<([])>)>)<><>(())(<>)()<>(<>)

Try it online!

share|improve this answer

answered 19 mins ago

W W

33.9k10150354

add a comment | 

up vote
1
down vote

up vote
1
down vote

Brain-Flak, 110, 102 bytes

()(<>)<>()(<(())>)<>()<>(<((())<([])>)>)<><>(())(<>)()<>(<>)

Try it online!

share|improve this answer

answered 19 mins ago

W W

33.9k10150354

Brain-Flak, 110, 102 bytes

()(<>)<>()(<(())>)<>()<>(<((())<([])>)>)<><>(())(<>)()<>(<>)

Try it online!

share|improve this answer

answered 19 mins ago

W W

33.9k10150354

share|improve this answer

share|improve this answer

answered 19 mins ago

W W

33.9k10150354

answered 19 mins ago

W W

33.9k10150354

answered 19 mins ago

W W

33.9k10150354

33.9k10150354

add a comment | 

add a comment | 

up vote
0
down vote

Jelly, 6 bytes

ṚT‘ÆḞS

A monadic link accepting a list.

Try it online!

share|improve this answer

answered 1 hour ago

Jonathan Allan

48.8k534161

add a comment | 

up vote
0
down vote

Jelly, 6 bytes

ṚT‘ÆḞS

A monadic link accepting a list.

Try it online!

share|improve this answer

answered 1 hour ago

Jonathan Allan

48.8k534161

add a comment | 

up vote
0
down vote

up vote
0
down vote

Jelly, 6 bytes

ṚT‘ÆḞS

A monadic link accepting a list.

Try it online!

share|improve this answer

answered 1 hour ago

Jonathan Allan

48.8k534161

Jelly, 6 bytes

ṚT‘ÆḞS

A monadic link accepting a list.

Try it online!

share|improve this answer

answered 1 hour ago

Jonathan Allan

48.8k534161

share|improve this answer

share|improve this answer

answered 1 hour ago

Jonathan Allan

48.8k534161

answered 1 hour ago

Jonathan Allan

48.8k534161

answered 1 hour ago

Jonathan Allan

48.8k534161

48.8k534161

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f173601%2fconverting-a-number-from-zeckendorf-representation-to-decimal%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email