Archive for the ‘John Conway’ Category.

## Shapes of Symbols in Latin Squares

Once John Conway showed me a cute way to enumerate Latin squares of size 4, up to the movements of the plane. It was a joint result with Alex Ryba, which is now written in a paper Kenning KenKen.

For starters, I want to remind you that a Latin square of size n is an n by n table filled with integers 1 through n, so that every row and column doesn’t have repeated integers. KenKen is a game that John Conway likes, where you need to recover a Latin square given some information about it.

Let me start by describing a particular shape of four cells that one digit can occupy in a Latin square of size 4. There are only seven different shapes. To get to the beautiful result, we need to number these seven shapes in a particular order starting from zero. The shapes are shown below.

There are 12 different Latin squares up to movements of the square and relabeling the digits. Here is how Conway and Ryba matches shapes and squares. For each Latin square, take the shapes of all four digits, remove the duplicate shape numbers and sum the leftover shape numbers. You will get a unique number from 1 to 12 that represents a particular Latin square. For example, consider the square on the picture below.

Digit 1 is shape 4, digits 2 and 4 form shape 2, and digit 3 forms shape 6. Shape 2 is used twice, and we ignore multiplicities. So we have shapes 2, 4, and 6 used. The resulting Latin square is number 2 + 4 + 6, that is 12. It is a fun exercise to try to find all the squares. For example, square 1 can only use shapes 0 and 1. But shape 1 uses exactly one corner. So the first square should use each of the digits in shape 1.

John likes finding interesting ways to remember which shape is which. You can find his and Alex’s suggestions in the paper which Alex submitted to the arxiv.

Oops! While I was writing this essay, arxiv rejected the paper.

Share:

## My Last Visit with John Conway

John Conway came to the 2017 MOVES conference and told me that he wanted to talk to me about subprime fibs. The subprime Fibonacci sequence was invented by John Conway, and I wrote a paper about it. The paper, Conway’s Subprime Fibonacci Sequences, wasn’t written with John, but rather with Richard Guy and Julian Salazar, and is published in Mathematics Magazine.

I wanted to visit my friend Julia, who lives in Princeton, and this was a good opportunity to discuss the mysteries of subprime fibs with John. On my second day in Princeton, I came to the math department around 3:00 pm carrying some apples. John never goes out for lunch, as he has trouble walking, so he is always hungry by the end of his work day. Thus, each time I go visit him, I come with food. We have very different tastes in apples: unlike me, he likes his apples unwashed.

Anyway, by the time I arrived to the department, John had already left. This was somewhat unusual, so I called him. He sounded weird and not very coherent, as if he wasn’t feeling well. Considering also that he had left early, I started to worry. Unfortunately, there was a lot of background noise during our conversation and I only understood that he was at a pizza place. John walks very slowly, so he couldn’t have gone too far away from campus. I found him in the second pizza place I checked. It was Tiger’s Pizza. He told me that he felt very sleepy and tired. However, I was gratified to see how much having an interested listener gave him energy. He started telling me stories of his trip to Germany a long time ago. He had already eaten, but decided to have some more fries. As a perfect gentleman he offered me some, but I didn’t want any.

At some point he dropped a couple of fries on the floor. He tried to reach them and I jumped to help. That was a mistake. I actually know that he likes proving to me and to himself that he can do stuff independently. He accepts my help when I am subtle about it, or when it is unavoidable. Anyway, he looked at me angrily and I backed off. He picked up his fries from the floor and ate them.

I liked his T-shirt and tried to take a picture of it. As you can see, I am no photographer. The T-shirt shows a test question: Name the triangles. Then it features three triangles: an equilateral, isosceles, and right. It also provides someone’s answers to this naming test: Geoffrey, Frederick, Eugene.

John asked me if I am more scared of Donald Trump or Kim Jong Un. We agreed that Trump is scarier. At this time he seemed his usual self.

I offered John a ride home, as I do whenever I visit him. He was very glad as he felt very tired. He started to get up. This time, I remembered not to try to help. He couldn’t get up, I waited. He tried to push his weight off the table top, but the table was wobbly. I leaned on the table, as if to rest. We often play this sort of game in which he welcomes my help as long as we both pretend that I’m not helping.

