Problem 47058. Determine the Zeckendorf expansion of a number

Created by ChrisR

Solve Later

{"parts":[{"partUri":"/matlab/document.xml","contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?><w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>The </w:t></w:r><w:hyperlink w:docLocation=\"https://en.wikipedia.org/wiki/Goldbach%27s_conjecture\"><w:r><w:t>Goldbach conjecture</w:t></w:r></w:hyperlink><w:r><w:t> deals with expressing integers as sums of primes. One might also seek to express integers as sums of other numbers, such as the </w:t></w:r><w:hyperlink w:docLocation=\"https://en.wikipedia.org/wiki/Fibonacci_number\"><w:r><w:t>Fibonacci numbers</w:t></w:r></w:hyperlink><w:r><w:t>, which begin 0, 1, 1, 2, 3, 5, 8, 13, 21... For example, 26 can be written as 13+8+5 or 21+3+2. </w:t></w:r><w:hyperlink w:docLocation=\"https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem\"><w:r><w:t>Zeckendorf</w:t></w:r></w:hyperlink><w:r><w:t> (and Lekkerkerker before him) showed that every positive integer can be uniquely expressed as the sum of </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>non-consecutive</w:t></w:r><w:r><w:t> Fibonacci numbers. The Zeckendorf expansion for 26 is 21+5. </w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>Write a function to determine the Zeckendorf expansion of the input number. In particular, output in decreasing order the Fibonacci numbers to be used in the sum.</w:t></w:r></w:p></w:body></w:document>","relationship":null}],"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","target":"/matlab/document.xml","relationshipId":"rId1"}]}

<div style = "text-align: start; line-height: 20.4333px; min-height: 0px; white-space: normal; color: rgb(0, 0, 0); font-family: Menlo, Monaco, Consolas, monospace; font-style: normal; font-size: 14px; font-weight: 400; text-decoration: rgb(0, 0, 0); white-space: normal; "><div style="block-size: 135px; display: block; min-width: 0px; padding-block-start: 0px; padding-top: 0px; perspective-origin: 407px 67.5px; transform-origin: 407px 67.5px; vertical-align: baseline; "><div style="block-size: 84px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 42px; text-align: left; transform-origin: 384px 42px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 14px 8.05px; transform-origin: 14px 8.05px; unicode-bidi: normal; "><span style="">The </span></span><a target='_blank' href = "https://en.wikipedia.org/wiki/Goldbach%27s_conjecture"><span style=""><span style="">Goldbach conjecture</span></span></a><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 294.442px 8.05px; transform-origin: 294.442px 8.05px; unicode-bidi: normal; "><span style=""> deals with expressing integers as sums of primes. One might also seek to express integers as sums of other numbers, such as the </span></span><a target='_blank' href = "https://en.wikipedia.org/wiki/Fibonacci_number"><span style=""><span style="">Fibonacci numbers</span></span></a><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 199.892px 8.05px; transform-origin: 199.892px 8.05px; unicode-bidi: normal; "><span style="">, which begin 0, 1, 1, 2, 3, 5, 8, 13, 21... For example, 26 can be written as 13+8+5 or 21+3+2. </span></span><a target='_blank' href = "https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem"><span style=""><span style="">Zeckendorf</span></span></a><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 255.608px 8.05px; transform-origin: 255.608px 8.05px; unicode-bidi: normal; "><span style=""> (and Lekkerkerker before him) showed that every positive integer can be uniquely expressed as the sum of </span></span><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 50.9667px 8.05px; transform-origin: 50.9667px 8.05px; unicode-bidi: normal; "><span style="font-style: italic; ">non-consecutive</span></span><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 196.242px 8.05px; transform-origin: 196.242px 8.05px; unicode-bidi: normal; "><span style=""> Fibonacci numbers. The Zeckendorf expansion for 26 is 21+5. </span></span></div><div style="block-size: 42px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 21px; text-align: left; transform-origin: 384px 21px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 372.5px 8.05px; transform-origin: 372.5px 8.05px; unicode-bidi: normal; "><span style="">Write a function to determine the Zeckendorf expansion of the input number. In particular, output in decreasing order the Fibonacci numbers to be used in the sum.</span></span></div></div></div>

Solve

Solution Stats

34 Solutions
8 Solvers

Last Solution submitted on Nov 25, 2020

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

mahesh P kumar on 24 Oct 2020

please improve the solution..

Problem Recent Solvers8

Problem Tags

fibonacci greedy sum

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 47058. Determine the Zeckendorf expansion of a number

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers8

Suggested Problems

More from this Author50

Problem Tags

Community Treasure Hunt

Problem 47058. Determine the Zeckendorf expansion of a number

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers8

Suggested Problems

More from this Author50

Problem Tags

Community Treasure Hunt

Players