This morning I was reading Terry Tao’s overview of the work of Yves Meyer and ran across this line:

The powers φ, φ

^{2}, φ^{3}, … of the golden ratio lie unexpectedly close to integers: for instance, φ^{11}= 199.005… is unusually close to 199.

I’d never heard that before, so I wrote a little code to see just how close golden powers are to integers.

Here’s a plot of the difference between φ^{n} and the nearest integer:

(Note that if you want to try this yourself, you need extended precision. Otherwise you’ll get strange numerical artifacts once φ^{n} is too large to represent exactly.)

By contrast, if we make the analogous plot replacing φ with π we see that the distance to the nearest integer looks like a uniform random variable:

The distance from powers of φ to the nearest integer decreases so fast that cannot see it in the graph for moderate sized *n*, which suggests we plot the difference on the log scale. (In fact we plot the log of the *absolute value* of the difference since the difference could be negative and the log undefined.) Here’s what we get:

After an initial rise, the curve is apparently a straight line on a log scale, i.e. the absolute distance to the nearest integer decreases almost exactly exponentially.

**Related posts**:

This happens because phi^n + (-phi)^(-n) is always an integer (you can prove this by induction in n). Hence the log of the absolute value of the difference being linear (it’s -n*log(phi).)

In this sense, phi is not so special; you can also try, for instance, 2+sqrt(3), or the largest root of a quadratic x^2 + ax + b = 0, a, b integers, such that the smallest root has absolute value smaller than 1.

This follows trivially from Binet’s formula for Fibonacci numbers.

Carlos and Theemathas:

Let x_n = phi^n + (-phi)^(-n). I see why x_n/sqrt(5) is near an integer — in fact it’s exactly an integer, the nth Fibonacci number — but I don’t see why x_n itself should be near an integer. Said another way, why should sqrt(5) times a Fibonacci number be nearly an integer?

Start with 1/√5 instead of 1 when repeatedly multiplying the powers of φ and near integers are also generated… although they’ll be a lot more familiar than the ones generated here (which are also fairly well known as it happens).

I have what I would consider an [moderately] unsurprising inductive proof of this convergence towards integers. Recall that the nth fibonacci number $f_n = \frac{\phi^n – (–\phi)^{–n}}/{\sqrt{5}}$. Since the second term decays exponentially, call that term $\epsilon_n$. Then we can say $\phi^n = \sqrt{5}(F_n – \epsilon_n)$. Now, the induction hypotheses are that for two consecutive n we have $\phi^n = z_n – (-1)^{n} \delta_n$ where $z_n$ is an integer and $\delta_n$ is positive and decreasing with n, and obeys a condition explained below.

Write $\phi^{n+1} = (F_{n+1} – \epsilon_{n+1})\sqrt{5}$. Use $F_{n+1}=F_n+F_{n–1}$ and substitute back to get $\phi^{n+1} = ( \phi^n/\sqrt{5} + \phi^{n-1}/\sqrt{5} + \epsilon_n + \epsilon_{n–1} – \epsilon_{n+1})\sqrt{5}$. The sum of the epsilons is exactly zero! So the square-roots of 5 cancel, and now invoke the induction hypothesis. $\phi^{n+1} = z_n + z_{n_1} – (-1)^{n} \delta_n – (-1)^{n–1} \delta_{n–1}$. So, we see $z_{n+1}$ is just $z_n + z_{n+1}$, and careful tracking of signs shows that $\delta_{n+1} = (\delta_{n-1} – \delta_n)$.

If $\delta_n > \delta_{n-1}/2$, then $\delta_{n+1} \delta_n > \delta_{n-1}/2$.

So now we just need to hunt for a pair of $n$s that form the base case. $\phi^2$ is $\delta_2=0.3819…$ less than 3 while $\phi^3$ is $\delta_3=0.236…$ more than 4, and $3/4 \delta_{3} > \delta_4 > \delta_{3}/2$. This completes the proof that the deltas decrease with n and so $\phi^n$ is very nearly an integer.