My car was a block away and he wanted to walk the block. But after making two steps out of the pizzeria he changed his mind and asked me to bring the car to him. This was the first time ever. This visit he was so much worse than ever before.

On the drive to his place, he gave me a puzzle:

John’s puzzle. Given a Mebius strip with a hole, how do you embed it in 3-D so that the two circular borders of the surface are equivalent?

I dropped him off at his house and offered to walk him to the door. He refused. I sat in my car and watched him walking very slowly along his path. I had this sinking feeling in my gut that I was seeing John for the last time. I drove away, once he disappeared behind his door.

On my way back to Boston I visited my friend Vitaly in East Brunswick, and the next day my high school friend Olga in Edison. In Edison, my car started beeping and I panicked. I was far away from home, and didn’t want to be stuck in NJ. I started to look for the source of the sound. It was John’s phone. As always, my gut feeling deceived me: I had to go back to Princeton.

I drove back to John’s apartment. His door was unlocked and I entered. He was resting in bed. He was greatly annoyed at being disturbed. I explained the reason, and gave him his phone. He took the phone and said, “Off you go.” I had this sinking feeling in my gut that these words would be the last words that I would hear from John.

Share:

## Hidden Birthdays in the Winning Ways

John Conway told me a story about the book Winning Ways for Your Mathematical Plays that he wrote jointly with Elwyn Berlekamp and Richard Guy. The book includes the birthdays of each of the book’s three authors. The book has short author bios, each of which mentions that author’s birthday. But in addition, each birthday is hidden inside the book.

Elwyn Berlekamp was born on September 6, 1940, and this date is pictured on a tombstone on page 318 of Volume 2. That chapter is about suiciding moves.

John Conway was born on December 26, 1937. The Doomsday algorithm to calculate the day of the week for a given date is discussed on page 903 of Volume 4. Boxing Day in 1937 is chosen as an example. Boxing Day is a British holiday that originated when wealthy people gave gift boxes to servants the day after Christmas. John Conway was born on Boxing Day. Hidden behind this calculation that it was a Sunday, is the fact that it was Conway’s day of birth.

Richard Guy was born on September 30, 1916. He often uses his initials RKG for Richard Kenneth Guy. Maybe because of that he got the nickname Archangel. If you look into the index pages of Volumes 3 and 4, you will find an entry for Archangel that refers to pages 9, 30, 1916. Not only are there no mentions of “Archangel ” on pages 9 and 30, the book only has 1004 pages.

The trio of Berlecamp, Conway, and Guy will be the topic of an upcoming MOVES (Mathematics Of Various Entertaining Subjects) conference at the Museum of Mathematics.

Share:

## Genius at Play

The last time I visited John Horton Conway, he showed me a book, Genius At Play: The Curious Mind of John Horton Conway by Siobhan Roberts. It had nothing to do with him wanting to brag about the book. Nothing, nothing at all.

He just wanted to show me a picture from the book. While he was browsing this book about himself, I took a photo of him (featured on the left). The picture he was looking for was on page 314. I am reproducing it here (Photo by Michael A. Stecker, courtesy of Stephen D. Miller).

When we finally found the picture, he asked me how many tennis balls were in it. I smelled a trick question right away and didn’t bite. I shrugged. It appears that one of the balls at the far corner at the base of the pyramid had rolled away. So there was one less ball than I would have calculated. So, how many balls are there?

Share:

## How Well Do You Know Your Dice?

Each time I see John Conway he teaches me something new. At the Gathering for Gardner he decided to quiz me on how well I know a regular six-sided die. I said with some pride that the opposite sides sum up to 7. He said, “This is the first level of knowledge.” So much for my pride. I immediately realized that the next level would be to know how all the numbers are located relative to each other. I vaguely remembered that in the corner where 1, 2, and 3 meet, the numbers 1, 2, and 3 are arranged in counter-clockwise order.

Here’s how John taught me to remember every corner. There are two types of corners. In the first type numbers form an arithmetic progression. John calls such numbers counters. He chose that name so that it would be easy to remember that counters are arranged in counter-clockwise order. The other numbers he calls chaos: their increasing sequence goes clockwise.

