Tanya Khovanova's Math Blog

The Symmetries of Things by John H. Conway, Heidi Burgiel, and Chaim Goodman-Strauss is out. It is a beautiful edition with great pictures.

The first chapter is very nicely written and might be recommended to high school and undergraduate students. It covers symmetries of finite and infinite 2D objects.

The second chapter adds color to the theory. For beautiful colorful pictures with symmetry, there are two symmetry groups: the group that preserves the picture while ignoring its coloring and the group that preserves the picture while respecting its coloring. The latter group is a subgroup of a former group. This second chapter discusses all possible ways to symmetrically color a symmetric 2D picture. The chapter then continues with a discussion of group theory. This chapter is much more difficult to read than the first chapter, as it uses a lot of notations. The pictures are still beautiful, though.

The third chapter is even more difficult to read and the notations become even heavier. This chapter discusses hyperbolic groups and symmetries of objects in the hyperbolic space. Then the chapter moves into 3D and 4D. I guess that some parts of the second and the third chapters are not meant for light reading; they should be considered more as reference materials.

Here are pictures of a musnub cube (multiplied snub cube), built by John H. Conway. It is an infinite Archimedean polyhedron. The description of it is on page 338 and the diagram is on page 339 of the book. This object was glued together from stars and squares. Each corner of the square is glued to a point of one star and to an inside corner of another star. Mathematically, a star is not a regular polygon. If you look at stars with your mathematical eye, each star in the picture is not just a star, but rather the union of a regular hexagon with 6 regular triangles. That means the list of the face sizes around each vertex of a musnub cube officially is represented as 6.3.4.3.3.

The second picture shows a finished musnub cube. You can’t really finish building an infinite structure. Right? It is finished in the sense that John Conway finished doing what he was planning to do: to construct a part of a musnub cube inside a regular triangular pyramid.

Did I mention that I like the pictures in The Symmetries of Things?

Here I repeat the Conway’s Wizards Puzzle from a previous posting:

Last night I sat behind two wizards on a bus, and overheard the following:

— A: “I have a positive integral number of children, whose ages are positive integers, the sum of which is the number of this bus, while the product is my own age.”
— B: “How interesting! Perhaps if you told me your age and the number of your children, I could work out their individual ages?”
— A: “No.”
— B: “Aha! AT LAST I know how old you are!”

Now what was the number of the bus?

It is obvious that the first wizard has more than two children. If he had one child then his/her age would be the number of the bus and it would be the same as the father’s age. While it is unrealistic, in mathematics many strange things can happen. The important part is that if the wizard A had one child he couldn’t have said ‘No’. The same is true for two children: their age distribution is uniquely defined by the sum and the product of their ages.

Here is a generalization of this puzzle:

Last night I sat behind two wizards on a bus, and overheard the following:

— Wizard A: “I have a positive integral number of children, whose ages are positive integers, the sum of which is the number of this bus, while the product is my own age. Also, the sum of the squares of their ages is the number of dinosaurs in my collection.”
— Wizard B: “How interesting! Perhaps if you told me your age, the number of your children, and the number of dinosaurs, I could work out your children’s individual ages. ”
— Wizard A: “No.”
— Wizard B: “Aha! AT LAST I know how old you are!”

Now what was the number of the bus?

As usual with generalizations, they are drifting far from real life. For this puzzle, you have to open up your mind. In Conway’s original puzzle you do not need to assume that the wizard’s age is in a particular range, but once you solve it, you see that his age makes sense. In this generalized puzzle, you should assume that wizards can live thousands of years, and keep their libido that whole time. Wizards might spend so much of their youth thinking, that they postpone starting their families for a long time. The wizards’ wives are also generalized. They can produce children in great quantities and deliver multiple children at the same time in numbers exceeding the current world record.

Another difference with the original puzzle is that you can’t solve this one without a computer.

You can continue to the next step of generalization and create another puzzle by adding the next symmetric polynomial on the ages of the children, for example, the sum of cubes. In this case, I do not know if the puzzle works: that is, if there is an “AHA” moment there. I invite you, mighty geeks, to try it. Please, send me the answer.

In case you are wondering why the wizard is collecting dinosaurs, I need to point out to you that John H. Conway is a superb puzzle inventor. His puzzle includes a notation suggestion: a for the wizard’s age, b for the bus, c for the number of children. Hence, the dinosaurs.

Here is my simplified version of Conway’s wizards puzzle.

Last night when I was coming home from my writing class with Sue Katz, I sat behind two wizards on the bus, and overheard the following:

— Wizard A: “I have a positive integral number of children, whose ages are positive integers, the sum of which is the number of this bus, while the product is the amount of dollars I have in my pocket.”

At this point I interrupted the wizard. “Excuse me, professor, I overheard your conversation and can’t resist asking you a question. Usually when a father says ‘my children’ everyone assumes that he has at least two children. Can I assume that?”

— Wizard A: “No. I stated my assumptions up front. A positive integral number of children means one or more.”

I started thinking. If I were to explain this to a non-mathematician who assumes that ‘my children’ means more than one child, I would need to change the wizard’s statement into the following:

“I have at least one child. The ages of my one-or-more children are all positive integers. The sum of the ages of my children or the age of my only child is the number of this bus. The product of the ages of my children or my only child’s age is the amount of dollars I have in my pocket.”

Hmm. I like that mathematicians use ‘my children’ to indicate any number of children. Makes puzzles faster to type.

Anyway, the wizards continued their discussion:

— Wizard B: “How interesting! Perhaps if you told me the number of your children, I could work out their individual ages”
— Wizard A: “No.”
— Wizard B: “Aha! AT LAST I know how many children you have!”

If I were John Conway, I would have asked you next, “What is the number of the bus?” As I am not John Conway, I’ll ask you, “Why do we presume that Wizard A hasn’t cheated on his wife?”

The answer is that all wizards are notorious for making precise statements. If he cheats a lot, he would have started the conversation with, “The number of children I know about is a positive integer.” Or maybe, more discreetly, “My wife and I have a positive integral number of children.”

If you have already figured out the number of the bus, the bonus question is, “Why did I change the ‘age of the first wizard’ in Conway’s original puzzle into the ‘amount of dollars’ in my puzzle?”

When I left the bus, I started wondering why on earth anyone would ever want to sum up the ages of their children. And I remembered that I once did it myself. I was trying to persuade my sister to apply for U.S. citizenship. My argument was that by moving here the life expectancy of her children would increase by 30 years. Indeed, she has two sons and the male life expectancy in Russia and the U.S. has an astonishing 15-year difference. I have to admit that my argument is not very clean, as we do not know the causes for this difference and, besides, the data is for life expectancy at birth and it changes while our kids age. My sister dismissed my argument, saying that the low male life expectancy in Russia is due to alcoholism and that her family is not in the high-risk group.

So, there could be a reason to sum up the ages of your children, but why would anyone ever want to multiply the ages of their children? In any case, if the first wizard continues to keep an amount of dollars equaling the product of the ages of his children in his pocket, his pocket will do better than mutual funds for the next several years.

John Conway sent me a puzzle about wizards, which he invented in the sixties. Here it is:

Last night I sat behind two wizards on a bus, and overheard the following:

— A: “I have a positive integral number of children, whose ages are positive integers, the sum of which is the number of this bus, while the product is my own age.”
— B: “How interesting! Perhaps if you told me your age and the number of your children, I could work out their individual ages?”
— A: “No.”
— B: “Aha! AT LAST I know how old you are!”

Now what was the number of the bus?

The smallest positive index m such that the Fibonacci number F_m is divisible by the number p is called the rank of apparition of p. If p is prime, one can prove that any Fibonacci number that is divisible by p has an index divisible by m.

Even Fibonaccis have indices divisible by 3. That means that if for some p the rank of apparition of p is divisible by three, all the Fibonaccis that are divisible by p are even. Therefore, no odd Fibonacci divides p. I already discussed this subject in my previous post “9 Divided no Odd Fibonacci.”

Now let’s look more closely at the set of primes that divide no odd Fibonacci. The Fibonacci numbers obey the following identity: F_n+k = (1/2)(F_nL_k + F_kL_n), where L_n are Lucas numbers. From here F_3n = (1/2)F_n(L_2n + L_n²). Like Fibonacci numbers, exactly every third Lucas number is even. Hence, the parity of L_2n is the same as the parity of L_n. Hence, L_2n + L_n² is divisible by 2. Let us denote G_n = (1/2)(L_2n + L_n²).

As we have already discussed before, if no odd Fibonacci is divisible by p, p‘s rank of apparition is of the form 3n which means p divides F_3n and doesn’t divide F_n. Hence, p divides G_n. On the other hand, we can show that G_n = 5F_n² + 3(-1)ⁿ. Hence, the only common divisor that F_n and G_n can have is 3. Let us take any prime divisor s of G_n other than 3. We see that F_3n is divisible by s while F_n is not. The rank of apparition of s must be a divisor of 3n and not a divisor of n. Hence this rank is divisible by 3. Thus we can see that with the exception of 3, the set of prime divisors of elements of G_n is the set of primes that do not divide odd Fibonaccis.

