Archive for the ‘John Conway’ Category.

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?
  • Bob: You seem to like it too. Please, go ahead.
  • 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:Facebooktwitterredditpinterestlinkedinmail

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:Facebooktwitterredditpinterestlinkedinmail

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:Facebooktwitterredditpinterestlinkedinmail

On the Perfidy of Negative Numbers

Tanya Khovanova, Alexey Radul

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:Facebooktwitterredditpinterestlinkedinmail

The Sexual Side of Life

by John H. Conway as told to Tanya Khovanova

Forty years ago, it took about 18 months for us to find the rules that eventually became the Game of Life. We thought in terms of birth rules and death rules. Maybe one day’s death rule would be a bit too strong compared to its birth rule. So the next day at coffee time we’d either try to weaken the death rule or strengthen the birth rule, but either way, only by a tiny bit. They had to be extremely well-balanced; if the death rule was even slightly too strong then almost every configuration would die off. And conversely, if the birth rule was even a little bit stronger than the death rule, almost every configuration would grow explosively.

What’s wrong with that, you might ask. Well, if the “radius” grows by 1 unit per generation, then after 9 or 10 moves, it’s off the (19 by 19) Go board. We can probably find more Go boards, of course, but after another 20 or so moves it will outflow the coffee table and then it is awfully hard to keep track. We wanted to be able to study configurations for much longer than that, which meant that we had to disallow rules that might lead to linear growth. Of course, we weren’t interested in rules that usually led to collapse.

Who were “we”? Well, I was the chief culprit and had an aim in mind — to find a simple set of rules that would lead to a system able to simulate a universal computer. Von Neumann had already shown that this was possible, but his system had 29 states and a very complicated set of rules. The rest of “us” were mostly graduate students who had no higher aim than amusing themselves. Every now and then some rather older colleagues or visitors took an interest.

So my plan was, first, to find a set of rules that almost always prevented explosive growth and catastrophic collapse. Second, I wanted to study it long enough to learn how it could be “programmed”. I hoped to find a system whose rules were much simpler than Von Neumann’s, preferably with only two states (on and off) per cell, rather than his 29.

I’ll just describe the last few rule fiddles. We had in fact given up on finding a two-state system, in favor of one with three states: 0, A, B. State 0 represented an empty cell, and it was natural to think of A and B as two sexes, but we only found their proper names when Martin Huxley walked by and said, “Actresses and bishops!”

Perhaps I should explain this. There is a British anecdote that starts like this:

“The actress sat on the left side of the bed, and removed her stockings. The bishop, on the right side of the bed, removed his gaiters. Then she unbuttoned her blouse and he took off his shirt…”

You are supposed to be getting excited, but it all ends quite tamely, because it turns out that the bishop was in his palace, while the actress was in her bedsit near the theater. There are lots of stories in England about the actress and the bishop, and if a person says something that has a salacious double meaning, it’s standard to respond “as the actress said to the bishop,” or “as the bishop said to the actress”.

Okay, back to Life! To inhibit explosive growth, we decided to imitate biology by letting death be a consequence of either overcrowding or isolation. The population would only grow if the number of neighbors was neither too large nor too small. Rather surprisingly, this turned out to mean that children had to have three or more parents. Let’s see why. If two parents could give birth, then in the figure below, the parents A and B, who are on the border of the population, would produce children A’ and B’ at the next time step, followed by grandchildren A” and B” and so on, thus giving us linear growth!

The Game of Life ExampleSo we moved to threesomes. Children were born to three parents, made up of both sexes. Moreover, the sex of the child was determined by the sex of its parents — two bishops and one actress would give birth to a little actress, while two actresses and one bishop would produce a tiny bishop. This was “the weaker-sex birth rule,” and it was accompanied by “the sexual frustration death rule,” which made death the punishment for not touching somebody of the opposite sex!

However, the weaker-sex birth rule lived up to its name, by being weaker than the death rule. Remember we weren’t interested in rules that led to disappointingly swift collapses, as the actress said to the bishop. Therefore, we strengthened the birth rule by allowing same-sex conception, but again by applying the weaker-sex rule — so that three actresses would produce a bishop or three bishops an actress. However this strengthened the birth rule too much, causing us to apply the death penalty more often.

We decided to apply the death penalty to those who weren’t touching at least two other people, whatever their sex. At first sight it was not obvious that this was stronger than the sexual frustration rule, but in fact it was, because the weaker-sex rule ensured that the sexes were fairly evenly mixed, so if you were touching at least two other people, there was a good chance that one of them would be of the opposite sex.

According to our new set of rules, the sex of parents played no role except to determine the sex of the children, so we abolished sex. After all, according to the bishop, Life without sex is much cleaner.

This is now called the Game of Life and these rules, at last, turned out to be clean and well-balanced.

Share:Facebooktwitterredditpinterestlinkedinmail

Conway’s Circle

Conway's backJohn Conway has a T-shirt with his theorem on it. I couldn’t miss this picture opportunity and persuaded John to pose for pictures with his back to me. Here is the theorem:

If you continue the sides of a triangle beyond every vertex at the distances equaling to the length of the opposite side, the resulting six points lie on a circle, which is called Conway’s circle.

Conway's circle

Poor John Conway had to stand with his back to me until I figured out the proof of the theorem and realized which point must be the center of Conway’s circle.


Share:Facebooktwitterredditpinterestlinkedinmail

The Second Doomsday Lesson

DoomsdayOn March 5, 2010 I visited Princeton and had dinner with John Conway at Tiger Noodles. He gave me the second Doomsday lesson right there on a napkin. I described the first Doomsday lesson earlier, in which John taught me to calculate the days of the week for 2009. Now was the time to expand that lesson to any year.

As you can see on the photo of the napkin, John uses his fingers to make calculations. The thumb represents the DoomsDay Difference, the number of days your birthday is ahead of DoomsDay for a given year. To calculate this number you have to go back to my previous post.

The index finger represents the century adjustment. For example, the Doomsday for the year 1900 is Wednesday. Conway remembers Wednesday as We-are-in-this-day. He invented his algorithm in the twentieth century, not to mention that most people who use his algorithm were born in that century. Conway remembers the Doomsday for the year 2000 as Twosday.

The next three fingers help you to calculate the adjustment for a particular year. Every non-leap year has 52 weeks and one day. So the Doomsday moves one day of the week forward in one year. A leap year has one extra day, so the Doomsday moves forward two days. Thus, every four years the Doomsday moves five days forward, and, consequently, every twelve years it moves forward to the next day of the week. This fact helps us to simplify our year adjustment by replacing every dozen of years with one day in the week.

The middle finger counts the number of dozens in the last two digits of your year. It is important to use “dozen” instead of “12” as later we will sum up all the numerals, and the word “dozen” will remind us that we do not need to include it in the sum.

The ring finger represents the remainder of the last two digits of the year modulo 12, and the pinkie finger represents the number of leap years in that remainder.

John made two sample calculations on the napkin. The first one was for his own birthday — December 26, 1937. John was born exactly on Doomsday. I suspect that that is the real reason he called his algorithm the Doomsday Algorithm. The century adjustment is Wednesday. There are 3 dozens in 37, with the remainder 1 and 0 leap years in the remainder. When we add four more days to Wednesday, we get Sunday. So John Conway was born on Sunday.

The second napkin example was the day we had dinner: March 5, 2010. March 5 is 5 days ahead of the Doomsday. The century adjustment is Twosday, plus 0 dozens, 10 years in the remainder and 2 leap years in the remainder. 5 + 0 + 10 + 2 equals 3 modulo 7. Hence, we add three days to Tuesday, demonstrating that we dined out together on Friday. But then, we already knew that.

Share:Facebooktwitterredditpinterestlinkedinmail

The Greatest Mathematician Alive

When the Abel Prize was announced in 2001, I got very excited and started wondering who would be the first person to get it. I asked my friends and colleagues who they thought was the greatest mathematician alive. I got the same answer from every person I asked: Alexander Grothendieck. Well, Alexander Grothendieck is not the easiest kind of person to give a prize to, since he rejected the mathematical community and lives in seclusion.