Once I grasped that, I relaxed thinking that now I know dice. “What about the third level?” he asked. “What third level?” “Now that you know which number goes on which side, you need to know how the dots are arranged.” Luckily, there are only three sides on which the dots are not placed with rotational symmetry: 2, 3, and 6. And they all meet in a corner, which John calls the home corner. The rule is that the diagonals formed by the dots on the sides with 2, 3, and 6, meet in the home corner. You might argue that 6 doesn’t have a diagonal. But if you look at 6, you can always connect the dots to form the letters N or Z, depending on the orientation of the die. When you lay the letter N on its side, it becomes the letter Z. Thus they define the same diagonal. This diagonal has to meet the diagonals from 2 and 3 in the corner.

When I came home from the conference I picked up a die and checked that the rules work. There are 8 corners. It is enough to remember one corner of numbers to recover the other numbers by using the opposite sum rule. But it is nice to have a simple rule that allows us to bypass the calculation. Four of the corners have numbers in arithmetic progression: 1:2:3, 1:3:5, 2:4:6, and 4:5:6. They are counters and they are arranged counter-clockwise. The other four corners are: 1:2:4, 1:4:5, 2:3:6, and 3:5:6, and they are arranged clockwise.

I wanted to provide a picture of a die for this post and went online to see if I could grab one. Many of the graphic images of dice, as opposed to photographs, were arranged incorrectly. Clearly these visual artists did not study dice with John Conway.

Then I decided to check my own collection of dice. Most of them are correct. The ones that are incorrect look less professional. Here is the picture. The ones on the right are correct.

Share:

## Conway’s Subprime Fibonacci Sequences

The Fibonacci sequence is all about addition, right? Indeed, every element Fn of the Fibonacci sequence is the sum of the two previous elements: Fn = Fn-1 + Fn-2. Looking closer we see that the Fibonacci sequence grows like a geometric progression φn, where φ is the golden ratio. In addition, the Fibonacci sequence is a divisibility sequence. Namely, if m divides n, then Fm divides Fn.

My point: we define the sequence through addition, and then multiplication magically appears by itself. What would happen if we tweak the rule and combine addition and multiplication there?

John Conway did just that: namely, he invented a new sequence, or more precisely a series of sequences depending on the pair of the starting numbers. The sequences are called Conway’s subprime Fibonacci sequences. The rule is: the next term is the sum of the two previous terms, and, if the sum is composite, it is divided by its least prime factor.

Let me illustrate what is going on. First we start with two integers. Let’s take 1 and 1 as in the Fibonacci sequence. Then the next term is 2, and because it is prime and we do not divide by anything. The next two terms are 3 and 5. After that the sum of two terms is 8, which is now composite and it is divided by 2. So the sequence goes: 1, 1, 2, 3, 5, 4, 3, 7, 5, 6, 11 and so on.

The subprime Fibonacci sequences excite me very much. Not only does adding some multiplication to the rule make sense to me, but also, the sequences are fun to play with. I got so excited that I even coauthored a paper about these sequences titled, not surprisingly, Conway’s Subprime Fibonacci Sequences. The paper is written jointly with Richard K. Guy and Julian Salazar, and is available at the arXiv:1207.5099.

We can start a subprime Fibonacci sequence with any two positive numbers. You can see that such a sequence doesn’t grow fast, because we divide the terms too often. We present a heuristic argument in the paper that allows us to conjecture that no subprime Fibonacci sequence grows indefinitely, but they all start cycling. The conjecture is not proven and I dare you to try.

Meanwhile, the sequences are a lot of fun and I suggest a couple of exercises for you:

• Prove that there are no cycles of length two or three.
• Prove that the maximum number in a non-trivial cycle is prime.
• Prove that the smallest number in a non-trivial cycle is more than one. You can prove that it is more than 6 for extra credit.

By the way, a trivial cycle is the boring thing that happens if we start a sequence with two identical numbers n bigger than one: n, n, n, n, ….

Have fun.

Share:

## Finchley Central

### by Sergei Bernstein, Tanya Khovanova and Alexey Radul

Here is a game that John Conway popularizes. It is called “Finchley Central,” which is a station of the London Underground. The game goes as follows. Alice and Bob take turns naming London Underground stations, in any order. The first person to say “Finchley Central” wins.

Alice, who starts, can just name the station. But then Bob will give her a look. It is not fun to win a game on the first turn. To avoid appearing rude, Alice will not start with “Finchley Central.” It would be impolite of Bob to take advantage of Alice’s generosity, so he also won’t say “Finchley Central.” The game might continue like this for a while.

The game has a hidden agenda: winning it after 10 turns will supply many more bragging rights than winning it right away would. We can make this hidden agenda explicit by assigning a value to the honor of continuing the game. For example, suppose every time Alice (or Bob) says a station, she puts one dollar into the pile. The person who says “Finchley Central” first takes all the money from the pile. The implicit goal of the game becomes explicit: you want to say “Finchley Central” right before your opponent says it.

By the way, Finchley Central is not actually a particularly central station — it is the station between Finchley East and Finchley West, serving the relatively small place called Finchley; and is not even under ground. It has the distinction of being one of the oldest still-standing pieces of London Underground physical plant, because plans to rebuild it were interrupted on account of World War II and never resumed. It also has the distinction of having served the home of the guy (an employee of the Underground system) who had the brilliant idea that since the Underground was, indeed, mostly under ground, the right way to map it was topologically, rather than geographically.

Here is another way to model the game. Alice writes an odd number on a piece of paper, and Bob writes an even number. When they compare, the person who wrote a smaller number wins that number of dollars. This version loses the psychological aspect. When you take turns, it is to your advantage to read the non-verbal signs of your opponent to see when s/he is getting ready to drop the bomb.

People play this game in real life. Here are Alice and Bob looking at the last piece of a mouth-watering Tiramisu:

• Alice: You look like you want this piece of cake. Why don’t you take it?
• Alice: I am fine. You take it.
• Bob: You have it; I insist.

At this point Alice wins with some extra brownie points for being polite.

We can model the honor points differently. We can say you will be the most proud of the game if you name the station write before you opponent is about to do so. Then the model is: everyone writes down their next move; if your move is Finchley Central when your opponent’s next move was going to be Finchley Central, then you win.

Here we suggest another game that we call “Reverse Finchley Central.” Alice and Bob name London Underground stations in turns and the person who names “Finchley Central” first loses. This game can continue until all the stations are exhausted, if the players are forbidden to repeat them, or it can continue indefinitely otherwise. But this is quite tiresome. The hidden agenda would be to not waste too much time. Clearly the person who values time less will win.

But let us model this game. We want to fix the value of winning. Let us set aside ten dollars for the winner. On their turn, each player puts one dollar into the pile, and as soon as one of the players says “Finchley Central,” the other one wins and takes the ten dollars. The pile goes to charity. Alternatively, Alice and Bob can each write a number. The person with the larger number wins the prize, while both have to pay the smaller number to charity.

We play this game with our parents. They nag us to do the dishes. We resist. Then they give up and do the dishes themselves. They lose, but we all pay with our nerves for nagging or being nagged at. Later our parents get their revenge when we have children of our own.

Share:

## Tell Time Looking at the Night Sky

John Conway taught me how to tell time at night. But first I need to explain the notions of the “time in the sky” and the “time in the year.”

The clock in the sky. Look at Polaris and treat it as the center of a clock. The up direction corresponds to 12:00. Now we need to find a hand. If you find Polaris the way I do, first you locate the Big Dipper. Then you draw a line through the two stars that are furthest away from the Big Dipper’s handle. The line passes through Polaris and is your “hour” hand. Now you can read the time in the sky.

The hand of the clock in the sky makes a full rotation in approximately 24 hours. So if you stare at the sky for a long time, you can calculate the time you spent staring. Keep in mind that the hand in the sky clock is twice as slow as the hour hand, and it turns counter-clockwise. So to figure out how long you’re looking into the sky, take the sky-time when you start staring, subtract the sky-time when you stop staring and multiply the result by 2.

To calculate the absolute time, we need to adjust for the day in the year.

