Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Excuse my incorrect use of terminology, I hope my question is clear:

I am coding a Python module which tests whether a given number is a member of the Fibonacci series. No problem with that. Additionally, should a number not be a member of the series, I would like to test whether it is significantly close to its nearest Fibonacci neighbor. Here an increasing deviation margin of what is considered "close" is needed, along the lines of:

deviation margin (x) increases as given number (n) increases

For my purposes 9 is significantly close to Fibonacci number 8 but 10 is not. 1600 is significantly close to Fibonacci number 1597 but 1610 is not, etc. So, the test for "significant closeness" is applying a deviation margin of 1 at lower numbers and an increasing deviation margin as the series increments up to infinity.

I figured a logical candidate for inclusion in the test would be Standard Deviation. So I have calculated a coarse margin as follows:

margin = (StdDev / ( n + closestfibneighbor)) * StdDev

This does not give me good control over the margin rate of increase and I am sure there is a more appropriate function to express the growth in margin caused by increments in x. Please feel free to elaborate on the mathematics of this - I am seeking a general solution and not a Python-specific function.

share|improve this question
    
The obvious thing would be to have the margin be a fixed percentage of $n$, say $1\%$ or something like that, but that doesn't work with your numbers. So you need to be more precise about how quickly or slowly you want the margins to increase. How did you decide that $1610$ is not "significantly close" to $1597$? Edit: You could just make the margin be $1+0.01n$... –  Rahul Feb 19 '13 at 6:13
    
Thank you for the suggestion - perhaps I am overcomplicating the matter by trying to use StdDev, but the problem got me thinking about exponential growth and a succinct mathematical function to express this ... percentage is perhaps a viable solution, since my personal idea of "closeness" is what made me consider 1610 to be an outlier - probably based on some intuitive notion of percentage or Fib ratio :) –  venzen Feb 19 '13 at 6:17
    
ℝⁿ. please put your latest suggestion as an answer –  venzen Feb 24 '13 at 16:31
add comment

2 Answers

up vote 2 down vote accepted

The Fibonacci numbers, the larger ones in particular, are very close to being given by the formula $$ F_n\approx\frac1{\sqrt5} \left(\frac{1+\sqrt5}2\right)^n $$ ($F_n$ is always the closest integer to the r.h.s.). In light of this I would also consider calculating, given input $x$, how far the ratio $$ r(x):=\frac{\log(x\cdot\sqrt5)}{\log\big((1+\sqrt5)/2\big)} $$ is from being an integer. In other words, I might use the number $$ s(x)=\left|r(x)-round(r(x))\right| $$ for measuring how far $x$ is from being a Fibonacci number.

The point is that a test based on Binet's formula should be faster than anything recursive. Of course, you need very precise floating point operations to be able to use that as a test, whether an integer $x$ actually is a Fibonacci number: compute $r(x)$, and find whether $$ x=round\left(\frac1{\sqrt5} \left(\frac{1+\sqrt5}2\right)^{round(r(x))}\right). $$

share|improve this answer
    
Jyrki, thank you for your answer - this is extremely useful. Having provided an impressive exposition on the calculation of Fib numbers and 'closeness' to being a Fib series member, could you perhaps elaborate on how to best construct a simple formula for determining (and controlling) a measurement margin of closeness? I am, for example, unfamiliar with the meaning of r(x)... –  venzen Feb 28 '13 at 10:11
    
@venzen, I define $r(x)$ on line five. –  Jyrki Lahtonen Feb 28 '13 at 11:06
    
thank you @Jyrki, suddenly the notation is clear! I will code, test and provide feedback over the weekend, –  venzen Feb 28 '13 at 14:25
    
@venzen: Please do! Sorry about not making it clear right away that the definition of $r(x)$ basically want to solve $n$ from the first equation. I'm a bit curious about how well this will work. It may turn out that the percentage scale (of the other answer) is too crude also, and this may be too. I mean, in a percentage scale 9 is about as close to 8 as 1700 is to 1597. We may still need to adjust it somewhat (like allowing a logarithmis error only). –  Jyrki Lahtonen Feb 28 '13 at 14:35
1  
@venzen: By the way, for any fixed threshold $t$, you have $s(x)\le t$ if and only if $x$ is between $\phi^{-t}$ and $\phi^t$ times the nearest Fibonacci number, where $\phi=(1+\sqrt5)/2$. In particular, $t=0.1$ corresponds to a range of about $5\%$. So this is not as different from my suggestion as it appears. :) –  Rahul Mar 6 '13 at 11:22
show 2 more comments

A suitable solution (suggested by Rahul Narain) is to simply calculate the margin as a fixed percentage of each successive Fibonacci number in the series:

margin = 1 + 0.01n

This gives the desired outcome of allowing a margin of ~1 at the lowest Fib numbers and an increasing margin as the series increments. In the spirit of the Fib series I calculate the margin as 13% of n instead of 10%.

Using standard deviation as a variable in this specific context is not elegant since a percentage of Std Dev will have to be applied in a working solution anyway.

share|improve this answer
    
Prefered the excellent answer by Jyrki Lahtonen since his solution allows very precise control wrt the proximity margin. This answer, whilst simple, is very functional yet without the control of margin variance which was one of my requirements. –  venzen Mar 6 '13 at 3:15
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.