Years later I told this story to my friend Ingrid Daubechies. She pointed out to me that my spontaneous poll was extremely biased. Indeed, I was asking only Russian mathematicians living abroad who belonged to “Gelfand’s school.” Even so, the unanimity of those responses continues to amaze me.

Now several years have passed and it does not seem that Alexander Grothendieck will be awarded the Prize. Sadly, my advisor Israel Gelfand died without getting the Prize either. I am sure I am biased with respect to Gelfand. He was extremely famous in Soviet Russia, although less well-known outside, which may have affected the decision of the Abel’s committee.

I decided to assign some non-subjective numbers to the fame of Gelfand and Grothendieck. On Pi Day, March 14, 2010, I checked the number of Google hits for these two men. All the Google hits in the rest of this essay were obtained on the same day, using only the full names inside quotation marks.

  • Alexander Grothendieck — 95,600
  • Israel Gelfand — 47,900

Google hits do not give us a scientific measurement. If the name is very common, the results will be inflated because they will include hits on other people. On the other hand, if a person has different spellings of their name, the results may be diminished. Also, people who worked in countries with a different alphabet are at a big disadvantage. I tried the Google hits for the complete Russian spelling of Gelfand: “Израиль Моисеевич Гельфанд” and got an impressive 137,000.

Now I want to compare these numbers to the Abel Prize winners’ hits. Here we have another problem. As soon as a person gets a prize, s/he becomes more famous and the number of hits increases. It would be interesting to collect the hits before the prize winner is announced and then to compare that number to the results after the prize announcement and see how much it increases. For this endeavor, the researcher needs to know who the winner is in advance or to collect the data for all the likely candidates.

  • Jean-Pierre Serre — 63,400
  • Michael Atiyah — 34,200
  • Isadore Singer — 44,300
  • Peter Lax — 118,000
  • Lennart Carleson — 47,500
  • Srinivasa Varadhan — 15,800
  • John Thompson — 1,610,000
  • Jacques Tits — 90,900
  • Mikhail Gromov — 61,900

John Thompson is way beyond everyone else’s range because he shares his name with a famous basketball coach. But my point is that Gelfand and Grothendieck could have been perfect additions to this list.

Pickover

I have this fun book at home written by Clifford Pickover and titled Wonders of Numbers: Adventures in Mathematics, Mind, and Meaning. It was published before the first Abel Prize was awarded. Chapter 38 of this book is called “A Ranking of the 10 Most Influential Mathematicians Alive Today.” The chapter is based on surveys and interviews with mathematicians.

The most puzzling thing about this list is that there is no overlap with the Abel Prize winners. Here is the list with the corresponding Google hits.

  1. Andrew Wiles — 64,900
  2. Donald Coxeter — 25,200
  3. Roger Penrose — 214,000
  4. Edward Witten — 45,700
  5. William Thurston — 96,000
  6. Stephen Smale — 151,000
  7. Robert Langlands — 48,700
  8. Michael Freedman — 46,200
  9. John Conway — 203,000
  10. Alexander Grothendieck — 95,600

Since there are other great mathematicians with a lot of hits, I started trying random names. In the list below, I didn’t include mathematicians who had someone else appear on the first results page of my search. For example, there exists a film director named Richard Stanley. So here are my relatively “clean” results.

  • Martin Gardner — 292,000
  • Ingrid Daubechies — 76,900
  • Timothy Gowers — 90,500
  • Persi Diaconis — 84,700
  • Michael Sipser — 103,000
  • James Harris Simons — 107,000
  • Elliott Lieb — 86,100

If prizes were awarded by hits, even when the search is polluted by other people with the same name, then the first five to receive them would have been:

  1. John Thompson — 1,610,000
  2. Martin Gardner — 292,000
  3. Roger Penrose — 214,000
  4. John Conway — 203,000
  5. Stephen Smale — 151,000

If we had included other languages, then Gelfand might have made the top five with his 48,000 English-language hits plus 137,000 Russian hits.

This may not be the most scientific way to select the greatest living mathematician. That’s why I’m asking you to tell me, in the comments section, who you would vote for.