The clock in the year. A year has twelve months and a clock has twelve hours. How convenient. You can treat each month as one hour. In addition as a month has about 30 days and an hour has exactly 60 minutes, we should count a day as two minutes. Thus, January 25 is 1:50.

Fact: on March 7th at midnight the clock in the sky shows 12:00. March 7th corresponds to 3:15. So to calculate the solar time you need to add up the time in the sky and the time in the year and multiply it by 2. Then subtracting the result from 6:30, which is twice 3:15, you get the solar time.

You are almost ready. You might need to adjust for daylight savings time or for peculiarities of your time zone.

This time formula is not very precise. But if you are looking into the sky and you do not have your watch or cell phone with you, you probably do not need to know the time precisely.

Share:

## A Nerd’s Way to Walk Up the Stairs

The last time I talked to John H. Conway, he taught me to walk up the stairs. It’s not that I didn’t know how to do that, but he reminded me that a nerd’s goal in climbing the steps is to establish the number of steps at the end of the flight. Since it is boring to just count the stairs, we’re lucky to have John’s fun system.

His invention is simple. Your steps should be in a cycle: short, long, long. Long in this case means a double step. Thus, you will cover five stairs in one short-long-long cycle. In addition, you should always start the first cycle on the same foot. Suppose you start on the left foot, then after two cycles you are back on the left foot, having covered ten stairs. While you are walking the stairs in this way, it is clear where you are in the cycle. By the end of the staircase, you will know the number of stairs modulo ten. Usually there are not a lot of stairs in a staircase, so you can easily estimate the total if you know the last digit of that number.

I guess I am not a true nerd. I have lived in my apartment for eight years and have never bothered to count the number of steps. That is, until now. Having climbed my staircase using John’s method, I now know that the ominous total is 13. Oh dear.

Share:

## On the Perfidy of Negative Numbers

Perfidy is to parity as odious is to odd and evil is to even. As a reminder, odious numbers are numbers with an odd number of ones in their binary expansions. From here you can extrapolate what the evil numbers are and the fact that the perfidy of an integer is the parity of the number of ones in its binary expansion. We live in a terrible world: all numbers are perfidious.

So why are we writing about the perfidy of negative numbers? One would expect it to be a natural extension of the perfidy of positive numbers, but it turns out that the naive way of defining it doesn’t work at all. Is there hope? Could negative numbers be innocent of evil and free of odiousness? Is zero an impenetrable bulwark against perfidy? Not quite, but something interesting does happen to evil as it tries to cross zero. Read on.

To define perfidy for negative numbers, let us study how perfidy behaves for positive numbers. It is easiest to think about the perfidies of power-of-two-sized chunks of non-negative integers at a time. Let us denote by Tn the string of perfidies of the integers from 0 to 2n−1, with evil being zero and odious being 1. So T0 = 0, T1 = 01, T2 = 0110, T3 = 01101001, …. The recurrence relation governing the Tn is Tn+1 = TnTn, where T is the bitwise negation of the string T, and juxtaposition is concatenation. The limit of this as n tends to infinity is the (infinite) sequence of perfidies of non-negative integers. This sequence is called the Thue-Morse sequence: 0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,….

So defining the perfidy of negative numbers is equivalent to extending the Thue-Morse sequence to the left. If we are to define “the” perfidy of negative numbers, that definition should preserve most of the properties of the Thue-Morse sequence after extension.

So, let’s see. We asked around, and most people said that the binary expansion of a negative integer should be the binary expansion of its absolute value, but with a minus sign. Defining perfidy as parity of number of ones in this binary expansion corresponds to the following extended Thue-Morse sequence in which we mark values corresponding to negative indices with bold font: … 0, 1, 1, 0, 1, 1, 0, ….

One of the major properties of the Thue-Morse sequence is its fractal property: if you replace every zero of the Thue-Morse sequence by 0,1 and every one by 1,0, you will get the Thue-Morse sequence back. Clearly, our new extended sequence doesn’t have this property.