Here’s a bit more info about the sequence G_n. It is sequence A047946 in the Online Encyclopedia of Integer Sequences. It is a recurrence: G_n=2*G_n-1+2*G_n-2-G_n-3. Thus, we have found a recursive sequence, elements of which have a set of prime divisors which with the exception of 3 is the set of primes that do not divide odd Fibonacci numbers.

My favorite puzzle at 2008 MIT Mystery Hunt was the puzzle named Functions. Here is this puzzle:

36 -> 18      A,B
2 -> 1        A,C,G,H,K,L,O
512 -> 256    A,C,H
4 -> 2        A,G,H,Q
320 -> 160    A,R
411 -> 4      B,E,Q
13 -> 3       B,G,K
88 -> 11      C,D
45 -> 9       C,D,F,J,L
48 -> 6       C,G,M,P,Q
4 -> 1        C,K,L,N,O
36 -> 9       D,E,F
66 -> 8       D,E,G,I
10 -> 3       D,G,L
1 -> 3        D,L
150 -> 15     D,M
3 -> 2        E,H,J,K
25 -> 3       E,K,L,N,Q
9477 -> 14    E,M
129 -> 4      E,N,P
55 -> 10      F,J
411 -> 6      F,K,L,M,N
2002 -> 4     F,O,Q
79 -> 8       G,I,L,P
25 -> 20      H,M
176 -> 80     H,R
3665 -> 8     I,N,Q
7 -> 3        K,Q
11 -> 5       L,M
501 -> 2      L,O,P,Q
8190 -> 5     M,O
180 -> 3      O,P
50 -> 10      R

? -> (?)      F,R
(?) -> ?      J,L
(?) -> ?      A,F
(?) -> ?      N,O,Q
? -> (?)      A,D,J
(?) -> ?      D,H
(?) -> ?      G,K,Q
? -> (?)      B,D,M
(?) -> ?      E,H
? -> (?)      D,F,G,L
? -> (?)      C,G,P

Do you know that 1210 is the smallest autobiographical number? You probably do not know what an autobiographical number is. You are right if you think that such a number should be a pompous self-centered number whose only purpose in life is to describe itself.

Here is the formal definition. An autobiographical number is a number N such that the first digit of N counts how many zeroes are in N, the second digit counts how many ones are in N and so on. In our example, 1210 has 1 zero, 2 ones, 1 two and 0 threes.

Let us find all autobiographical numbers using the “zoom-in” method.

1. By definition, the autobiographies can’t have more than 10 digits. It is nice to know that these egotistical numbers can’t be too grand.
2. The sum of the digits in an autobiography equals the number of the digits. Consequently, the sum of the digits will not be more than 10.
3. The first digit is the number of zeroes. As you know, self-respecting integers do not start with a zero. Hence, the number of zeroes is not a zero.
4. Subtracting statement “c” from statement “b” above, we get a resulting statement that the sum of all the digits, except for the first one, is equal to the number of non-zero digits plus 1.
5. That means, other than the first digit, the set of all other non-zero digits consists of several ones and 1 two.
6. Furthermore, the number of ones is either 0, 1 or 2.

Now we continue zooming in in three different directions depending on the number of ones. In this blog entry, I will consider only the case in which there are no ones; I leave the other two cases to the reader.

• If the number of ones is zero, then the only non-zero non-first digit of such a number is 2.
• This 2 should be included in the autobiography; since the third digit of the number is not zero, it must be 2.
• The number has 2 twos.
• It must be 2020.

Here is the full set of autobiographical numbers: 1210, 2020, 21200, 3211000, 42101000, 521001000, 6210001000.

This is the sequence A104786 in the Online Encyclopedia of Integer Sequences (OEIS), where I first encountered the autobiographical numbers.

Autobiographical numbers are very cute numbers. But there is a problem with their name. If there is a notion of an autobiography of a number, then it would be logical to expect that there is a notion of a biography of a number. What would be the logical candidate for a biography of a number? Let us say that given a number N, its biography is another number M such that the first digit of M is the number of zeroes in N, the second digit of M is the number of ones in N and so on.

Of course, for a number to have a biography, we need to assume that none of its digit is present more than nine times. Still there are several problems with the definition of a biography.

The first problem is that if N doesn’t have zeroes, its biography starts with a zero. As numbers don’t start with 0, that biography is not a number! Furthermore, if N starts with 0, it can have a biography but N is not a number. Luckily for this article, a digit string starting with zeroes can’t be an autobiographical string, because the number of zeroes is not a zero. It is a relief that those illegitimate strings that are trying to pretend to be numbers can’t actually be autobiographical.

The second problem with biographies is that a number can have many biographies. Indeed, if a number doesn’t have nines, you can remove or add zeroes at the end of a biography to get another biography of the same number. Since mathematicians like to define things uniquely, we might consider it a problem if a number has several biographies. In real life it is possible to have many biographies of a person. So the second problem is not a big problem. I will call the shortest possible biography of a number the curriculum vitae and the longest possible biography the complete life story.

The third problem is that numbers with the same digits in different permutations have the same biographies. So in a sense a biography follows the life not of a number, but rather the set of its digits.

Suppose for now we allow a biography to start with 0. Also, let us choose the curriculum vitae — the shortest biography in case there could be several. Let us build a sequence of CVs. As an example, we start with 0. Zero’s CV is 1, one’s CV is 01, continuing that we get the following sequence: 0, 1, 01, 11, 02, 101, 12, 011, 12, 011, 12, …. You can see that the CVs’ sequence fell into a cycle in this case. I tried sequences of CVs starting with many numbers. I found that they fall into two cycles. One cycle is described above and another one is: 22, 002, 201, 111, 03, 1001, 22. Can you find another cycle or, alternatively, can you prove that all the numbers that allow the sequence of CVs converge to only these two cycles?

Let us build the sequence of complete biographies, that is, life stories, starting with 0: 0, 1000000000, 9100000000, 8100000001, 7200000010, 7110000100, 6300000100, 7101001000, 6300000100, …. We see that this sequence falls into a cycle of length two. The members of this cycle are legitimate numbers. These numbers are too shy to advertise themselves. But Alice praises Bob, because Bob praises Alice. It’s a very advantageous flattery pattern! I will call such a pair a mutually-praising pair. We’ve already seen mutually-praising strings: 12 and 001. Two other examples of number pairs thriving on each others’ compliments are, first, 130 and 1101, and second, 2210 and 11200.

Are you afraid of Friday the 13th? Here is my only Friday the 13th story.

It was Friday the 13^th, and I was listening to the psychologist Joy Browne’s show. Joy asked her listeners to call in with stories of interesting things that happened to them on Friday the 13th. I wondered why I didn’t remember any stories about Friday the 13^th.

At the end of her show, I went to pick up my mail, where I found a book kindly sent to me by Princeton University Press named Nonplussed!: Mathematical Proof of Implausible Ideas by Julian Havil. I opened this book to a random page, and it was Chapter 13. That was not such a big deal by itself, but in addition, Chapter 13 was titled “Friday the 13th”.

One of the things Julian Havil discussed in the chapter is how often the 13th of the month falls on different days of the week. You might remember from your elementary school education that the Gregorian calendar repeats an entire identical day-of-the-week cycle every 400 years. Hence, it is just a matter of calculation to check on which day of the week the 13th falls the most often.

Can you guess the answer? I am sure you can apply some meta-thinking and derive that there is one special day of the week on which the 13th most frequently falls. You might even guess by now that that day is Friday. Otherwise, why would I write this blog entry? Or what would Mr. Havil have to say in the whole chapter of the aforementioned book?

As we can see, this calculation increases the worry for people who suffer from paraskevidekatriaphobia — the fear of Friday the 13th. The 13th falls on Friday more often than on any other day.

Should we be worried?

Mathematically, the difference between the number of Fridays the 13th and, say, Thursdays the 13th is so small that it can only be observed when we look at the 400 year lifetime of the Gregorian calendar. Many countries have yet to experience the full cycle of the Gregorian calendar. For example, Russia adopted the calendar only in the 20th century. Is this why I am not so very afraid?

On second thought, for people of my generation, who are unlikely to live until the year 2100, the situation is slightly different. In the years between 1901 and 2099 our calendar has a days-of-the-week cycle of 28 years. You can calculate and check that in the period of 28 years, the 13th falls on any day of the week with the same probability. Hence, in events happening around my life time, there is not much to worry about, because Friday is no more special than any other day.

On third thought, a particular individual might see more Fridays on the 13th in his lifetime depending on the exact date of his birth. In my own life up to today, Monday is the most frequently occurring 13th. Maybe that’s why I do not like Mondays.

I stumbled upon the following sentence in the MathWorld article on the Fibonacci numbers: “No odd Fibonacci number is divisible by 17.” I started wondering if there are other numbers like that. Of course there are — no odd Fibonacci number is divisible by 2. But then, an odd number need not be a Fibonacci number in order not to be divisible by 2.

So, let’s forget about 2 and think about odd numbers. How do we know that the infinite Fibonacci sequence never produces an odd number that is divisible by 17? Is 17 the only such odd number? Is 17 the smallest such odd number? If there are many such odd numbers, how do we calculate the corresponding sequence?

We’ll start with a general question: How can we approach puzzles about the divisibility of Fibonacci numbers? Suppose K is an integer. Consider the sequence a_K(n) = F_n(mod K), of Fibonacci numbers modulo K. The cool thing about this sequence is that it is periodic. If it is not immediately obvious to you, think of what happens when a pair of consecutive numbers in the sequence a_K(n) gets repeated. As a bonus for thinking you will get an upper bound estimate for this period.

Let us denote the period of a_K(n) by P_K. By the way, this period is called a Pisano period. From the periodicity and the fact that a_K(0) = 0, we see right away that there are infinitely many Fibonacci numbers divisible by K. Are there odd numbers among them? If we trust MathWorld, then all of the infinitely many Fibonacci numbers divisible by 17 will be even.

How do we examine the divisibility by K for odd Fibonacci numbers? Let us look at the Fibonacci sequence modulo 2. As we just proved, this sequence is periodic. Indeed, every third Fibonacci number is even. And the evenness of a Fibonacci number is equivalent to this number having an index divisible by 3.

Now that we know the indices of even Fibonacci numbers we can come back to the sequence a_K(n). In order to prove that no odd Fibonacci number is divisible by K, it is enough to check that all the zeroes in the sequence a_K(n) have indices divisible by 3. We already have one zero in this sequence at index 0, which is by divisible by 3. Because the sequence a_K(n) is periodic, it will start repeating itself at a_K(P_K) . Hence, we need to check that P_K is divisible by 3 and all the zeroes up to a_K(P_K) have indices divisible by 3. When K = 17 it is not hard to do the calculations manually. If you’d like, try this exercise. To encourage (or perhaps to discourage) you, here’s an estimate of the scope of the work for this exercise: the Pisano period for K = 17 is 36.

After I checked that no odd Fibonacci number is ever divisible by 17, I wanted to find the standard solution for this statement and followed the trail in MathWorld. MathWorld sent me on a library trip where I found the proof of the statement in the book Mathematical Gems III by Ross Honsberger. There was a proof there alright, but it was tailored to 17 and didn’t help me with my questions about other such odd numbers.

The method we developed for 17 can be used to check any other number. I trusted this task to my computer. To speed up my program, I used the fact that the Pisano period for K is never more than 6K. Here is the sequence calculated by my trustworthy computer, which I programmed with, I hope, equal trustworthiness:

• A133246 Odd numbers n with the property that no odd Fibonacci number is divisible by n.
  9, 17, 19, 23, 27, 31, 45, 51, 53, …

The sequence shows that 9 is the smallest odd number that no odd Fibonacci is ever divisible by, and 17 is the smallest odd prime with this same property. Here is a trick question for you: Why is this property of 17 more famous than the same property of 9?

Let us look at the sequence again. Is this sequence infinite? Obviously, it should include all multiples of 9 − hence, it is infinite. What about prime numbers in this sequence? Is there an infinite number of primes such that no odd Fibonacci number is divisible by them? While I do not know the answer, it’s worth investigating this question a little bit further.

From now on, let K be an odd prime. Let us look at the zeroes of the sequence a_K(n) more closely. Suppose a zero first appears at the m-th place of a_K(n). Then a_K(m+1) = a_K(m+2) = a. In this case the sequence starting from the m-th place is proportional modulo K to the sequence a_K(n) starting from the 0-th index. Namely, a_K(n+m) = a*a_K(n) (mod K). As a is mutually prime with K, then a_K(n+m) = 0 iff a_K(n) = 0. From here, for any index g that is a multiple of m, a_K(g) = 0. Furthermore, there are no other zeroes in the sequence a_K(n). Hence, the appearances of 0 in the sequence a_K(n) are periodic with period m.

By the way, m is called a fundamental period; and we just proved that the Pisano period is a multiple of the fundamental period for prime K. Hence, the fact that no odd Fibonacci number is divisible by K is equivalent to the fact that the fundamental period is not divisible by 3. It is like saying that if the smallest positive Fibonacci number divisible by an odd prime K is even, then no odd Fibonacci number is divisible by K.

If the remainder of the fundamental period modulo 3 were random, we would expect that about every third prime number would not divide any odd Fibonacci numbers. In reality there are 561 such primes among the first 1,500 primes (including 2). This is somewhat more than one third. This gives me hope that there is a non-random reason for such primes to exist. Consequently, it may be possible to prove that the sequence of prime numbers that do not divide odd Fibonacci numbers is infinite.

Can you prove that?