From primitive roots to Euclid’s orchard

Commenter Snowball pointed out the similarity between Euclid’s Orchard

…and this picture of primitive roots I made a year ago:

At first I didn’t see the connection, but Snowball was absolutely right. Once I understood it, I made this little animation to illustrate the connection more clearly:

(Some of the colors flicker a bit; I’m not sure why.)

Posted in pattern, pictures, posts without words | Tagged , , , , , | Leave a comment

A few words about PWW #20

A couple commenters quickly figured out what my previous post without words was about. The dots making up the image are at integer grid points (m,n), with the center at (0,0). There is a dot at (m,n) if and only if m and n are relatively prime, that is, \gcd(m,n) = 1. Here is a slightly smaller version so it’s easier to see what is going on:

I learned from Lucas A. Brown that this is sometimes known as “Euclid’s Orchard”. Imagine that there is a tall, straight tree growing from each grid point other than the origin. If you stand at the origin, then the trees you can see are exactly those at grid points (m,n) with \gcd(m,n) = 1. This is because if a tree is at (dm,dn) for some d > 1, then it is blocked from your sight by the tree at (m,n): both lie exactly along the line from the origin with slope n/m. But if a tree is at some point with relatively prime coordinates (m,n), then it will be the first thing you see when you look along the line with slope exactly n/m.

(…well, actually, all of the above is only really true if we assume the trees are infinitely skinny! Otherwise trees will end up blocking other trees which are almost, but not quite, in line with them. So try not to breathe while standing at the origin, OK? You might knock over some of the infinitely skinny trees.)

Here’s the 9 \times 9 portion of the grid surrounding the origin, with the lines of sight drawn in along with the trees you can’t see because they are exactly in line with some closer tree. (I’ve made the trees skinny enough so that they don’t accidentally block any other lines of sight—but if we expanded the grid we’d have to make the trees even skinner.)

Now, what about the colors of the dots? Commenter Snowball guessed this correctly: each point is colored according to the number of steps needed for the Euclidean algorithm needed to reach 1. Darker colors correspond to more steps. It is interesting to note that there seems to be (eight symmetric copies of) one particularly dark radial stripe, indicated below:

In fact, the slope of this stripe is exactly \varphi = (1 + \sqrt 5)/2! This corresponds to the fact (first proved by Gabriel Lamé in 1844) that consecutive Fibonacci numbers are worst-case inputs to the Euclidean algorithm—that is, it takes more steps for the Euclidean algorithm to compute \gcd(F_{n+1}, F_n) = 1 than for any other inputs of equal or smaller magnitude. Since the ratio of consecutive Fibonacci numbers tends to \varphi, the dots with the darkest color relative to their neighbors all lie approximately along the line with slope \varphi. What’s interesting to me is that lots of other dots that lie close to this line are also relatively dark. Why does this happen?

Posted in pattern, pictures, posts without words | Tagged , , | 10 Comments

Post without words #20

Image | Posted on by | Tagged , , | 7 Comments

The curious powers of 1 + sqrt 2: recurrences

In my previous post, we found an answer to the question:

What’s the 99th digit to the right of the decimal point in the decimal expansion of (1 + \sqrt 2)^{500}?

However, the solution depended on having the clever idea to add (1 + \sqrt 2)^n + (1 - \sqrt 2)^n. But there are other ways to come to similar conclusions, and in fact this is not the way I originally solved it.

The first thing I did when attacking the problem was to work out some small powers of 1 + \sqrt 2 by hand:

\displaystyle \begin{array}{rcl} (1 + \sqrt 2)^2 &=& 1 + 2 \sqrt 2 + 2 = 3 + 2 \sqrt 2 \\[1em] (1 + \sqrt 2)^3 &=& (3 + 2 \sqrt 2)(1 + \sqrt 2) = 7 + 5 \sqrt 2 \\[1em] (1 + \sqrt 2)^4 &=& (7 + 5 \sqrt 2) (1 + \sqrt 2) = 17 + 12 \sqrt 2 \end{array}

and so on. It quickly becomes clear (if you have not already seen this kind of thing before) that (1 + \sqrt 2)^n will always be of the form a + b \sqrt 2. Let’s define a_n and b_n to be the coefficients of the nth power of (1 + \sqrt 2), that is, (1 + \sqrt 2)^n = a_n + b_n \sqrt 2. Now the natural question is to wonder what, if anything, can we say about the coefficients a_n and b_n? Quite a lot, as it turns out!

