Archive for the ‘John Conway’ Category.

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!

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

Conway’s Circle

John 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.

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:

The Second Doomsday Lesson

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

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
• Peter Lax — 118,000
• Lennart Carleson — 47,500
• 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.

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:

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:

Langton’s Ant’s Life

Langton’s ant travels on the infinite square grid, colored black and white. At each time step the ant moves one cell forward. The ant’s direction changes according to the color of the cell he moves onto. The ant turns 90 degrees left if the cell is white, and 90 degrees right if the cell is black. After that, the cell he is on changes its color to the opposite color.

There is a symmetry of time and space for this ant. If at any point of the ant’s travel, someone interferes and reverses the ant’s direction in between the cells, the ant and the grid will traverse the steps and stages back to the starting point.

Let’s give this ant a life. I mean, let’s place him inside the Game of Life invented by John H. Conway. In addition to the Langton’s ant’s rules, I want the cells to change colors according to the rules of the Game of Life.

Let me remind you of the rules of Conway’s Game of Life. We call black cells live cells and white cells dead cells. Black is life and white is death. The cell has eight neighbors — horizontal, vertical, diagonal. At each time step:

• A cell dies of agoraphobia, if it has more than three neighbors.
• A cell dies of boredom, if it has less than two neighbors.
• A dead cell can be born again, if it has exactly three neighbors.
• Otherwise, the cell’s status doesn’t change.

So, our ant will be traveling in this dying and reproducing population and correcting nature’s mistakes. He revives dead cells and kills live cells.

There is an ambiguity in this ant’s life description. The life can happen at two different moments. In the first ant’s world, the ant jumps from one cell to the next, and while he is in the air, the cells have time to copulate, give birth and die. Upon landing, the ant changes direction and uses his magic wand to change the life status of its landing cell. In the second ant’s world, the ant moves to the destination cell, changes its own direction and the status of the cell and then takes a smoke. All the fun, sex and death happen while he is enjoying his cigarette.

The ant’s life has symmetry in a way that is similar to the symmetry of the ant without life. If we reverse the ant’s direction back and also switch his life-style from the first to the second or vice versa, then the ant and the grid will go backwards in their states.

The parameters for the Langton’s ant were chosen to make the ant’s behavior interesting. The parameters of the Game of Life were chosen to make the Game of Life’s behavior interesting. To make the ant’s life fascinating, we might want to modify the ant’s behavior or the Life’s rules. The synergy of the ant and the Life might be intriguing only if the ant changes its behavior and the Life changes its rules.

Let’s experiment and discover how we need to change the rules in order to make the ant’s life interesting.

Share:

The 2009’s Doomsday is Saturday

John H. Conway is teaching me his doomsday algorithm to calculate the day of the week for any day. The first lesson was devoted to 2009. “The 2009’s Doomsday is Saturday” is a magic phrase I need to remember.

The doomsday of a particular year is the day of the week on which the last day of February falls. February 28 of 2009 is Saturday, thus 2009’s doomsday is Saturday. For leap years it is the day of the week of February 29. We can combine the rules for leap years and non-leap years into one common rule: that the doomsday of a particular year is the day of the week of March 0.

If you know the day of the week of one of the days in 2009, you can theoretically calculate the day of the week of any other day that year. To save yourself time, you can learn by heart all the days of the year that fall on doomsday. That is actually what Conway does, and that is why he is so fast with calculations. The beauty of the algorithm is that the days of the doomsday are almost the same each year. They are the same for all months other than January and February; and in January and February you need to make a small adjustment for a leap year. That gives me hope that after I learn how to calculate days in 2009 I can easily move to any year.

To get us going we do not need to remember all the doomsday days in 2009. It is enough to remember one day for each month. We already know one for February, which works for March too. As there are 28 days in February, January 31 happens on a doomsday. Or January 32 for leap years.

Now we need to choose days for other months that are on doomsday and at the same time are easy to remember. Here is a nice set: 4/4, 6/6, 8/8. 10/10. For even months the days that are the same as the month will work. The reason it works so nicely is that two consecutive months starting with an even-numbered month, excluding February and December, have the sum of days equaling 61. Hence, those two months plus two days are 63, which is divisible by 7.

Remembering one of the doomsdays for every other month might be enough to significantly simplify calculations. But if you want a day for every month, there are additional doomsday days to remember on odd numbered months: 5/9, 9/5, 7/11 and 11/7. These days can be memorized as a mnemonic “9-5 job at 7-11,” or, if you prefer, “I do not want to have a 9-5 job at 7-11.”

If you throw in March 7, then the rule will fit into a poem John recited to me:

