Problem 44481. How many Fibonacci numbers?

Created by Bob Tivnan

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Find the number of unique Fibonacci numbers (don't count repeats) in a vector of positive integers.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Example:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ x = [1 2 3 4 5 6 7 8 8]\n y = 5]]></w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

1078 Solutions
268 Solvers

Last Solution submitted on Sep 10, 2021

Last 200 Solutions

Problem Comments

7 Comments

7 Comments

Show 4 older comments

Ahmos Sansom on 15 Jan 2018

Hello,

As soon as I do test 3, the 499th fibonacci term with 104 digits is converted to a double - should the test be char or strings for the inputs?

if I use int2str() it loses some of the accuracy...

David Verrelli on 17 Jan 2018

Hello, Bob Tivnan. I agree with Ahmos Sansom that there is a flaw in the current Test Suite. The problem is demonstrated in "Solution 1418487". Please address this, either by changing the input data type (not my preference) or by using numbers with precision compatible with double or uint64 data type (my preference). . . . If you are concerned about hard-coded 'solutions' (e.g. "Solution 1418491"), then you should add more tests to your Test Suite, and can also implement random permuting of the order of elements within each of your specified input vectors.
—DIV

David Verrelli on 17 Jan 2018

By the way, this might be avoided if you develop your own reliable Reference Solution beforehand.

Bob Tivnan on 1 Feb 2018

David Verrelli, my reference test suite passes without the problem you mention.

Ahmos Sansom on 2 Feb 2018

what happens if you change the last digit - does it still pass?

i.e:
x = [2 2 3 3 3 3 3 3 5 5 6 6 6 7 86168291600238450732788312165664788095941068326060883324529903470149056115823592713458328176574447204501];

x = [2 2 3 3 3 3 3 3 5 5 6 6 6 7 86168291600238450732788312165664788095941068326060883324529903470149056115823592713458328176574447204500];

Alfonso Nieto-Castanon on 6 Feb 2019

Hi Bob, in the last testsuite problem the last element in your x vector cannot be properly represented using double precision (t will be indistinguishable from similar numbers differing by anything within the last 88 digits). Please either switch to using other suitable representations (e.g. java big integers) or modify the testsuite to keep the values there a bit smaller (double precision can reasonably work with integers below ~1e15 and int64 could go up to ~1e20)

Ned Gulley on 8 Feb 2019

I went ahead and changed the test suite so the last number can be safely represented as an integer in double precision floating point.

Solution Comments

Solution 5100392

2 Comments

2 Comments

RAHUL DEY on 18 Mar 2021

Any ideas why this keeps failing Test 3 while it works perfectly on my PC?

goc3 on 18 Mar 2021

@RAHUL DEY: Are you sure that your solution gives you the correct answer for test 3 on your PC? When I run your solution on tests 3 and 4, they both give me the same result (correct for test 4, but not for test 3).

Note what Alfonso Nieto-Castanon mentioned in a comment on this problem: "double precision can reasonably work with integers below ~1e15." The method you are using squares the values in x, which makes that large number (about 8.9e15) equal to about 8e31, which is beyond the allowable precision in double values, causing what should be different values to appear the same. That is why you solution returns the same result for tests 3 and 4. You'll have to find a different method that does not rely upon squaring (or otherwise increasing) the values of x.

Solution 1412076

1 Comment

1 Comment

Bob Tivnan on 11 Jan 2018

Your solution was the first one to work! However, I changed the test suite and your code did not pass the new test. I basically added a really really big fibonacci number. Can you modify your code to make it work?

Problem Recent Solvers268

Problem Tags

fibonacci integers

Community Treasure Hunt

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

Start Hunting!