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.

Advertisements

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in challenges, number theory, puzzles and tagged , , , . Bookmark the permalink.

15 Responses to The curious powers of 1 + sqrt 2

  1. hektor441 says:

    Perhaps something about \mathbb{Z}[\sqrt{2}] ?

  2. Sylvain B. says:

    mmmhhh… Pascal is lurking around, I think

  3. kaligule says:

    “What are you doing?”

    “I am trying to find the 99th digit after the point of $(1 + \sqrt 2)^{500}$.”

    “Why?”

    “Someone on the internet told me to.”

    “Really? So why don’t you just look it up?”

    “Well, the same person said there is a more complicated way, so I am l searching that one.”

  4. Pingback: Because we love square roots here. – The Square Root

  5. Lucas A. Brown says:

    Let x = 1+sqrt(2). This is a Pisot-Vijayaraghavan number, so the numbers x^n get exponentially close to the nearest integer to x^n as n gets large. Since x’s Galois conjugate is negative, x^n will alternately over- and under-estimate its nearest integer. So in any base b, we find that for all sufficiently large n, the kth digit to the right of x^n’s decimal point will alternate between 0 and b-1; in particular, the even powers yield b-1 and the odd powers yield 0. I’m on mobile right now and don’t have any scratch paper handy, so I’ll leave it to others to figure out what qualifies as “sufficiently large” for a given selection of b and k.

    For another approach, we can use the fact that x’s continued fraction is [2;2,2,2,2,…]. Applying an elementary error estimate for convergents then tells us that, if p/q is a convergent to x, then 1/4q^2 < |x-p/q| < 1/2q^2. This can be combined with the Wallis-Euler recurrence q_(k+1) = 2*q_k + q_(k-1) with q_0 = 1 and q_1 = 2 for the convergents' denominators to easily determine how many terms we need in the continued fraction to compute x to any desired precision.

    • Lucas A. Brown says:

      In regards to my first paragraph above, I should probably add that we can use the theory of Lucas sequences (and in particular the formula V_k(2,-1) = x^n + (1-sqrt(2))^k) to get an easy way to determine what qualifies as “sufficiently large n” for a particular b and k.

  6. Fergal Daly says:

    [BIG HINT ALERT]

    It doesn’t bring you down an interesting rabbit hole or provide a deep reason why but if you take

    $$(1 + \sqrt 2)^n + (1 – \sqrt 2)^n$$

    and apply the binomial expansion, you’re almost done.

    Despite not being interesting, it does give you a way to generalize to an infinite number of $(a + \sqrt b)^n$ with a pretty simple condition relating $a$ and $b$.

    • David Brahm says:

      It’s slowly dawning on me that this may be the simplified version of what Lucas A Brown said. Is (1 - \sqrt 2) the “Galois conjugate”?

      • Lucas A Brown says:

        Yes. The Galois conjugates of an algebraic number are the other roots of that number’s minimal polynomial. Quadratic numbers such as 1+sqrt(2) have one Galois conjugate, and it is found by flipping the sign on the square root term.

      • Fergal Daly says:

        I haven’t dug through the details but I presume that there are some polynomial identitites relating the sum of the nth powers of all the roots to the coefficients of the polynomial such that the sum must be an integer. So if all the conjugates have complex magnitude < 1, then their nth powers vanish and so nth power of the original root must be some integer +/- vanishing quantity.

  7. Pingback: The curious powers of 1 + sqrt 2: conjecture | The Math Less Traveled

  8. Pingback: The curious powers of 1 + sqrt 2: a clever solution | The Math Less Traveled

Comments are closed.