u-tube

Posted on January 10, 2012 by

[This is the eighth in a series of posts on the decadic numbers (previous posts: A curiosity, An invitation to a funny number system, What does "close to" mean?, The decadic metric, Infinite decadic numbers, More fun with infinite decadic numbers, A self-square number).]

In my previous post, we found a decadic number

u = \dots 57423423230896109004106619977392256259918212890625

with the curious property that it is its own square.

We also discovered an algorithm for computing u: starting with u_1 = 5, we square each u_n and take the remainder \bmod{10^{n+1}} (that is, we keep only the last n+1 digits) to give us u_{n+1}. Then u is defined as the limit of the u_n as n \to \infty.

(As an aside, notice why we are allowed to define u as a limit: because of the funny decadic metric, the distance between successive u_n is actually getting smaller by a factor of 1/10 each time; they are converging on something, and that something is u.)

So,

\begin{array}{rcl} u_2 & = & u_1^2 \bmod{100} = 5^2 \bmod{100} = 25 \\ u_3 & = & u_2^2 \bmod{1000} = 25^2 \bmod{1000} = 625 \\ u_4 & = & u_3^2 \bmod{10000} = 625^2 \bmod{10000} = 390625 \bmod{10000} = 625 \\ u_5 & = & \dots \end{array}

We can pretty easily turn this into a computer program to compute u to as many digits as we like. As usual, I’m using my favorite programming language, Haskell. It doesn’t matter if you don’t know Haskell, I’ll try to explain things well enough that you can still follow along anyway.

First we just need to import something we’ll need later.

> module Decadic where
>
> import Control.Monad.State

Now, we define u1 to be 5, and the function nextU takes n and u_n as input and produces u_{n+1} = u_n^2 \bmod{10^{n+1}}.

> u1 :: Integer
> u1 = 5
>
> nextU :: Integer -> Integer -> Integer
> nextU n un = (un^2) `mod` (10^(n+1))

Now we can define the (infinite!) list of u_n, which we’ll call us. generateUs takes the current values of n and u_n and generates a list with u_n as its first element, and the remainder of the list computed by a recursive call to generateUs (with n + 1 and u_{n+1} as its inputs). us just gets things started by calling generateUs with n=1 and u_1 = 5.

> us :: [Integer]
> us = generateUs 1 u1
>   where generateUs n un = un : generateUs (n+1) (nextU n un)

Let’s see if it works by asking for the first ten elements of the list us:

*Decadic> take 10 us
[5,25,625,625,90625,890625,2890625,12890625,212890625,8212890625]

Seems good!

However, all is not roses. Let’s think about what our program had to do in order to calculate u_{10}. Given u_9 = 212890625, it first squared it to get 45322418212890625… but wait a minute! 45322418212890625 ends in 212890625—of course it does, since that’s the defining property of the u_n. But that means that half (more or less) of the work needed to square 212890625 was completely wasted! There’s no point in computing the last half of u_n^2, since we already know it is going to be u_n. We only care about the rest of it.

Realizing that our program is doing too much work is one thing; turning this intuition into actual improvements is quite another! Initially it was far from obvious to me how to avoid the repeated work. But I finally figured it out.

The key is to remember at each step not just u_n, but u_n^2. However, since we know that u_n^2 ends with u_n, we can remember u_n along with the prefix (call it p_n) of u_n^2 that comes before the ending u_n. For example, for n = 9 we’ll remember p_9 = 45322418 and u_9 = 212890625 (since u_9^2 = 45322418212890625). That is, we will always insist that

u_n^2 = 10^n p_n + u_n.

The key question now is: given p_n and u_n, how do we compute p_{n+1} and u_{n+1}? Well, computing u_{n+1} is easy: it’s just u_n with an extra digit tacked on, namely, the final digit of p_n. In particular, we can define d_{n+1} = p_n \bmod{10} to be the last digit of p_n; then u_{n+1} = d_{n+1} 10^n + u_n.

It’s computing p_{n+1} which is the tricky part. Since we want to have u_{n+1}^2 = p_{n+1} 10^{n+1} + u_{n+1}, the idea is to expand out u_{n+1}^2, manipulate it into the desired form, and see what we get for p_{n+1}:

\begin{array}{rcl} u_{n+1}^2 & = & (d_{n+1} 10^n + u_n)^2 \\ & = & d_{n+1}^2 10^{2n} + 2d_{n+1} 10^n u_n + u_n^2 \\ & = & d_{n+1}^2 10^{2n} + 2d_{n+1} 10^n u_n + p_n 10^n + u_n \end{array}

Now, note that we can break p_n into two parts: the last digit (which we’re calling d_{n+1}) and the rest. That is,

p_n = 10 \lfloor p_n/10 \rfloor + d_{n+1}

where \lfloor - \rfloor denotes rounding down to the nearest integer, so \lfloor p_n/10 \rfloor means to divide p_n by 10 and throw away the remainder—that is, p_n without its final digit. Continuing,

\begin{array}{rcl} u_{n+1}^2 & = & d_{n+1}^2 10^{2n} + 2d_{n+1} 10^n u_n + p_n 10^n + u_n \\ & = & d_{n+1}^2 10^{2n} + 2d_{n+1} 10^n u_n + \lfloor p_n / 10 \rfloor 10^{n+1} + d_{n+1} 10^n + u_n \\ & = & d_{n+1}^2 10^{2n} + 2d_{n+1} 10^n u_n + \lfloor p_n / 10 \rfloor 10^{n+1} + u_{n+1} \\ & = & (d_{n+1}^2 10^{n-1} + 2 d_{n+1} u_n / 10 + \lfloor p_n / 10 \rfloor) 10^{n+1} + u_{n+1} \end{array}

and there we have it! We have expressed u_{n+1}^2 in the form p_{n+1} 10^{n+1} + u_{n+1}. In particular,

p_{n+1} = d_{n+1}^2 10^{n-1} + 2 d_{n+1} u_n / 10 + \lfloor p_n / 10 \rfloor

Notice that 2 d_{n+1} u_n / 10 is actually guaranteed to be an integer, since u_n is divisible by 5—this is the same phenomenon we ran across in proving that our simple algorithm for computing u_n works correctly. So we can factor out a division by ten (division is generally slow so we’d rather only do it once):

p_{n+1} = \lfloor (d_{n+1}^2 10^n + 2 d_{n+1} u_n + p_n) / 10 \rfloor

And now for some code! As one final optimization, instead of keeping track of n, we keep track of 10^n, so we don’t have to keep recomputing 10^n every iteration.

First, the data structure we use to keep track of the current values of p_n, u_n, and 10^n:

> -- State for incrementally constructing u_n.
> -- Invariant: curT = 10^n; un^2 = pn*curT + un
> data UState = UState { pn     :: Integer
>                      , un     :: Integer
>                      , curT   :: Integer
>                      }
>   deriving Show

The initial state for n = 1 has p_1 = 2, u_1 = 5, and 10^1 = 10.

> -- u_1 = 5;  5^2 = 25 = 2*10 + 5
> initUState = UState 2 5 10

The uStep function is the heart of the algorithm: it takes the current values of p_n, u_n, and 10^n and updates them to p_{n+1}, u_{n+1}, and 10^{n+1}. It also returns d_{n+1} as its result, which we can use to build up u digit-by-digit.

> uStep :: State UState Int
> uStep = do
>   u <- gets un
>   p <- gets pn
>   t <- gets curT
>
>   let d   = p `mod` 10      -- next digit
>       u'  = d * t + u       -- prepend the next digit to u
>       p'  = (p + 2*d*u + d*d*t) `div` 10   -- see above proof
>
>   put (UState p' u' (10*t)) -- record the new values
>
>   return $ fromInteger d    -- return the new digit

So, did we gain anything? As a concrete comparison, let’s see how long it takes to compute u_{10001}. Using our first, simple code, it takes 7.2 seconds:

*Decadic> :set +s
*Decadic> length . show $ us !! 10000
10001
(7.23 secs, 208746872 bytes)

(I just had it print the number of digits of u_{10001} to avoid wasting a ton of space printing out the entire number.) And using our new and hopefully improved code?

*Decadic> length . show . un . flip execState initUState
          $ replicateM_ 10000 uStep
10001
(1.55 secs, 225857080 bytes)

Only 1.5 seconds! Nice!

The other nice thing about uStep is that it spits out one digit of u at a time, which we can use to define u as an (infinite) list of digits—as if the digits were coming one at a time down a "tube", a u-tube, one might say… get it, a u… tube… heh… never mind.

> type TenAdic = [Int]
>
> u :: TenAdic
> u = 5 : evalState (sequence $ repeat uStep) initUState

*Decadic> reverse $ take 20 u
[9,2,2,5,6,2,5,9,9,1,8,2,1,2,8,9,0,6,2,5]

Nifty! Next time the real fun begins, as I show off some cool things we can do with our shiny new implementation of u.

Posted in computation, convergence, infinity, iteration, modular arithmetic, number theory, programming | Tagged , , , , | Leave a comment

Herbert Wilf: 13 June 1931 – 7 January 2012

Posted on January 9, 2012 by

I was sad to learn that Herbert Wilf died yesterday. Long-time readers of this blog may remember him as one of the discoverers of the Calkin-Wilf tree, which I wrote about in a ten-part series of posts (1, 2, 3, 4, 5, 6, 7, 8, 9, 10).

The Calkin-Wilf Tree

The Calkin-Wilf Tree

He also wrote generatingfunctionology, a textbook about generating functions, a topic near and dear to my heart (which I hope to write about here someday).

Although he was an emeritus professor at the University of Pennsylvania (where I am currently doing my PhD) I sadly never got a chance to meet him.

Posted in people | Tagged | 1 Comment

A self-square number

Posted on January 4, 2012 by

[This is the seventh in a series of posts on the decadic numbers (previous posts: A curiosity, An invitation to a funny number system, What does "close to" mean?, The decadic metric, Infinite decadic numbers, More fun with infinite decadic numbers). I know it's been a while since I've written on this topic, so if you've been following along, you might want to go back and refresh your memory.]

Finally, as promised, I can show you the strange number u which is its own square (but which isn’t zero or one!). Up until now all the decadic numbers we’ve considered have been equivalent to familiar rational numbers, but zero and one are the only rational numbers which are their own square; clearly u must be something quite different!

Assuming that such a u could exist—and assuming it’s a decadic integer, that is, has no digits to the right of the decimal point—let’s think for a minute about what u could possibly be. For example, what could its last digit be?

When we multiply two integers, the last digit of the result depends only on the last digits of the integers being multiplied, since all the other digits contribute some power of 10. So we can narrow down the possibilities for the last digit of any self-square decadic integer by seeing which digits have squares that end in the same digit:

d_0 d_0^2
0 0
1 1
2 4
3 9
4 16
5 25
6 36
7 49
8 64
9 81

I’ve highlighted the digits with the desired property: of course, 0^2 = 0 and 1^2 = 1, but also 5^2 ends in 5 and 6^2 ends in 6. We already know we don’t want to consider 0 and 1. So for now, let’s suppose that u ends with 5.

What about the last two digits of u? Again, the last two digits of u^2 depend only on the last two digits of u. (If this isn’t obvious to you, you should try a few examples to convince yourself. For example, what is 1234 \cdot 962? What information did you need to compute the last two digits of the answer?) So whatever the last two digits are, their square, when considered on their own as a two-digit number, must be some number that ends in the same two digits. Assuming the last digit is 5, we can turn this requirement into a modular equation which we can use to solve for the second-to-last digit:

\begin{array}{rcl}(10d_1 + 5)^2 & \equiv & 10d_1 + 5 \pmod{100} \\ 100d_1^2 + 100d_1 + 25 & \equiv & 10d_1 + 5 \pmod{100} \\ 20 & \equiv & 10d _1\pmod{100} \\ 2 & \equiv & d_1 \pmod{10} \end{array}

Sure enough, 25^2 = 625 which ends with 25.

Can we take this further? What about the last three digits?

\begin{array}{rcl}(100d_2 + 25)^2 & \equiv & 100d_2 + 25 \pmod{1000} \\ 10000d_2^2 + 5000d_2 + 625 & \equiv & 100d_2 + 25 \pmod{1000} \\ 600 & \equiv & 100d_2 \pmod{1000} \\ 6 &\equiv & d_2 \pmod{10} \end{array}

Check: 625^2 = 390625, which indeed ends with 625. Continuing in a similar fashion (I’ll let you work out the details on your own), we find that the fourth digit must be 0, and the fifth digit must be 9.

Are you seeing a pattern? Let’s make a table of the results so far:

n u \bmod{10^n} (u \bmod{10^n})^2
1 5 25
2 25 625
3 625 390625
4 0625 390625
5 90625 8212890625

Why did I put some numbers in bold? Well, hopefully you’ve noticed by now that each number in the left-hand column always seems to be a suffix of the square of the previous number. So perhaps the next digit will be 8? Sure enough, 890625^2 ends in 890625.

Will this always work? Yes, in fact, it will, and here’s why. Let’s let u_n denote the last n digits of u (so u_1 = 5, u_2 = 25, and so on). Once we have found u_n, we can set up a modular equation to find the next digit (this is just a generalization of what we did earlier):

\begin{array}{rcl}(10^n d_n + u_n)^2 & \equiv & 10^n d_n + u_n \pmod{10^{n+1}} \\ 10^{2n} d_n^2 + 2 \cdot 10^n d_n u_n + u_n^2 & \equiv & 10^n d_n + u_n \pmod{10^{n+1}} \end{array}

Now, 10^{2n} d_n^2 is clearly divisible by 10^{n+1} so that term goes away. But what about 2 \cdot 10^n d_n u_n? It seems that we only know it is divisible by 10^n, not necessarily by 10^{n+1}. Ah, but wait! We know that u_n ends with 5, and hence is divisible by 5; combining this with the 2 gives us another factor of 10! So this term goes away too, and we are left with

u_n^2 \equiv 10^n d_n + u_n \pmod{10^{n+1}}.

Now, u_n^2 \equiv u_n \pmod{10^n} (by definition), so subtracting u_n from both sides leaves a multiple of 10^n in the place of u_n^2 (namely, u_n^2 with the rightmost n digits set to zero). But we can also get rid of all the digits to the left of the (n+1)st because we are working mod 10^{n+1}. Dividing by 10^n we find that d_n must be equal to that (n+1)st digit of u_n^2.

So here’s the procedure: starting with u_1 = 5, define

u_{n+1} = u_n^2 \bmod{10^{n+1}}

That is, square the current number of length n and take the last n+1 digits to get the next number. The above proof shows that

  • At every step we will have a number u_n whose square ends with the digits of u_n;
  • this procedure will always work; and
  • this procedure gives the unique sequence of u_n with this property when starting with u_1 = 5!

So we have

\begin{array}{rcl} u_1 & = & 5 \\ u_2 & = & 25 \\ u_3 & = & 625 \end{array}

and so on.

So what is u? It is simply the limit of carrying out this procedure to infinity!

u = \dots 57423423230896109004106619977392256259918212890625

We know that any suffix of u, when squared, yields something ending with itself. So it makes sense (although it takes a bit of imagination!) that squaring u itself yields u again.

Posted in arithmetic, infinity, iteration, modular arithmetic, proof | Tagged , , , | 11 Comments

Four-figure offer

Posted on December 1, 2011 by

This just arrived in my inbox:

My name is Becky Raymond, I’m a Domain Brokerage Consultant working on behalf of the owner of traveled.com to sell this premium asset.

While searching online I came across your domain mathlesstraveled.com; since both domains have listings under a related keyword I thought perhaps your company may be interested in acquiring traveled.com? If this domain is of interest to you, please submit an offer in the four figure range and above to qualify as a potential buyer.

Sure thing, Becky! Here is my four-figure offer:

Fig. 1. A graph of the first 1000 hyperbinary numbers.

Fig 2. Hasse diagram for the subsets of a five-element set.

Fig. 3: Proof that T_n T_k + T_{n-1} T_{k-1} = T_{nk}.

Fig. 4: Complete set of 15-bracelets.

I hope you will agree that this is a very fine set of figures. I could probably add a couple more figures to my offer if that becomes necessary.

I look forward to being the proud owner of traveled.com, the place to go for all your mathematical travel needs!

Posted in humor, meta | Tagged , , | 7 Comments

Sigmas and sums of squares

Posted on November 29, 2011 by

Commenter Rachel recently asked,

How would you find the sum of \displaystyle \sum_{i=1}^n (i^2 + 3i + 4)?

See here for an explanation of sigma notation—in this case it denotes the sum

(1^2 + 3\cdot 1 + 4) + (2^2 + 3\cdot 2 + 4) + \dots

Of course, for any particular value of n we can just plug in values and do a bunch of adding. But I interpret Rachel’s question to mean “can we find an algebraic expression in terms of n which lets us compute the sum more quickly than actually adding the individual terms?”

Let’s try!

First, we observe that

\displaystyle \sum_i (X_i + Y_i) = \left(\sum_i X_i \right) + \left(\sum_i Y_i \right)

Why? If you think about it a bit, you can see that the same terms show up on the left and the right, just in a different order: the left side is (X_1 + Y_1) + (X_2 + Y_2) + \dots whereas the right side is (X_1 + X_2 + \dots) + (Y_1 + Y_2 + \dots). Since addition is associative (a + (b + c) = (a + b) + c) and commutative (a + b = b + a) these are equal.

Next, we observe that

\displaystyle \sum_i c X_i = c \sum_i X_i,

that is, (c X_1 + c X_2 + \dots) = c (X_1 + X_2 + \dots). This is because multiplication distributes over addition.

So, we have \displaystyle \sum_{i=1}^n (i^2 + 3i + 4) = \sum_{i=1}^n i^2 + 3 \sum_{i=1}^n i + \sum_{i=1}^n 4.

\sum_{i=1}^n 4 is just n copies of 4, so it is equal to 4n. I’ve written before about \sum_{i=1}^n i; it is equal to n(n+1)/2. So far, we have

\displaystyle \sum_{i=1}^n (i^2 + 3i + 4) = \frac{3n(n+1)}{2} + 4n + \sum_{i=1}^n i^2.

What about that pesky \sum_{i=1}^n i^2? Can it be simplified at all?

It can, and I know of a few different ways to figure it out. I’ll show you one of them today (and hopefully others in the future).

Consider the sum

\displaystyle \sum_{i=1}^n ((i+1)^3 - i^3)

For example, if n = 4 we have (2^3 - 1^3) + (3^3 - 2^3) + (4^3 - 3^3) + (5^3 - 4^3). Notice that we end up with both 2^3 and -2^3, 3^3 and -3^3… in fact, everything cancels except the -1^3 at the beginning and the 5^3 at the end. I hope you can see that in general,

\displaystyle \sum_{i=1}^n ((i+1)^3 - i^3) = (n+1)^3 - 1

This sort of sum is called a “telescoping” sum, because the whole thing “collapses” like one of those old-school telescopes that pirates use.

However, we can also expand out the (i+1)^3 and then simplify:

\displaystyle \begin{array}{rcl} \sum_{i=1}^n ((i+1)^3 - i^3) & = & \sum_{i=1}^n (i^3 + 3i^2 + 3i + 1 - i^3) \\ & = & \sum_{i=1}^n (3i^2 + 3i + 1) \\ & = & 3 \sum_{i=1}^n i^2 + 3 \sum_{i=1}^n i + \sum_{i=1}^n 1 \\ & = & 3 \sum_{i=1}^n i^2 + \frac{3n(n+1)}{2} + n \end{array}

So now we know that

\displaystyle (n+1)^3 - 1 = 3 \sum_{i=1}^n i^2 + \frac{3n(n+1)}{2} + n

since both sides are equal to \displaystyle \sum_{i=1}^n ((i+1)^3 - i^3). From here we just need some algebra to put \displaystyle \sum_{i=1}^n i^2 on one side and everything else on the other, and clean things up a bit to obtain… well, I’ll let you finish working it out. =)