Share:Facebooktwitterredditpinterestlinkedinmail

Conway’s Recipe for Success

One fine day in January 2010, John H. Conway shared with me his recipe for success.

1. Work at several problems at a time. If you only work on one problem and get stuck, you might get depressed. It is nice to have an easier back-up problem. The back-up problem will work as an anti-depressant and will allow you to go back to your difficult problem in a better mood. John told me that for him the best approach is to juggle six problems at a time.

2. Pick your problems with specific goals in mind. The problems you work on shouldn’t be picked at random. They should balance each other. Here is the list of projects he suggests you have:

  • Big problem. One problem should be both difficult and important. It should be your personal equivalent to the Riemann hypothesis. It is not wise to put all your time into such a problem. It most probably will make you depressed without making you successful. But it is nice to get back to your big problem from time to time. What if you do stumble on a productive idea? That may lead you to become famous without having sacrificed everything.
  • Workable problem. You should have one problem where it’s clear what to do. It’s best if this problem requires a lot of tedious work. As soon as you get stuck on other problems, you can go back to this problem and move forward on the next steps. This will revive your sense of accomplishment. It is great to have a problem around that can be advanced when you do not feel creative or when you are tired.
  • Book problem. Consider the book you are working on as one of your problems. If you’re always writing a book, you’ll write many of them. If you’re not in the mood to be writing prose, then work on math problems that will be in your book.
  • Fun problem. Life is hardly worth living if you are not having fun. You should always have at least one problem that you do for fun.

3. Enjoy your life. Important problems should never interfere with having fun. When John Conway referred to having fun, I thought that he was only talking about mathematics. On second thought, I’m not so sure.

Share:Facebooktwitterredditpinterestlinkedinmail

Destinies of Numbers

Do you know that numbers have destinies? Well, to have a destiny, a number needs to have a life, or in mathematical terms, destinies are defined with respect to an operation or a function.

I know the term “destiny” from John Conway, the creator of the Game of Life. It would be harmonious to assume that he suggested this term.

Case 1. SOD. Suppose our function is the sum of digits of a number, denoted as SOD. Then the trajectory of a number k is the sequence a(n), such that a(0) = k and a(n+1) = SOD(a(n)).

Two numbers have the same destiny with respect to SOD if the tails of their trajectories coincide. Suppose a(n) and b(n) are two trajectories. Then the numbers a(0) and b(0) on which these trajectories are build have the same destiny if there exist N and M, such that for any j, a(N+j) = b(M+j). In particular, all numbers in the same trajectory a(n) have the same destiny.

In the above example of SOD, any trajectory of a positive integer ends with a one-digit non-zero number repeating many times. It follows that all the natural numbers have 9 different destinies with respect to SOD, which only depend on the remainder of the number modulo 9.

Given an operation, we can build another sequence that is called “the first occurrence of a new destiny”. This is the sequence of numbers c(n) such that c(n) is the smallest number with its destiny. For the SOD operation, the sequence of the first occurrences of new destinies is finite and is equal to: 1, 2, 3, 4, 5, 6, 7, 8, 9.

Case 2. The next prime. Let us consider a different example. Let the function f(n) be the next prime after n. Then wherever we start, the tail of the trajectory with respect to the function f(n) is a sequence of consecutive prime numbers. Therefore, with respect to this function all integers have the same destiny.

Case 3. Reverse. Suppose f(n) is a reverse of n. If a number is a palindrome, then its trajectory is a one-cycle consisting of that number. If a number is not a palindrome, then its trajectory is a two-cycle consisting of a number and its reverse. The first appearance of a new destiny is sequence A131058 — a list of numbers n whose reverse is not less than n. In this case, instead of studying destinies, it might be more interesting to study types of destinies. For this operation we have two types: one-cycles for palindromic integers and two-cycles for non-palindromic integers.

Case 4. The sum of proper divisors. For the next example, let f(n) denote the sum of proper divisors. Let’s look at the trajectory of 15: it is 15, 9, 4, 3, 1, 0. The sum of proper divisors of zero is not-defined or is equal to infinity, whichever you prefer. So, let us say the trajectory of 15 is finite, and ends with 1, 0. This situation makes the definition of destinies more complicated, but it is appropriate to say that finite sequences have the same destinies if they end with the same number. For our example of sums of proper divisors all finite sequences end with 0. Thus all the numbers whose trajectories are finite have the same destinies. The sequence of new destinies starts 1, 6, 28, 220, …; and we do not know what the next number is because for 276 we do not know the behavior of its trajectory. Even when we know what kind of life the number is living the destinies are not always clear.

Case 5. TITO. The next interesting example is the TITO operation. TITO is an abbreviation of “Turning Inside, Turning Outside”. By definition, to calculate TITO(n) you need to reverse the prime factors of n, multiply them back together (with multiplicities) and reverse the result. For example, to calculate TITO(68), we first find prime factors of 68, which are 2, 2 and 17. We reverse them and multiply: 2*2*71 = 284. Then we reverse the result: TITO(68) = 482.

It is easy to see that prime numbers are among the fixed points of the TITO operation. That means all prime numbers have different destinies of the same type: they end with a one-cycle. There are numbers other than prime that have one-cycle destinies. For example, a palindrome that is a product of palindromic primes is a fixed point of the TITO operation. There are other cases too: for example 26 is a fixed point, but is neither prime nor palindromic. There are numbers that have one-cycle destinies, but are not the fixed points of TITO operation themselves. For example, the trajectory of 49 starts with the following sequence: 49, 94, 841, 4648, 8212, 80041, 415003, 282145, 54796, 849667, 3652951, 35429422, 2941879, 27075955, 5275759, 5275759, 5275759. ….

There are numbers that generate two-cycles. For example, 12 and 156. For numbers n that have only palindromic factors, TITO(n) is equal to the reverse of n. If n is not a palindrome and the reverse of n has only palindromic factors, then the trajectory of n is a two-cycle. Not all two-cycles are like that. Take for example 291 which is a product of primes 3 and 97. Thus, TITO(291) is the reverse of 3*79, which is equal to 732. On the other hand, 732 = 2*2*3*61. Hence, TITO(732) = reverse(2*2*3*16) = 291.

There are longer cycles too. Take for example 15, which generates a cycle of length 7: 15, 51, 312, 447, 3282, 744, 213, 15, …. Also, for some numbers we do not know if there is a cycle. The smallest number for which I myself do not know whether the trajectory tends to infinity or collapses into a cycle is 78.

For the TITO operation we might be more interested in types of destinies. Personally, I am interested not only in the types of destinies, but also in sets of numbers that have the same destinies for the same reasons. For example, I am interested in dividing numbers of one-cycle TITO destinies into three groups: primes, palindromes with palindromic primes and other cases.

Case 6. RATS. I kept the RATS operation for dessert as, in my opinion, it is the most interesting operation with respect to destinies. RATS is the abbreviation of Reverse Add Then Sort. For example, to calculate RATS(732) we need to reverse 732 getting 237, then add 732 and 237 together getting 969, then sort the digits. Thus, RATS(732) = 699.

Let’s look at the RATS sequence starting with one: 1, 2, 4, 8, 16, 77, 145, 668, 1345, 6677, 13444, 55778, 133345, 666677, 1333444, 5567777, 12333445, 66666677, 133333444, 556667777, 1233334444, 5566667777, 12333334444, 55666667777, 123333334444, 556666667777, …. We can prove that this sequence is infinite, because numbers fall into a repetitive pattern with an increasing number of digits. This is the first such example in this discussion. John Conway calls the destiny of 1 “the creeper”. Conway conjectured that RATS destinies are either the creeper or a cycle.

New destinies do not appear too often in this sequence. That is why the sequence of new destinies might be of interest: 1, 3, 9, 29, 69, 2079, 3999, 6999, 10677, 20169, …. This sequence is A161590 in the Online Encyclopedia of Integer Sequences and it needs more terms. The length of the corresponding periods starting from the second term are: 8, 2, 18, 2, 2, 2, 14, which is the sequence A161593.

Destinies are kinda fun.

Share:Facebooktwitterredditpinterestlinkedinmail