We can start by working out what happens when we multiply (1 + \sqrt 2)^n = (a_n + b_n \sqrt 2) by another copy of (1 + \sqrt 2):

\displaystyle (1 + \sqrt 2)^{n+1} = (a_n + b_n \sqrt 2)(1 + \sqrt 2) = (a_n + 2b_n) + (a_n + b_n) \sqrt 2

But (1 + \sqrt 2)^{n+1} = a_{n+1} + b_{n+1} \sqrt 2 by definition, so this means that a_{n+1} = a_n + 2b_n and b_{n+1} = a_n + b_n. As for base cases, we also know that (1 + \sqrt 2)^0 = 1 + 0\sqrt 2, so a_0 = 1 and b_0 = 0. From this point it is easy to quickly make a table of some of the values of a_n and b_n:

\displaystyle \begin{array}{ccc} n & a_n & b_n \\ \hline 0 & 1 & 0 \\ 1 & 1 & 1 \\ 2 & 3 & 2 \\ 3 & 7 & 5 \\ 4 & 17 & 12 \\ 5 & 41 & 29 \\ 6 & 99 & 70 \\ 7 & 239 & 169 \\ 8 & 577 & 408 \\ 9 & 1393 & 985 \end{array}

Each entry in the b_n column is the sum of the a_n and b_n from the previous row; each a_n is the sum of the previous a_n and twice the previous b_n. You might enjoy playing around with these sequences to see if you notice any patterns. It turns out that there is an equivalent way to define the a_n and b_n separately, such that each a_n only depends on previous values of a_n, and likewise each b_n only depends on previous b_n. I’ll explain how to do that next time, but leave it as a challenge for you in the meantime!

Posted in number theory, puzzles | Tagged , , , , , | 8 Comments

The curious powers of 1 + sqrt 2: a clever solution

Recall that we are trying to answer the question:

What’s the 99th digit to the right of the decimal point in the decimal expansion of (1 + \sqrt 2)^{500}?

In my previous post, we computed (1 + \sqrt 2)^n for some small n and conjectured that the answer is 9, since these powers seem to be alternately just under and just over an integer. Today, I’ll explain a clever solution, which I learned from Colin Wright (several commenters also posted similar approaches).

First, let’s think about expanding (1 + \sqrt 2)^n using the Binomial Theorem:

\displaystyle (1 + \sqrt 2)^n = 1 + n \sqrt 2 + \binom{n}{2} (\sqrt 2)^2 + \binom{n}{3} (\sqrt 2)^3 + \dots + (\sqrt 2)^n.

We get a sum of powers of \sqrt 2 with various coefficients. Notice that when \sqrt 2 is raised to an even power, we get an integer: (\sqrt 2)^2 = 2, (\sqrt 2)^4 = 2^2 = 2, and so on. The odd powers give us irrational things. So if we could find some way to “cancel out” the odd, irrational powers, we would be left with a sum of a bunch of integers.

Here is where we can pull a clever trick: consider (1 - \sqrt 2)^n. If we expand it by the Binomial Theorem, we find

\displaystyle \begin{array}{rcl} (1 - \sqrt 2)^n &=& \displaystyle 1 + n (-\sqrt 2) + \binom{n}{2} (-\sqrt 2)^2 + \binom{n}{3} (-\sqrt 2)^3 + \dots + (-\sqrt 2)^n \\[1.5em] &=& \displaystyle 1 - n \sqrt 2 + \binom{n}{2} (\sqrt 2)^2 - \binom{n}{3} (\sqrt 2)^3 + \dots \pm (\sqrt 2)^n \end{array}

but this is the same as the expansion of (1 + \sqrt 2)^n, with alternating signs: the odd terms—which are exactly the irrational ones—are negative, and the even terms are positive. So if we add these two expressions, the odd terms will cancel out, leaving us with two copies of all the even terms:

\displaystyle (1 + \sqrt 2)^n + (1 - \sqrt 2)^n = 2 \left(1 + \binom{n}{2} (\sqrt 2)^2 + \binom{n}{4} (\sqrt 2)^4 + \dots \right).

For now, we don’t care about the value of the sum on the right—the important thing to note is that it is an integer, since it is a sum of integers multiplied by even powers of \sqrt 2, which are just powers of two.

We are almost done. Notice that \sqrt 2 \approx 1.4142 \dots, so 1 - \sqrt 2 \approx -0.4142 \dots. Since this has an absolute value less than 1, its powers will get increasingly close to zero; since it is negative, its powers will alternate between being positive and negative. Hence,

\displaystyle (1 + \sqrt 2)^n + (1 - \sqrt 2)^n