Posted in algebra | Tagged , , , , | 6 Comments

Dimensions: go watch! now!

Posted on November 21, 2011 by

I finally got around to watching the Dimensions videos, which I mentioned once before. They are super cool and will be sure to blow your mind! They start by explaining some simple tools (stereographic projection) and intuition (with references to Flatland), then jump into four-dimensional polytopes, complex numbers, fractals, and fibrations. The videos can be a tiny bit cheesy and slow-moving at times—although really, if they went much faster it would be difficult to take it all in, and there is lots of stunningly beautiful 3D animation. Well, there’s 4D animation too, stereographically projected into 3-space, of course. =) Watching them all is definitely an investment of time (2 hours), but definitely worth it (and there’s nothing wrong with skipping around a bit). If you want to skip around, for maximum beautiful-mind-blowingness make sure you at least watch the videos about 4D polytopes and fibrations.

Posted in fractals, geometry, links, video | Tagged , , , , | 2 Comments

Old posts fixed

Posted on November 19, 2011 by

When I moved this blog from my own custom WordPress installation to wordpress.com last March, the formatting, \LaTeX, and images on a number of old posts got screwed up. I have finally finished going back through all my old posts and fixing things up! If you’re bored and looking for something interesting to read, why not take a look through my archives? =)

Posted in meta | Leave a comment