The last of Feb., or of Jan. will do
(Except that in leap years it’s Jan. 32).
Then for even months use the month’s own day,
And for odd ones add 4, or take it away*.

*According to length or simply remember,
you only subtract for September or November.

Let’s see how I calculate the day of the week for my friend’s birthday, July 29. The 11th of July falls on the doomsday, hence July 25 must be a doomsday. So we can see that my friend will celebrate on Wednesday this year.

You might ask why I described this trivial example in such detail. The reason is that you might be tempted to subtract 11 from 29, getting 18 and saying that you need to add four days to Saturday. In the method I described the calculation is equivalent, but as a bonus you calculate another day for the doomsday and consequently, you are getting closer to John Conway who remembers all doomsdays.

My homework is the same as your homework: practice calculating the days of the week for 2009.

Share:

Fire Hazard

Visitors to the math department of Princeton University used to stop by John Conway’s office. Even if it were closed, they could peek through the window in the door to see the many beautiful, symmetric figures hanging in his office.

The figures, which John Conway had made, were there for 20 years. Just recently John received a letter informing him that his office had been inspected by the State Fire Marshall and that “those things hanging from your ceiling are against the State’s fire code and must be taken down.” The math department was worried about a possible fine.

So John threw away the “things.” I wanted to cry as I watched these huge garbage bags being taken away. I rescued several figures, but that was all that I could fit into my car. For 20 years no one complained, but now the bureaucracy has beat out beauty and mathematics.

This picture is the last view of the “hazardous” office.

Share:

Turning Numbers Inside Out

On one of my visits to Princeton, I stopped by the math department and, as usual, asked John H. Conway what he was up to. He told me that he was turning numbers inside out. He explained that to perform this procedure on a number you need to reverse every prime factor, multiply the reversed factors back and reverse the result. For example, for 34, which is the product of 2 and 17, we need to reverse 2 and 17 (turning inside), changing them into 2 and 71, multiply back, getting 142, and reversing again (turning outside), leading to the resulting number 241.

He started with a number, turned it inside out, then turned the result inside out, and so on, thus getting an infinite sequence for any number. Every sequence he had calculated up to this point ended with a cycle.

Before I had interrupted him, he was calculating the sequence starting with 78 and it was growing. I suggested that Mathematica could do this calculation faster than John could do in his head. Although that was very rude considering his reputation for speed, John agreed, and we moved to a computer. The computer confirmed that the sequence starting with 78 was growing wildly.

While playing around with this, I became very interested in numbers that are fixed under this turning inside-out operation. First, prime numbers do not change — you just reverse them twice. Second, palindromes with palindromic primes do not change, as every reversal encounters a palindrome to apply itself to. I started to wonder if there are palindromes that are fixed under the turning inside-out procedure, but are not products of palindromic primes.

Here is where John had his revenge. He told me that he would be able to find such a number faster than I could write a program to find it. And he won! He found such a number while I was still trying to debug my program. The number he found was 1226221.

Here is how he beat me. If you have two not-too-big primes that consist of zeroes and ones and that are reversals of each other, their product will be a palindrome. And John is really fast in checking primes for primality. See his lesson in my essay Remember Your Primes.

The next day, when I stumbled on John again, he was doing something else. I asked him about the numbers and he told me that he was no longer interested. Initially he had hoped that every sequence would end in a cycle. The turning inside-out operation doesn’t produce much growth in a number. On top of that, prime numbers are stable. That means that if the turning inside-out operation was a random operation with a similar growth pattern, there would have been a very high probability of every sequence eventually hitting a prime. But the operation is not random, as it doesn’t change remainders modulo 9. In particular, sequences that start with a composite number divisible by 3 would never hit a prime. Our experiment with 78 discouraged him by showing no hope for a cycle.

I asked him, “Why not do it in binary?” He answered that he had sinned enough playing with a base 10 sequence.

A year later when I next visited Princeton and saw John again, I asked him if he had published or done something with the operation. He had not. He agreed to submit the sequence to the online database, but only if we came up with a name he liked. And we did. We now call this operation TITO (turning inside, turning outside). Please welcome TITO.

Share:

Thue-Morse Odiousness

Here is a baby puzzle. On Monday the baby said A, on Tuesday AU, on Wednesday AUUA, on Thursday AUUAUAAU. What will she say on Saturday?

You can see that this very gifted baby increases her talking capacity twice each day. The first half of what she says repeats her speech of the day before; and the second half is like the first half, but switches every A and U. If the baby continues indefinitely, her text converges to an infinite sequence that mathematicians call the Thue-Morse sequence (A010060). Of course, mathematicians use zeroes and ones instead of A and U, so the sequence looks like 0110100110010110100….

