## 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 $100$th 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!

## 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 $9$s 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 , , , , , | 1 Comment

## The curious powers of 1 + sqrt 2

Recently on mathstodon.xyz, 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 , , , | 11 Comments

## Post without words #19

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

## Post without words #18

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

## AlphaGo

Many of my readers may have already heard about AlphaGo, a computer program developed by Google DeepMind which plays the ancient board game of Go. Developing a program to play Go is not that big of a deal—the first such program was written in 1968—but what is a big deal is how well it plays. In fact, it has just beaten Ke Jie, widely regarded at the moment to be the best human Go player in the world, three games to none in a three-game series.

# What is Go?

Go is a very old board game, invented in ancient China over 2500 years ago. Players take turns playing white and black stones on the intersections of a grid, with the goal being to surround more territory than the opponent. The rules themselves are actually quite simple—it takes just a few minutes to learn the basics—but the simple rules have complex emergent properties that make the strategy incredibly deep. Top human players spend their whole lives devoted to studying and improving at the game.

I enjoy playing Go for many of the same reasons that I love math—it is beautiful, deep, often surprising, and rewards patient study. If you want to learn how to play—and I highly recommend that you do—try starting here!

# Why is this a big deal?

Ever since IBM’s Deep Blue beat world champion Garry Kasparov in a chess match in 1997, almost 20 years ago, the best chess-playing computer programs have been able to defeat even top human players. Go, on the other hand, is much more difficult for computers to play. There are several reasons for this:

• The number of possible moves is much higher in Go than in chess, and games tend to last much longer (a typical game of Go takes hundreds of moves as opposed to around 40 moves for chess). So it is completely infeasible to just try all possible moves by brute force.
• With chess, it is not too hard to evaluate who is winning in a particular position, by looking at which pieces they have left and where the pieces are on the board; with Go, on the other hand, evaluating who is winning can be extremely difficult.

Up until just a few years ago, the best Go-playing programs could play at the level of a decent amateur player but could not come anywhere close to beating professional-level players. Most people thought that further improvements would be very difficult to achieve and that it would be another decade or two before computer programs could beat top human players. So AlphaGo came as quite a surprise, and is based on recent fundamental advances in machine learning techniques (which are already having lots of other cool applications).

It is particularly interesting that AlphaGo works in a much more “human-like” way than Deep Blue did. Deep Blue was able to win at chess essentially by being really fast at evaluating lots of potential moves—it could analyze hundreds of millions of positions per second—and by consulting giant tables of memorized positions. Chess playing programs are better than us at chess, yes, but as far as I know we haven’t particularly learned anything from them. AlphaGo, on the other hand, “learned” how to play go by studying thousands of human games and then improving by playing itself many, many times. It uses several “neural networks”—a machine learning technique which is ultimately modeled on the structure of the human brain—both to predict promoising moves to study and to evaluate board positions. Of course it also plays out many potential sequences of moves to evaluate them. So it plays using a combination of pattern recognition and speculatively playing out potential sequences of moves—which is exactly how humans play. The amazing thing is that AlphaGo has actually taught us new things about Go—on many occasions it has played moves that humans describe as surprising and beautiful. It has also played moves that the accepted wisdom said were bad moves, but AlphaGo showed how to make them work. One might expect that people in the Go world might feel a sense of loss upon being beaten by a computer program—but the feeling is actually quite the opposite, because of the beatiful way AlphaGo plays and how much it has taught us about the game.