Return to Answer

@Zeta has pointed out one fact, which I did not consider relevant and thus I didn't mention it. If you implemented the original Binet's formula \$\frac{\phi^n-\psi^n}{\sqrt5}\$, and your function returned double or float instead of an integer type such as int or float, you would see that the result is incorrect due to floating-point errors. Here's an illustration of how incorrect the result would be:

@Zeta has pointed out one fact, which I did not consider relevant and thus I didn't mention it. If you implemented the original Binet's formula \$\frac{\phi^n-\psi^n}{\sqrt5}\$, and your function returned double or float instead of an integer type such as int or long, you would see that the result is incorrect due to floating-point errors. Here's an illustration of how incorrect the result would be:

\$498\ 454\ 011\ 879\ 264\ \$ is the first number for which the integral part of both results is not equal. If the rounding version is used, the result is incorrect starting with the previous tern \$308\ 061\ 521\ 170\ 129\$.

This is not a problem in this scenario, since we only need Fibonacci numbers which are less or equal to \$4\ 000\ 000\$. Moreover the function given above returns an int, which can only hold the maximum value of \$2^{31}-1\$, which is \$2\ 147\ 483\ 647\$ — well out of danger.

\$498\ 454\ 011\ 879\ 264\ \$ is the first number for which the integral part of both results is not equal. If the rounding version is used, the result is incorrect starting with the previous term \$308\ 061\ 521\ 170\ 129\$.

This is not a problem in our scenario, since we only need Fibonacci numbers which are less or equal to \$4\ 000\ 000\$. Moreover the function given above returns an int, for which the maximum possible value is \$2^{31}-1\$, which is \$2\ 147\ 483\ 647\$ — well out of danger.

So now we know how to calculate the index of the last Fibonacci number in our sum. Note that \$1\$ occurs in the sequence twice, but obviously this method can produce only one index.

EDIT

@Zeta has pointed out one fact, which I did not consider relevant and thus I didn't mention it. If you implemented the original Binet's formula \$\frac{\phi^n-\psi^n}{\sqrt5}\$, and your function returned double or float instead of an integer type such as int or float, you would see that the result is incorrect due to floating-point errors. Here's an illustration of how incorrect the result would be:

actual value [long]   Binet's formula [double]
3                     3.0000000000000004
5                     5.000000000000001
8                     8.000000000000002
⋮                    ⋮
498454011879264       498454011879265.2

\$498\ 454\ 011\ 879\ 264\ \$ is the first number for which the integral part of both results is not equal. If the rounding version is used, the result is incorrect starting with the previous tern \$308\ 061\ 521\ 170\ 129\$.

This is not a problem in this scenario, since we only need Fibonacci numbers which are less or equal to \$4\ 000\ 000\$. Moreover the function given above returns an int, which can only hold the maximum value of \$2^{31}-1\$, which is \$2\ 147\ 483\ 647\$ — well out of danger.

I would post a link to a now-classical paper by David Goldberg, What Every Computer Scientist Should Know About Floating-Point Arithmetic. But since it's not just some easy wikipedia-style reading, I doubt anybody would actually read it. It's no problem to google it if you're interested.

So now we know how to calculate the index of the last Fibonacci number in our sum.

Note that \$1\$ occurs in the sequence twice, but obviously this method can produce only one index.