Now, showing that it exponentially decays can be seen by examining the difference equation for $\delta$. Rewrite it as $\delta_n = -(\delta_{n+1} – \delta_{n-1})$ This is the finite difference approximation of the differential equation $\delta(x) = -2 \partial_x \delta(x)$ which is solved by $\delta(x) = c \exp(-x/2)$ with some c, and 1/2 is VERY nearly the slope in your plot!

Sorry, I had sloppy copy-and-pasting. The third paragraph (about the inequalities between deltas) should read:

If $\delta_n > \delta_{n-1}/2$, then $\delta_{n+1} \delta_n > \delta_{n-1}/2$.

Nope, it’s a problem with the comments. After what’s above, it should read:

But we also now need to induce on this hypothesis, and we wind up with the requirement that $3 \delta_{n-1}/4 > \delta_n > \delta_{n-1}/2$.

It is easier in the following way:

If x(0)=a+b and x(1)=a*phi+b/(-phi) are integer then x(n)=a*phi^n+b/(-phi)^n will always be integer. This is because phi and -1/phi are the two solutions of x^2=x+1, and thus x(n+1)=x(n)+x(n-1) for all n.

Comment was sent before it was finished, and I cannot edit it. So here it goes on:

This does not help, however, to solve the problem. We would need a=1, and thus an integer b, and then phi-b/phi can not be integer, for that means b=phi^2-c*phi=1+(1-c)*phi.

@Rene, what’s wrong with a = b = 1? x(0) = 2, x(1) = phi – 1/phi = 1. Then phi^n + 1/(–phi)^n is always integer, and the second term decays.

And, @Renee, if b=1 then \delta_n (in my language) is 1/phi^n (I had pulled the minus sign out explicitly). That explains why the slope in John’s plot isn’t exactly -1/2, but is a little bit more— log(1/phi) = -0.481212… Your way is indeed beautiful.

The numbers x_n = phi^n + (-phi)^(-n) mentioned above are called Lucas numbers, see https://en.wikipedia.org/wiki/Lucas_number

Even more generally, this happens for any real algebraic number greater than 1 all of whose complex conjugates are inside the complex unit circle. For example, the root of z^3-z-1 that is close to 1.32 has its powers getting close to an integer. These are called PV-numbers. https://en.wikipedia.org/wiki/Pisot%E2%80%93Vijayaraghavan_number

Another simple way to understand this is that, if F(n) is the nth fibonacci number with F(0) = 0, F(1) = 1, then using the fact that \phi^2 = \phi + 1, it’s an easy induction to show that \phi^n = F(n)\phi + F(n-1).

Since the ratio of consecutive fibonacci numbers approaches \phi, we have for large n that F(n)\phi ≈ F(n+1), so that \phi^n ≈ F(n+1) + F(n-1)

Very cool, I didn’t know this fact. I once computed Phi to 2,000+ digits using a Matlab program of my own invention. I used FFTs for high precision floating

point multiplication simulation and Newton’s iteration for division (inverses). I used the ratio of Fibonacci numbers method and then the direct formula for Phi as a check. The latter method was faster of course, but only took a few seconds on a 2 GHz PC!

Gary Sitton

DSP Consultant

Houston, TX

Do you have the code you used to make these graphs on git by chance?

For every odd integer n >= 479, the fractional part of Phi^n is less than 1/Googol (10^100).

Try Table[Simplify[(1/2^n) (Expand[(1 + Sqrt[5])^n] +

Expand[(1 – Sqrt[5])^n])], {n, 0, 10}] in Mathematica.

THANKS MUCHLY Mr Cook / John. “Golden powers are nearly integers” is a beautiful presentation. I especially like/enjoy the plot + log-plot as it’s like an empirical (engineering signals analysis) waveform. So the pattern of your plot is very cool. .. *** John would I be able to have a copy of the (?python) code which you used in your making your presentation *** .. I am a retiring biomedical engineer interested in STEM teaching for underprivileged kids + I will do ethical thing, ie NOT circulate your code / teaching purposes ONLY .. If you say no I respectfully understand.