Book review: Viewpoints: Mathematical Perspective and Fractal Geometry in Art

Posted on November 18, 2011 by

Viewpoints

This book is certainly quite different from the sort I usually read and review—but I am always interested in new and creative ways to teach mathematics! This is quite a fun book. It’s all about visual art and some of the ways it is informed by mathematics, with focuses on perspective and fractals. It’s full of hands-on learning activities: reproducing a building using masking tape on a glass window, using shish kebab skewers to help view artworks at a museum, drawing assignments, and, yes, some math exercises. Interspersed between the chapters are “artist vignettes” telling the story (and showing off the (often amazing!) artwork) of artists whose work is somehow mathematically inspired. I didn’t learn much math from this book, but I did learn some fun things about art, and I suspect that the reverse would be true for artists without much math background. This book should work well for students who haven’t had too much fun with math in the past but are willing to try something new. It would especially work well as the textbook for a hands-on class or workshop taught by an enthusiastic instructor—as, in fact, it is designed to be.

My one gripe is with the quality of many of the included images (and yes, I find it strange that I should have to complain about this in a book about art!). First of all, the book is printed in black and white (with a collection of color plates in the middle); yes, of course I understand that there are tradeoffs involving the cost of printing the book, but still, it’s rather disappointing to have a book about art printed in black and white. The included diagrams and figures look great, but many of the included images (i.e. reproductions of artworks) are much too dark and hard to see, and I repeatedly found myself thinking, “I bet this painting/photograph/artwork would be really beautiful/interesting/amazing… if only I could see it in color.”

Still, overall, this is a great book with fresh perspective on the intersection of math and art that illuminates both subjects.

Posted in books, fractals, geometry, pattern, pictures, review | Tagged , , , , , | Leave a comment

Fun with repunit divisors: more solutions

Posted on November 17, 2011 by

In Fun with repunit divisors I posed the following challenge:

Prove that every prime other than 2 or 5 is a divisor of some repunit. In other words, if you make a list of the prime factorizations of repunits, every prime other than 2 or 5 will show up eventually.

My previous post explained two different proofs. At the end of “Fun with repunit divisors” I also posed a series of follow-up challenges; here are solutions to those.

  1. Compute a repunit which is divisible by 2011 (you’ll probably want to use a computer!).

    As we now know from the second proof (using Fermat’s Little Theorem), the repunit with 2010 ones must be divisible by 2011. So I guess a computer is not really necessary after all! However, what if we want to compute the smallest repunit which is divisible by 2011? In that case we can compute 1 \bmod {2011}, 11 \bmod {2011}, 111 \bmod {2011}, … until we get zero. However, we don’t have to actually compute a bigger and bigger repunit each time! Each repunit is related to the previous one by an application of the function f(x) = 10x + 1. So it suffices to keep only the remainder \pmod {2011} at each step, and apply f(x) = 10x + 1 to each remainder to get the next (reducing \pmod {2011} when needed). For example, we start out by computing 1, 11, 111, 1111, but at the next step we can reduce 11111 \bmod {2011} to get 1056. Then we compute (1056 \cdot 10 + 1) \bmod {2011} = 10561 \bmod {2011} = 506, then 5061 \bmod{2011} = 1039, and so on. Iterating this process on a computer is very fast, and in a fraction of a second we find that (10^{670} - 1)/9 is the smallest repunit divisible by 2011. For example, I computed this using Haskell by defining

    f p x = (10*x + 1) `mod` p
smallestRep p = (+1) . length . takeWhile (/= 0) . iterate (f p) $ 1

  2. Prove that every prime other than 2 or 5 is actually a divisor of infinitely many repunits.

    Proof: Note that multiplying, say, 111 by 1001 gives 111111; multiplying by 1001001 gives 111111111, and so on. In general, we can see that the repunit with m digits always evenly divides the repunit with n digits whenever m evenly divides n. So if p is a divisor of (10^n - 1)/9 then it is also a divisor of (10^{kn} - 1)/9 for all k \geq 1.

  3. Prove that every integer which is not divisible by 2 or 5 is a divisor of some repunit.

    Proof: suppose n has the prime factorization n = p_1 p_2 \dots p_k. We know that each p_i is a divisor of some repunit (10^{j_i} - 1)/9. Then, by the argument above, n must be a divisor of (10^{j_1 j_2 \dots j_k} - 1)/9. As a simple example, 231 = 3 \cdot 7 \cdot 11; 3 divides 111 = (10^3 - 1)/9, 7 divides 111111 = (10^6 - 1)/9, and 11 = (10^2 - 1)/9 is a repunit itself. Hence 231 must be a divisor of (10^{36} - 1)/9, since 36 = 2 \times 3 \times 6. (Actually, we can make this a bit more precise in order to find a much smaller repunit that 231 must evenly divide. Can you see how?)

  4. Generalize all of the above to repunits in bases other than 10.

    In base b, we can define a repunit of length n to be 111\dots 1_{b} = b^{n-1} + b^{n-2} + \dots + 1. Everything above is still true as long as we replace the special excluded primes 2 and 5 with whichever primes show up in the prime factorization of the base b.

  5. What’s so special about repunits here? Can you generalize to other sorts of numbers?

    I’ll leave this one open for the time being! There are probably lots of interesting ways you could answer this question.

Posted in arithmetic, iteration, modular arithmetic, number theory, primes, programming, proof, solutions | Tagged | Leave a comment

Fun with repunit divisors: proofs

Posted on November 16, 2011 by

As promised, here are some solutions to the repunit puzzle posed in my previous post. (Stop reading now if you don’t want to see solutions yet!)

Prove that every prime other than 2 or 5 is a divisor of some repunit. In other words, if you make a list of the prime factorizations of repunits, every prime other than 2 or 5 will show up eventually.

Proof 1: Note that we can write the repunit containing n ones as (10^n - 1)/9. Suppose p is a prime other than 2 or 5, and consider the remainders when repunits are divided by p. Since there are infinitely many repunits and only p possible remainders, by the Pigeonhole Principle there must be some remainder which is repeated, that is, there must be two distinct numbers i and j (let’s say i < j) such that

(10^j - 1)/9 \equiv (10^i - 1)/9 \pmod p.

Bringing (10^i - 1)/9 over to the left-hand side and simplifying gives

(10^j - 10^i)/9 \equiv 0 \pmod p.

Since i < j we can factor out 10^i, giving

10^i(10^{j-i} - 1)/9 \equiv 0 \pmod p.

Now, although it is perfectly OK to add, subtract, or multiply by the same thing on both sides of a modular equation, we have to be careful with division: it is only safe to divide both sides of a modular equation by some number which does not share any common factors with the modulus. Well, in this case we began by assuming that p is neither 2 nor 5, so it does not share any factors with 10^i. Hence, dividing both sides by 10^i gives us

(10^{j-i} - 1)/9 \equiv 0 \pmod p.

Look! A repunit divisible by p!

What’s the “big idea” here? We have some sort of iterative process and want to show that some particular thing must eventually happen. If there are only a finite number of possibilities, by the Pigeonhole Principle we know the process must eventually repeat. So we look at the places where it repeats, and use those to create the thing we wanted to show.

Proof 2: Fermat’s Little Theorem states that for any number a which is not divisible by some prime p,

a^{p-1} - 1 \equiv 0 \pmod p.

So we can apply this directly to conclude that (10^{p-1} - 1)/9 is divisible by p for any primes other than 2, 3, or 5 (note: why not 3?). In other words, such p always divide the repunit with p-1 ones. To complete the proof we simply note that 111 is divisible by 3.

This version is much shorter but of course requires you to know Fermat’s Little Theorem! And it doesn’t give as much insight unless you already have some insight into why Fermat’s Little Theorem is true. Perhaps I could explain a proof or two of Fermat’s Little Theorem in a future post if anyone is interested.

At the end of my last post I also posed some “follow-up” challenges. I’ll post solutions to those next time.

Posted in iteration, modular arithmetic, number theory, pattern, primes, proof | Tagged , , , , | 1 Comment