The Math Less Traveled

Herbert Wilf: 13 June 1931 – 7 January 2012

Posted on January 9, 2012 by Brent

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

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 Herbert Wilf | 1 Comment

A self-square number

Posted on January 4, 2012 by Brent

[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 decadic, idempotent, self, square | 12 Comments

Four-figure offer

Posted on December 1, 2011 by Brent

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 domain, four figure, offer | 7 Comments

Sigmas and sums of squares

Posted on November 29, 2011 by Brent

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 notation, sigma, squares, sum, telescope | 6 Comments

Dimensions: go watch! now!

Posted on November 21, 2011 by Brent

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 Dimensions, fibration, polytope, projection, video | 2 Comments

Old posts fixed

Posted on November 19, 2011 by Brent

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 Brent

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 art, fractal, geometry, perspective, review, textbook | Leave a comment

The Math Less Traveled

Herbert Wilf: 13 June 1931 – 7 January 2012

A self-square number

Four-figure offer

Sigmas and sums of squares

Dimensions: go watch! now!

Old posts fixed

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

Pages

Tags

Blogroll

Fun

Reference

Categories

Archives

Meta

Follow “The Math Less Traveled”