is an integer, and (1 - \sqrt 2)^n is very small, so (1 + \sqrt 2)^n must be very close to that integer. When n is even, (1 - \sqrt 2)^n is positive, so (1 + \sqrt 2)^n must be slightly less than an integer; conversely, when n is odd we conclude that (1 + \sqrt 2)^n is slightly greater than an integer.

To complete the solution to this particular problem, we have to make sure that (1 - \sqrt 2)^{500} is small enough that we can say for sure the 99th digit after the decimal point of (1 + \sqrt 2)^{500} is still 9. That is, we need to prove that, say, (1 - \sqrt 2)^{500} < 10^{-100}. This will be true if we can show that |1 - \sqrt 2|^5 < 10^{-1} (just raise both sides to the 100th power), and in turn, taking the base 10 logarithm of both sides, this will be true if 5 \log_{10} |1 - \sqrt 2| < -1. At this point we can simply confirm by computation that 5 \log_{10} |1 - \sqrt 2| \approx -1.91\dots < -1. The fact that we get -1.91\dots means that not just 99, but actually the first 191 digits after the decimal point of (1 + \sqrt 2)^{500} are 9. (It turns out that the 192nd digit is a 5.)

The rabbit hole goes much deeper than this, however!

Posted in number theory, puzzles | Tagged , , , , , | 2 Comments

The curious powers of 1 + sqrt 2: conjecture

In my previous post I related the following puzzle from Colin Wright:

What’s the 99th digit to the right of the decimal point in the decimal expansion of (1 + \sqrt 2)^{500}?

Let’s play around with this a bit and see if we notice any patterns. First, 1 + \sqrt 2 itself is approximately

1 + \sqrt 2 \approx 2.414213562373095\dots

so its powers are going to get large. Let’s use a computer to find the first ten or so:

\displaystyle \begin{array}{cc} n & (1 + \sqrt 2)^n \\ \hline 1 & 2.414213562373095 \\ 2 & 5.82842712474619 \\ 3 & 14.071067811865474 \\ 4 & 33.970562748477136 \\ 5 & 82.01219330881975 \\ 6 & 197.99494936611663 \\ 7 & 478.002092041053 \\ 8 & 1153.9991334482227 \\ 9 & 2786.0003589374983 \\ 10 & 6725.9998513232185 \end{array}

Sure enough, these are getting big (the tenth power is already bigger than 6000), but look what’s happening to the part after the decimal: curiously it seems that the powers of (1 + \sqrt 2) are getting rather close to being integers! For example, (1 + \sqrt 2)^{10} is just under 6726, only about 0.0002 away.

At this point, I had seen enough to notice and conjecture the following patterns (and I hope you have too):

  • The powers of (1 + \sqrt 2) seem to be getting closer and closer to integers.
  • In particular, they seem to alternate between being just under an integer (for even powers) and just over an integer (for odd powers).

If this is true, the decimal expansion of (1 + \sqrt 2)^{500} must be of the form n.99999999\dots for some big integer n and some number of 9s after the decimal point. And it seems reasonable that if Colin is posing this question, it must have more than 99 nines, which means the answer would be 9.

But why does this happen? Do the powers really keep alternating being just over and under an integer? And how close do they get—how do we know for sure that (1 + \sqrt 2)^{500} is close enough to an integer that the 99th digit will be a 9? This is what I want to explore in a series of future posts—and as should come as no surprise it will take us on a tour of some fascinating mathematics!

Posted in number theory, puzzles | Tagged , , , , , | 3 Comments

The curious powers of 1 + sqrt 2

Recently on, Colin Wright posted the following puzzle:

What’s the 99th digit to the right of the decimal point in the decimal expansion of (1 + \sqrt 2)^{500}?

Of course, it’s simple enough to use a computer to find the answer; any language or software system that can compute with arbitrary-precision real numbers can find the correct answer in a fraction of a second. But that’s obviously not the point! Can we use logical reasoning to deduce or prove the correct answer, without doing lots of computation? Even if we find the answer computationally, can we explain why it is the right answer? Solving this puzzle took me down a fascinating rabbit hole that I’d like to share with you over the next post or three or eight.

For the moment I’ll just let you think about the puzzle. Although using a computer to simply compute the answer is cheating, I do encourage the use of a computer or calculator to try smaller examples and look for patterns. It is not too hard to see a pattern and conjecture the right answer; the interesting part, of course, is to figure out why this pattern happens, and to prove that it continues.

Posted in challenges, number theory, puzzles | Tagged , , , | 15 Comments