Another set of properties for the Thue-Morse sequence, called avoidance properties, is a long list of patterns that the sequence avoids. For example, the Thue-Morse sequence doesn’t contain any overlapping squares — patterns axaxa, where a is a character and x is a word. But you can see above, our first extension contains it. So this definition is wrong, not just once but twice (and two wrongs only make a right under very unusual circumstances). Perfidy is stymied by the cross-over from zero to minus one. Are negative numbers protected from the ravages of evil? (and odiousness?)

Unfortunately, there are many people, for example John Conway, who inadvertently extend the reach of perfidy by arguing that the binary expansion of a negative integer should be different. Indulge in a flight of fancy and imagine the binary expansion that consists of infinitely many ones to the left: …1111. What happens when you add 1 to it? The carry gets pushed infinitely far away, and you get …000000 — zero. So it is quite reasonable to let …1111 be the binary expansion of −1. Similarly, the string …1110 represents −2, …1101 represents −3, etc. Continuing this we see that the binary expansion of a negative integer −n is the bitwise negation of the binary expansion of n − 1 (including the leading zeros). This is called the Two’s complement representation.

Why is two’s complement a reasonable representation? Suppose you were trying to invent a binary notation for negative numbers, but you wanted to pursue uniformity by not using a minus sign. The problem is that the standard definition of the binary representation allows you to represent only positive numbers. But you can solve this problem with modular arithmetic: modulo any fixed N, every negative number is equivalent to some positive number (by adding enough multiples of N), so you can just represent it by representing that positive number. If you choose N to be a power of two, modding out by it is just truncation of the binary representation. If you let those powers of two tend to infinity, you get the two’s complement representation described above.

Aside: When you are building a computer, uniformity is money, because special cases cost special transistors. The two’s complement idea lets one build arithmetic units that just operate on positive numbers with some number of bits (effectively doing arithmetic modulo 2k), and leave the question of negativeness to the choice of representatives of those equivalence classes.

If we take two’s complement as the binary expansion of negative numbers, how will we define the perfidy? Is the number of ones in the infinite string …1111 corresponding to −1 even or odd?

We can’t answer that question, but we know for every binary expansion of negative numbers the parity of the number of zeroes. Thus we can divide all negative integers in two classes with different perfidy. We just do not know which one is which.

Let us consider two cases. In the first case we consider a negative number odious if the number of zeroes in its binary expansion is odd. The corresponding extended Thue-Morse sequence is: … 0, 1, 1, 0, 0, 1, 1, 0, …. The negative half is the reflection of the classical Thue-Morse sequence. In the second case we consider a negative number odious if the number of zeroes in its binary expansion is even. The corresponding extended Thue-Morse sequence is: … 1, 0, 0, 1, 0, 1, 1, 0, …. The negative half is the bitwise negation of the reflection of the classical Thue-Morse sequence.

Can we say that one of the sequences is better than the other? Both of them respect the fractal property of the classical Thue-Morse sequence. Let us look at the avoidance properties. The avoidance properties are symmetric with respect to switching zeroes with ones and with respect to changing the direction of the sequence. Hence, the negation, the reflection, and the reflection of the negation of the Thue-Morse sequence will continue to respect these properties.

Thus, we only need to check the avoidance properties of the finite subsequences that span both negative and non-negative indices. We claim that for both definitions of perfidy, any finite middle subsequence of the extended Thue-Morse sequence occurs as a subsequence in the classical Thue-Morse sequence. So any avoidance properties that are true for the Thue-Morse sequence will also be true for both extensions.

Indeed, it is easy to show that the strings T2n defined above are palindromes. So for the first definition of perfidy the string in the middle will be a substring of T2nT2n for some large n, and for the second definition a substring of T2nT2n. But the classical Thue-Morse sequence contains the subsequence T2nT2nT2nT2nT2nT2nT2nT2n. So whichever way we extend the Thue-Morse sequence to the left any finite middle part will always be a repetition of a piece in the classical Thue-Morse sequence. Thus, all the avoidance properties will hold.

We see that there are two logical ways to define perfidy for negative integers. There are two clear groups of numbers with the same perfidy, but which is called evil and which odious is interchangeable. So evil doesn’t stop at zero after all, but at least it gets an identity crisis.

Share: