45
$\begingroup$

Problem #25 from Project Euler asks:

What is the first term in the Fibonacci sequence to contain 1000 digits?

The brute force way of solving this is by simply telling the computer to generate Fibonacci numbers until it finds the first one that has 1000 digits. I wanted to look for a more mathematical solution that doesn't require that many computations.

Initially, I expected that by plotting the Fibonacci numbers (mapping the number itself to the number of digits) I would get a logarithmic graph. I only plotted the first few ones and the sequence looked more like it had linear progression (I hope that's the correct mathematical term; I mean similar to $y=x$ functions.)

I also noticed that, roughly, every five numbers the number of digits is increased by 1 — except the four digit numbers (there's only four of them) and the one digits numbers (if you count the first 1, there's six of them).

$$1, 1, 2, 3, 5, 8$$ $$13, 21, 34, 55, 89$$ $$144, 233, 377, 610, 987$$ $$1597, 2584, 4181, 6765$$ $$10946, ...$$

Thus, the first number with seven digits would be $n = 5 \cdot (7 - 1)$, which turned out to be correct. However, starting with the tenth digit, the behavior of the sequence changes (or rather, it becomes clear that it's not linear). The first number with 10 digits is not $5 \cdot (10 -1)$, but $5 \cdot (10 - 1) - 1$.

Plotting the sequence for even larger numbers (again, numbers mapped to their digit count), you get a very slight logarithmic curve. For example, the first number with 1000 digits is $5 \cdot (1000 - 43)$ (WolframAlpha).

My question is,
How can the Fibonacci sequence's behavior be abstracted such that the problem can be solved more elegantly, as opposed to using the brute force algorithm.

Edit: Regarding efficiency

The question, I asked mainly to satisfy my curiosity. Doing this by brute-force is probably the best way in a real world application (computers can do it fast and the code is clearer). But (again, just for entertainment) the more efficient solution can still be to use a mathematical formula to find the index of the number you're looking for; here's why:

  1. Conditionals are expensive. Doing fewer of them is always good, and the brute-force approach requires you to do a check on every number you generate.
  2. Some languages (like C++ and D) allow you to do tricks like generating part of the Fibonacci sequence at compile-time (see meta-programming). This means less work at run-time, though admittedly, this could also apply to the brute-force approach.

Not doing checks on the numbers, as well as generating many of them at compile time, can significantly make the algorithm faster (but only in a theoretical sense; most computers nowadays are fast enough that no human will ever notice the difference unless you do the computations a couple of times a second).

Besides, the process of counting the digits of a numbers — required by the brute-force approach — is itself pretty expensive, whether you use the $\lceil\log_{10}n \rceil$ algorithm or the $n\mod10$ algorithm.

$\endgroup$
5
  • 16
    $\begingroup$ (+1) "This question shows research effort; it is useful and clear" Check. Check. Check. $\endgroup$
    – The Chaz 2.0
    Sep 4, 2011 at 15:58
  • $\begingroup$ See also math.stackexchange.com/questions/9026. $\endgroup$
    – Mike Spivey
    Sep 6, 2011 at 3:23
  • $\begingroup$ Why are you using the log or mod to check the number of digits? It's probably a lot faster to check if the number is greater than 10^1000. Subtracting and checking if the result is negative is surely a lot faster than taking the log or the modulo of a 1000 digit number. $\endgroup$
    – Hannesh
    Sep 6, 2011 at 10:24
  • $\begingroup$ @Hannesh I know, but I was talking about a more general algorithm that counts the digits, not one that checks whether a number is within a certain range. $\endgroup$
    – Paul Manta
    Sep 6, 2011 at 10:30
  • $\begingroup$ Hannes: 10^999 has 1000 digits :-) $\endgroup$
    – gnasher729
    Mar 30 at 16:28

7 Answers 7

Reset to default
12
$\begingroup$

The sequence $n \mapsto F_n$ grows exponentially. In fact, I suggest you look at this part of the wikipedia article on Fibonacci numbers, which gives exact and nearly exact formulas for $F_n$ as exponential functions. This should be very helpful in determining the smallest $n$ such that $F_n$ has $1000$ digits.

$\endgroup$
14
  • 2
    $\begingroup$ @Paul: sorry, you said that in your question but I missed it. Right, so $n \mapsto F_n$ is exponential and thus $n \mapsto d(F_n) \approx \log_{10} F_n$ is linear. Anyway, the point of my answer is not just that $F_n$ is exponential but is given up to the nearest integer by a very simple exponential expression, such that you can set it equal to $10^{1000}$ and solve for $n$. Does this make sense? $\endgroup$
    – Pete L. Clark
    Sep 4, 2011 at 8:28
  • 2
    $\begingroup$ Addendum to the above: when I say "solve for $n$", I mean that first you solve some equation that gives you a value of $n$ which is very nearly correct but not necessarily even an integer, and then you check nearby integers to see which one you want. I really don't want to say more than this, except that in between typing the above answer and this comment I decided to try the procedure out for myself...it works! $\endgroup$
    – Pete L. Clark
    Sep 4, 2011 at 8:41
  • 2
    $\begingroup$ Also note that $10^{1000}$ has $1001$ digits (I confess I missed this the first time around!) so that one might speed things up a little bit more by trying $10^{999}$ instead. But if you have access to something which will spit out values of $F_n$ for $n$ in the thousands, either way is already very fast... $\endgroup$
    – Pete L. Clark
    Sep 4, 2011 at 8:55
  • 4
    $\begingroup$ @Pete, the Project Euler problems are posed as programming/algorithmic exercises -- the task is really to figure out how to produce the thing they ask for. Just asking Wolfram Alpha for the solution instead of actually solving the problem posed is not going to be any more educational than cheating on a test or bribing a teacher to pass you. It doesn't matter that not solving the problem "seems more efficient" than solving it -- otherwise, what would be the point in participating at all in the first place? $\endgroup$
    – hmakholm left over Monica
    Sep 4, 2011 at 16:10
  • 1
    $\begingroup$ @Henning: okay, I take your point. I am a mathematician, not a computer scientist (and this is a math site...) so I was answering the question in that context. I agree that when I looked into the computations myself I used gp/pari, which has a built-in "fibonacci" function. Following your comment I tried using the rounded Binet's formula instead, and indeed I got not nearly enough digits of precision. $\endgroup$
    – Pete L. Clark
    Sep 4, 2011 at 16:18
12
$\begingroup$

The $n$-th Fibonacci number is given by the following formula: $$F_n = \left\lfloor \frac{\phi^n}{\sqrt 5} + \frac12 \right\rfloor,$$ where $\displaystyle\varphi = \frac{1+\sqrt 5}{2}$. Equivalently, $F_n$ is the integer closest to $\displaystyle\frac{\varphi^n}{\sqrt 5}$. Thus, $\log_{10}F_n$ is very, very close to $\displaystyle n \log_{10}\varphi - \frac12 \log_{10}5$. Since the number of digits in the integer $m$ is $\lceil\log_{10}m \rceil$, so $-$ ignoring that very small discrepancy, which shouldn’t matter with numbers of this size $-$ you want the smallest $n$ such that $$\displaystyle n \log_{10}\varphi - \frac12 \log_{10}5 > 999.5.$$

Added: I guessed wrong about the effect of the discrepancy. By actual calculation it turns out that the value estimated from the inequality above is a little too small.

$\endgroup$
7
  • $\begingroup$ I'm not quite sure why you have 999.5 rather than 1000. $\endgroup$
    – Henry
    Sep 4, 2011 at 8:48
  • $\begingroup$ @Henry: Because I wanted the ceiling of the number on the left-hand side to be at least $1000$, which means that the number itself must be more than $999.5$. $\endgroup$
    – Brian M. Scott
    Sep 4, 2011 at 9:05
  • $\begingroup$ I still do not see it. First ceilings do not work like that. Second you want the left hand side to be greater than $\log(10^{1000})$ so you do not need ceilings at this stage. Later you could have $n=\text{ceiling} \left[ \dfrac{1000 + \frac12 \log_{10}5 }{\log_{10}\varphi} \right]$. I think this works for two or more digits. $\endgroup$
    – Henry
    Sep 4, 2011 at 9:38
  • $\begingroup$ This answer (with @Henry's correction) is true as far as it goes, but does it actually help find the actual Fibonacci number asked for? Ordinary computer floating-point arithmetic is not precise enough to find all the 1000 digits of the number simply by taking a power of $\phi$, so one has to execute the exact recurrence with bignums anyway after computing how far to go -- which is just the same work as the OP's original algorithm, except for the very minor step of checking for each $F_n$ whether we've reached $10^{1000}$ or not. $\endgroup$
    – hmakholm left over Monica
    Sep 4, 2011 at 15:37
  • 3
    $\begingroup$ @Henning: the format of the desired answer has been questioned several times, and the Project Euler guidance is clear. $\endgroup$
    – Henry
    Sep 4, 2011 at 22:51
7
$\begingroup$

Here is a useful fact, for any positive number n, the number of digits of n in base 10 is given by:

$$\lfloor\log_{10}(n)\rfloor + 1$$

The number of digits of the Fibonacci sequence grows linearly, as can be shown in the graph.

plot of number of digits of Fibonacci numbers

$\endgroup$
1
  • 18
    $\begingroup$ I particularly like the plot of the imaginary part. $\endgroup$
    – RoundTower
    Sep 4, 2011 at 11:43
1
$\begingroup$

The other answers giving exact forumlas for Fibonacci numbers are spot on, but if you don't have them handy, you can also solve this problem by shifting the computation to the logarithmic domain. Calculate the log, base 10, of each number, and add it to a double-precision sum; as soon as the value equals or exceeds 999 (i.e. the log, base 10, of the lowest number with 1000 digits), you've reached the right Fibonacci number.

$\endgroup$
1
$\begingroup$

The answers you have got so far will help you finding the index of the first Fibonacci number greater than $10^{999}$, but are not particularly useful for finding that Fibonacci number itself, with all is 1000 digits.

For that, I think you have no choice but compute the Fibonacci sequence far enough. If you know the index in advance you can use that to decide how far to go in the computation, but that does not seem to be a significant improvement over simply checking whether each successive Fibonacci number has reached 1000 digits -- you need to compute them all anyway.

The point of the exercise must be that a naive implementation of the Fibonacci sequence (top-down, with two recursive calls in each step) is not going to complete for these sized until well after the heat death of the universe. But if you compute the sequence from the bottom up, saving all of them in an array, and simply pull the two previous numbers out of the array at each step, it's all fast and straightforward.

(You'll need an arbitrary-precision integer arithmetic library if your programming language doesn't already provide one, of course).

$\endgroup$
10
  • 3
    $\begingroup$ ...or he could do a matrix exponentiation of an appropriate matrix. $\endgroup$
    – J. M. ain't a mathematician
    Sep 4, 2011 at 15:52
  • 1
    $\begingroup$ @J, yes, but will be more programming work for a dubious benefit unless he has a library that handles both matrix exponentiation and arbitrary-precision arithmetic in one integrated package. The straightforward iterative solution will take $O(n^2)$ time, and ought to complete in comfortably less than a minute. Under the (perhaps not completely realistic) assumption that the library has a sub-quadratic multiplication algorithm, matrix exponentiation by squaring would get down to about $O(n\log^2(n))$, but it seems not to be worth the trouble. $\endgroup$
    – hmakholm left over Monica
    Sep 4, 2011 at 15:58
  • 1
    $\begingroup$ The problem cited asks for the index, not the term itself. $\endgroup$
    – Ross Millikan
    Sep 4, 2011 at 19:22
  • 2
    $\begingroup$ @Henning Makholm: You are right that the quote is accurate, but the answer it accepted from me was the term number. The answer box won't hold 1000 digits (many problems ask for the last 8 digits of a big number). I believe there was discussion on the forum suggesting rewording, but it hasn't happened. $\endgroup$
    – Ross Millikan
    Sep 4, 2011 at 21:26
  • 1
    $\begingroup$ The matrix exponentiation gives the insight needed to produce a simple and efficient recursive evaluation method. cheddarmonk.org/Fibonacci.html $\endgroup$
    – Peter Taylor
    Sep 6, 2011 at 8:48
0
$\begingroup$

The brute force method IS the elegant method. Compare the gyrations and convolutions above to: find each Fibonnaci number in sequence, count the number of digits, stop at the first one with 1,000 digits (if any).

$\endgroup$
6
  • 1
    $\begingroup$ You're right, that method is much better than it looks at first glance. $\endgroup$
    – Charles
    Sep 4, 2011 at 16:40
  • $\begingroup$ "If any"? Since $F_{n+1}$ is extremely close to $((1+\sqrt{5})/2) \cdot F_n$, it is clear that except for very small $d$ (in fact $d \geq 2$ suffices) there are either $4$ or $5$ Fibonacci numbers with $d$ digits. Maybe the gyrations are not so bad after all? $\endgroup$
    – Pete L. Clark
    Sep 4, 2011 at 16:45
  • $\begingroup$ Patrick: would you make the same statement in (say) 1950? I don't think brute force is at all elegant; it's just convenient and simple in a time where we have easy access to cheap powerful computing resources. $\endgroup$
    – Fixee
    Sep 4, 2011 at 17:02
  • 1
    $\begingroup$ @Fixee, even in 1950, if you were asked to compute the first Fibonacci number that had 1000 digits, that's what you had to do. Knowing the index of that number in the sequence is actually not going to simplify the computations for you. $\endgroup$
    – hmakholm left over Monica
    Sep 4, 2011 at 21:31
  • $\begingroup$ @Henning I asked the question to satisfy my curiosity, because brute force is completely uninteresting. :) Even so, for very large numbers the non-brute-force approach may be faster. Brute force implies doing a check on every number you generate, and conditionals are expensive. It might (theoretically) be better to know ahead of time how many numbers you have to generate, so you don't have to do any more checks. $\endgroup$
    – Paul Manta
    Sep 6, 2011 at 5:36
0
$\begingroup$

Violating both the terms of the question and good taste, I spent 1.5 minutes and wrote a program to solve this. Being a computer scientist, it was an irresistible temptation.

Python seems the logical choice for something quick: it has arbitrary precision integers built in.

Solution deleted due to comment below

$\endgroup$
8
  • $\begingroup$ In python, t = j; j += i; i = t can be written as i, j = j+i, i. Also, rather than calculate the log of j in every loop, I thought it would be quicker to just see if it's greater than or equal to 10 ** 999, but in tests, it made only a small difference. $\endgroup$
    – rjmunro
    Sep 4, 2011 at 23:34
  • $\begingroup$ @rjmunro: I had written i,j = j,j+1 originally, but changed it before posting here, hoping to avoid too much python-specific syntax so that C programmers would understand the code. (Btw, I don't think the two code snippets in your comment are equivalent.) Also, you're right that 10 **999 is probably a bit faster than a log, however that depends on how exponentiation is computed in python... it might be just as bad. I usually don't try optimizing in Python much; the language is horrendously slow (even jitted), so I'd never use for anything where I care about performance. $\endgroup$
    – Fixee
    Sep 5, 2011 at 0:15
  • $\begingroup$ It's not that 10**999 is faster than log(), it's that you only have to compute it once at the start. You are computing log(j) on every loop. $\endgroup$
    – rjmunro
    Sep 5, 2011 at 11:21
  • $\begingroup$ @rjmunro: Yup true. So inside the loop, we have to ask if it's faster to compute the log of a huge number or to compare one huge number to another. I'd have to think that the latter is much faster, as you suggested. (Though once again, I think talking about optimized Python is akin to talking about high-performance tricycles.) $\endgroup$
    – Fixee
    Sep 5, 2011 at 16:46
  • 1
    $\begingroup$ I can understand the temptation to solve the problem (I gave into that myself) but not the temptation to post the solution here, contrary to the instructions at Project Euler. Haven't you just spoiled the puzzle for a lot of (presumably young, non-professional computer scientist) people? $\endgroup$
    – Pete L. Clark
    Sep 5, 2011 at 21:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .