Introducing Zeckendorf - A possible New Problem
Back to General discussions forum
This is a must for all fans of Fibonacci numbers.
Rodion, the files are in your e-mail.
Clive, thanks a lot!
The problem is online! I suspect it is related to Fibonacci Numerals as in this task but I never knew the principle bears the name of matematician!
Moreover thanks that diving into mailbox I found a letter from Mathias also! Very sorry, it looks I wasn't checking mail for more than two weeks. Hopefully yet another problem about bunnies will come live soon!
CSFPython, many thanks for the Zeckendorf problem. When I first read the title, I thought it might be about a village of ticks :) - I had never heard about that mathematician before.
And Rodion, many thanks for publishing the egg throwing problem.
Just in time for Easter!
For those who want to have a go, think about a solution that works in O(N) for any input.
Rodion, thanks for posting the problem so quickly; and Mathias, thanks for another installment in the saga of the Easter Bunnies.
Introducing Zeckendorf is intended to be the first of 3 problems on the Zeckendorf theme.
Hi Experts,
As an example, let's take the number 858239231427506638.
test engine answer - [1, 8, 55, 46368, 317811, 832040, 24157817, 102334155, 2971215073, 7778742049, 591286729879, 2504730781961, 27777890035288, 117669030460994, 308061521170129, 806515533049393, 2111485077978050, 14472334024676221, 160500643816367088, 679891637638612258]
my answer - [2, 8, 55, 377, 1597, 4181, 28657, 196418, 514229, 1346269, 3524578, 14930352, 102334155, 2971215073, 7778742049, 591286729881, 2504730781970, 27777890035407, 117669030461521, 308061521171549, 806515533053216, 2111485077988334, 14472334024750472, 160500643817242656, 679891637642453632]
both answers fulfil the conditions. But my answer wrong. Can anyone please explain the situation.
Cheers, Sam.
Are your numbers really all Fibonacci numbers? Looking at your code, I think you use a formula to approximate Fibonacci numbers. Calculate them directly instead.
@gardengnome yes, it worked. Thanks for the tip. Sometimes I wonder how do you guys write a code with just 5,6 line, for the same taks I normaly write 15-25 lines. :-)
It took me quite a time to figure out why Mathias talks about "Village of Ticks" :) It's cool to have multi-lingual community! Now I wonder why really Dr Zeckendorf had such a funny last name.
Meanwhile I composed myself enough to try working on solutions for first two Zeckendorf's problems, and found that the "introduction" allows even simpler solution than I initially thought.
Frustrated a bit by this fact I dared to compose the fourth small problem on the topic. Regretfully it still allows lazy workaround in languages like Python, but preventing this will require inputs of many thousand digits, which I deem inconvenient. So let it be as is and perhaps let everyone choose the way of solving it.
This is a really amusing problem which really makes the most of Mathias' initial interpretation of the word Zeckendorf. The solution which I suppose that you have in mind is not very much harder than what you describe as the lazy solution. Although I thought of two different lazy approaches (one much better than the other) I opted to go for a solution which doesn't require the use of any numbers larger than single digits. This was a fun problem!
Hi, I think this problem might be trickier than anticipated (intended?), and thus I went for the lazy option
(for now anyway). There are special cases that need to be handled carefully (e.g. 1+1 or 10+10).
yes, noticed them (special cases) myself bit too late, but luckily it appeared they are simply resolved (well, not sure though my code is the brilliant of efficiency)
I recognised the situations for 1+1 and 10+10 as presenting problems (along with others which decompose into these). My lazy solution would provide an answer for these but I don't think the answer is compatible with what we are given for the Zeke behaviours. I think that these situations are not resolvable and assumed that the problems set would always avoid them. That certainly seemed to be the case for the small number of data sets which I checked.
My solution is based on the described behaviour and would crash if one of these problems arose. Without specific details of how to deal with these issues I thought it best to assume that they would never arise.
Random fact: Peter Fenwick did some research on this 20 years ago, published in Fibonacci Quarterly (where else :) ) - you might recognise his name from Fenwick Trees.
Hm-m-m... I definitely remember the name of Fenwick Tree though can't remember what it is about. Surprisingly it seems to be about structure for calculating frequencies in adaptive arithmetic coding :))) Very cool, probably it may be the idea for yet another small and dull but perhaps useful exercise, thank you :)
P.S. I remember there existed journal/magazine for example about the Game of Life on peak of interest to it... But special periodical dedicated to Fibonacci sequence... Big surprise :)
Hi, yes I found the connection to the adaptive arithmetic coding frequency calculations also amusing; quite a coincidence. Btw, you might have mail ...
Thanks for the hint! I see colleague Vladimir already successfully tested your new problem :)