This sequence has many interesting properties. For example, if you replace every zero by 01 and every one by 10 in the Thue-Morse sequence, you will get the Thue-Morse sequence back. You can see that this is so if you code A in the baby’s speech by 01 and U by 10. Thus the Thue-Morse sequence is a fixed point under this substitution. Moreover, the only two fixed points under this substitution are the Thue-Morse sequence and its negation (A010059).

The Thue-Morse sequence possesses many other cool properties. For example, the sequence doesn’t contain substrings 000 and 111. Actually any sequence built from the doubles 01 and 10 can’t contain the triples 000 and 111 because we switch the digit after every odd-indexed term of such a sequence. A more general and less trivial statement is also true for the Thue-Morse sequence: it doesn’t contain any cubes. That is, it doesn’t contain XXX, where X is any binary string.

I stumbled upon this sequence when I was playing with evil and odious numbers invented by John H. Conway. A number is evil if the number of ones in its binary expansion is even, and odious if it’s odd. We can define a function, called the odiousness of a number, in the following way: odiousness(n) is one, if n is odious and 0 otherwise. We can apply the odiousness function to a sequence of non-negative integers term-wise. Now I can describe the Thue-Morse sequence as the odiousness of the sequence of non-negative numbers. Indeed, the odiousness of the number 2n + k is opposite of the odiousness of k, if k is less than 2n. That means if we already know the odiousness of the numbers below 2n, the next 2n terms of the odiousness sequence is the bitwise negation of the first 2n terms. So odiousness is built the same way as the Thue-Morse sequence, and you can easily check that the initial terms are the same too.

Let me consider as an example the sequence which is the odiousness of triangular numbers A153638: 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0…. What can we say about this sequence? We can say that the number of zeroes is infinite, as all the terms with indices of the form 2n-1(2n+1) are zeroes. Also, the number of ones is infinite because all the terms with indices of the form 22n-1(22n-1-1) are ones.

Obviously, we can define the evilness of a number or of a sequence with non-negative terms. Namely, the evilness of a number is 1 if the number is evil, and 0 if it is not. The evilness is the bitwise negation of the odiousness. The evilness of the sequence of non-negative integers is the negation of the Thue-Morse sequence. The odiousness sequence of any sequence of zeroes and ones is the sequence itself, and the evilness sequence is its negation.

I would like to define an inverse odiousness operation on binary sequences. Many different sequences can have the same odiousness sequence. In such a case mathematicians usually define the inverse operation as a minimal non-negative sequence whose odiousness is the given sequence. Obviously, the minimal inverse of a binary sequence is the sequence itself, and thus not very interesting. I suggest that we define the inverse as a minimal increasing sequence. In this case the odiousness inverse of the Thue-Morse sequence is the sequence of non-negative numbers.

For example, let me describe the inverse odiousness of the sequence of all ones. Naturally, all the numbers in the sequence must be odious, and by minimality property this is the sequence of odious numbers A000069: 1, 2, 4, 7, 8, 11, 13, 14, 16, 19…. Analogously, the odiousness inverse of the sequence of all zeroes is the sequence of evil numbers A001969: 0, 3, 5, 6, 9, 10, 12, 15, 17, 18, 20….

Let us find the odiousness inverse of the alternating sequence A000035: 0, 1, 0, 1, 0, 1…. This is the lexicographically smallest sequence of numbers changing putridity. By the way, “putridity” is the term suggested by John Conway to encompass odiousness and evilness the same way as parity encompasses oddness and evenness.

The odiousness inverse of the alternating sequence is the sequence A003159: 0, 1, 3, 4, 5, 7, 9, 11, 12, 13…. By my definition we can describe this sequence as indices of terms of the Thue-Morse sequence that are different from the previous term. This sequence can be described in many other ways. For example, the official definition in the OEIS is that this sequence consists of numbers whose binary expansion ends with an even number of zeroes. It is fun to prove that this is the case. It is also fun to show that this sequence can be built by adding numbers to it that are not doubles of previous terms.

Let us look at the first differences of the previous sequence. This is the sequence A026465: 1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2… — the length of n-th run of identical symbols in the Thue-Morse sequence. As we know that the Thue-Morse sequence doesn’t contain three ones or three zeroes in a row, we can state that the terms of this sequence will continue to be ones or twos.

You can define putridity sequences for any non-negative sequence. Which of them are interesting? I do not know, but I know which of them are not very interesting. For example, the putridity of pronic (oblong) numbers sequence is the same as the putridity of the triangular numbers sequence. This is because pronic numbers are twice triangular numbers and putridity is independent of factors of two. Another uninformative putridity sequence is the odiousness of the powers of two. This sequence consists only of ones.

I bet that my readers can find putridity sequences that are interesting.

Share: