Tanya Khovanova's Math Blog

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.

Let me remind you of a very interesting problem from my posting Oleg Kryzhanovsky’s Problems.

You have 6 coins weighing 1, 2, 3, 4, 5 and 6 grams that look the same, except for their labels. The number (1, 2, 3, 4, 5, 6) on the top of each coin should correspond to its weight. How can you determine whether all the numbers are correct, using the balance scale only twice?

I do not want you to find the weight of each coin; I just want you to say yes if the labels are correct, or no if they are not.

I have given this problem to a lot of people, and not one of them solved it. Some of my students mistakenly thought that they succeeded. For example, they would start by putting the coins labeled 1 and 2 on the left cup of the scale and 3 on the right cup. If these coins balanced, the students assumed that the coins on the left weighed 1 and 2 grams and that the coin on the right weighed 3 grams. But they’d get the same result if they had 1 and 4 on the left, for example, and 5 on the right. I am surprised that no one has solved it yet, as I thought that this problem could be offered to middle-schoolers, since it does not actually require advanced mathematical skills.

If you want to try to solve this problem, pause here, as later in this essay I will be providing a number of hints on how to do it. The problem is fun to solve, so continue reading only if you are sure you’re ready to miss out on the pleasure of solving it.

I propose the following sequence a(n). Suppose we have a set of n coins of different weights weighing exactly an integer number of grams from 1 to n. The coins are labeled from 1 to n. The sequence a(n) is the minimum number of weighings we need on a balance scale to confirm that the labels are correct. The original Oleg Kryzhanovsky’s problem asks to prove that a(6) = 2. It is easy to see that a(1) = 0, a(2) = 1, a(3) = 2. You will enjoy proving that a(4) = 2 and a(5) = 2.

In general, we can prove that a(n) ≤ n-1. For any k < n, the k-th weighing compares coins labeled k and k+1. If we get the expected result every time, then we can confirm that the weights are increasing according to the labels.

On the other hand, we can prove that a(n) ≥ log₃(n). Indeed, suppose we conducted several weighings and confirmed that the labels are correct. To every coin we can assign a sequence of three letters L, R, N, corresponding to where the coin was placed during each weighing — left cup, right cup or no cup. If two coins are assigned the same letters for every weighing, then we can’t confirm that the labels on these two coins are accurate. Indeed, if we switch the labels on these two coins, the results of all the weighings will be the same.

My son, Alexey Radul, sent me the proof that a(10) = a(11) = 3. As 3 is the lower bound, we just need to describe the weighings that will work.

Here is the procedure for 10 coins. For the first weighing we put coins labeled 1, 2, 3, and 4 on one side of the scale and the coin labeled 10 on the other. After this weighing, we can divide the coins into three groups (1,2,3,4), (5,6,7,8,9) and (10). We know to which group each coin belongs, but we do not know which coin in the group is which. The second weighing is 1, 5 and 10 on the left, and 8 and 9 on the right. The left side should weigh less than the right side. The only possibility for the left side to weigh less is when the smallest weighing coins from the first and the second group and 10 are on the left, and the two largest weighing coins from the first two groups are on the right. After the second weighing we can divide all coins into groups we know they belong to: (1), (2,3,4), (5), (6,7), (8,9) and (10). The last weighing contains the lowest weighing coin from each non-single-coin group on the left and the largest weighing coin on the right, plus, in order to balance them, the coins whose weights we know. The last weighing is 2+6+8+5 = 4+7+9+1.

Here is Alexey’s solution, without explanation, for 11 coins: 1+2+3+4 < 11; 1+2+5+11 = 9+10; 6+9+1+3 = 8 +4+2+5.

Let me denote the n-th triangular number as T_n. Then a(T_n) ≤ a(n) + T_n – n – 1. Proof. The first weighing is 1+2+3 … +n = T_n. After that we can divide coins into groups, where we know that the labels stay within the group: (1,2,…,n), (n+1,n+2,…,T_n-1), (T_n). We can check the first group in a(n) weighings, the second group in T_n – n – 2 weighings, and we already used one. QED.

Similarly, a(T_n+1) ≤ a(n) + T_n – n.

For non-triangular numbers there are sometimes weighings that divide coins into three groups such that the labels can only be permuted within the same group. For example, with 13 coins, the first weighing could be 1+2+3+4+5+6+7+8 = 11+12+13. After that weighing we can divide all coins into three groups (1,2,3,4,5,6,7,8), (9,10), (11,12,13).

In all the examples so far, each weighing divided all the coins into groups. But this is not necessary. For example, here is Alexey’s solution for 9 coins. The first weighing is 1+2+3+4+5 < 7+9. When we have five coins on the left weighing less than two coins on the right, we have several different possibilities of which coins are where. Other than the case above, we can have 1+2+3+4+6 < 8+9 or 1+2+3+4+5 < 8+9. But let’s look at the next weighing that Alexey suggests: 1+2+4+7 = 6+8. Or, three coins from the previous weighing’s left cup, plus one coin from the previous weighing’s right cup equals the sum of the two coins that were left over. This can only be true if the coins in the first weighing were indeed 1+2+3+4+5 on the left and 7+9 on the right. After those two weighings everything divides into groups (1,2,4), (3,5), (6,8), (7) and (9). The last weighing 1+7+9 = 4+5+8, resolves the rest.

To check 7 or 8 coins in three weighings is simpler than the cases for 9, 10, and 11 coins, so I leave it as an exercise. As of today I do not know if it is possible to check 7, 8 or 9 coins in two weighings. Consider this a starred exercise.

I invite you to play with this amusing sequence and calculate some bounds. Also, let me know if you can prove or disprove that this sequence is non-decreasing.

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.

My son Sergei brought back the Flip-Flop game from Canada/USA Mathcamp, and now I teach it to my students. This game trains students in the multiplication table for seven and eight. These are the most difficult digits in multiplication. This game is appropriate for small kids who just learned the multiplication table, but it is also fun for older kids and adults.

This is a turn-based game. In its primitive simplification kids stand in a circle and count in turn. But it is more interesting than that. Here’s what to say and do on your turn, and how the game determines who is next.

First I need to tell you what to say. On your turn, say the next number by default. However, there are exceptions when you have to say something else. And this something else consists of flips and/or flops.

So what are flips? Flip is related to seven. If a number is divisible by seven or has a digit seven, instead of saying this number, we have to say “flip” with multiplicities. For example, instead of 17 we say “flip” because it contains one digit seven. Instead of 14 we say “flip”, because it is divisible by seven once. Instead of 7 we say “flip-flip”, as it is both divisible by seven and has a digit seven. Instead of 49, we say “flip-flip” as 49 is divisible by the square of seven. Instead of 77 we say “flip-flip-flip” as it has two digits seven and is divisible by seven once.

Flop relates to eight the same way as flip relates to seven. Thus, instead of 16 we say “flop” as it is divisible by eight; instead of 18 we say “flop” as it contains the digit eight; and for 48 we say “flop-flop” as it is both divisible by eight and contains the digit eight.

A number can relate to seven and eight at the same time. For example 28 is divisible by seven and contains the digit eight. Instead of 28 we say “flip-flop”. The general rule is that all flips are pronounced before all flops. For example, instead of 788 we will say “flip-flop-flop-flop” as it is divisible by eight and contains the digit seven once and the digit eight twice.

The sequence of natural numbers in the flip-flop version starts as the following: 1, 2, 3, 4, 5, 6, flip-flip, flop-flop, 9, 10, 11, 12, 13, flip, 15, flop, flip, flop, 19, 20, flip, 22, 23, flop, 25, 26, flip, flip-flop, 29, 30, 31, flop, 33, 34, flip, 36, flip, flop, 39, flop, 41, flip, 43, 44, 45, 46, flip, flop-flop, flip-flip, 50, 51, 52, 53, 54, 55, flip-flop, flip, flop, 59, 60, 61, 62, flip, flop-flop, 65, 66, flip, flop, 69, flip-flip, flip, flip-flop, flip, flip, flip, flip, flip-flip-flip, flip-flop, flip, flop-flop, flop, flop, flop, flip-flop, flop, flop, flip-flop, flop-flop-flop, flop, 90, flip, 92, 93, 94, 95, flop, flip, flopflip-flip-flop, 99, 100.

So how does the turn change? Everyone stands in a circle and says their number the way explained above. We start clockwise and move to the next number. For every flip we reverse the direction and for every flop we skip a person. That means that if we have two flips, we don’t change the direction, while for two flops we skip two people. If we have flips and flops together, for example 28 corresponds to “flip-flop”, then first we change the direction and then we skip a person.

On top of that, there is an extra rule for what you do on your turn. If you say something other than a default number, you switch your position from standing to sitting and vice versa. Sometimes I skip this extra feature — not because I am too lazy to exercise, but because I usually conduct this game in a classroom, where all the desks prevent us from fully enjoying such physical activity.

There are two ways to play this game: as a competition or as practice. When we are competing, a person who makes a mistake drops out. If we’re just practicing, no one drops out. Sometimes I am particularly generous and allow my kids one mistake before making them drop out after the second mistake. So far we have played up to 100. I am curious to see if we can ever reach 700 and how long we will be able to continue the game after that.

I have forgotten all the problems from the math Olympiads I participated in, except for one. That problem cost me one point, and as result I didn’t get a perfect score. Here is Problem Number 4 from the 1976 IMO:

Determine the greatest number that is the product of some positive integers, and the sum of these integers is 1976.

The solution goes like this. Consider a partition of 1976. If there is an integer x in the partition greater than 5, then replacing it with two integers x-2 and 2 gives a bigger product. Replacing 4 in the partition by 2 and 2 doesn’t change the product. On the other hand, if there is 1 in the partition, it is profitable to attach it to any other number: to replace 1 and x by x+1.

That means the maximum-product partition of a number greater than one has to consist only of twos and threes. If we have three twos in the partition, we can replace them by two threes, thus increasing the product. That means that our partition should consist of twos and threes, and the number of twos shouldn’t be greater than three.

I lost my point when I made an elementary arithmetic mistake while calculating the remainder of 1976 modulo 3.

Let’s generalize this problem for any number n. If we define the maximum product of partitions a(n) as a function of the number n, we get the sequence A000792 in the Encyclopedia of Integer Sequences. This sequence has other interesting definitions, which appear if we add some structure to partitions of n.

For example, we can suppose that our n is not just a number, but it also represents n objects that are being permuted by the symmetric group S_n. In this case, we can associate some Abelian subgroups of the symmetric group with every partition. Namely, we can divide the set of n elements into disjoint subsets of sizes corresponding to our partition and cycle the elements in every subset. The product of these cycles is an Abelian subgroup, the order of which doesn’t depend on how exactly we partition or how we cycle. This order is the product of the partition numbers. It appears that we can get all maximal Abelian subgroups of the symmetric group in this manner. Thus the sequence a(n) is the maximum size of the maximal Abelian subgroup in a symmetric group S_n.

We can do something else with our n objects. Suppose they are represented by vertices of a graph. We take any partition of n and divide our graph into groups of vertices according to this partition. Next we connect vertices of the graph that belong to different groups. If we take a vertex from every group, then the corresponding subgraph is a clique. We can see that it is a maximal clique as two vertices from the same group are never connected and we can’t add any more vertices. The number of different cliques of this size is the product of the number of elements in every group. We can prove that a(n) is the maximum possible number of maximal cliques in a graph with n vertices.

Even though I can’t return to 1976 to correct my stupid mistake, I love this problem and the corresponding sequence.

This piece of graph theory was inspired by a logic puzzle The Sexaholics of Truthteller Planet at the 2009 MIT mystery hunt.

Suppose we have a graph where nodes are people and edges connect two people who ever had sex with each other. Given this graph, I am wondering what we can derive about the gender and sexual orientation of the people involved. To do this I need to make some assumptions.

As these are people from another planet, Truthteller, I can choose any assumptions I please, so let us assume that people are of two genders and two types of sexual orientation. The first type of sexual orientation is strictly straight — people of this type only have sex with strictly straight people of the opposite gender. The second type of sexual orientation is strictly homosexual — people of this type only have sex with strictly homosexual people of the same gender. Whoops! I almost forgot: as I assume simplicity, no threesomes happen on that planet.

My question is: Looking at the sex graph can we say anything about sexual orientation? Given any graph, all the vertices can represent homosexual people of the same gender. Is it possible to say, on the other hand, that a vertex of this graph can correspond to a straight person? Let us consider a connected graph representing sex between strictly straight people. This graph has to be bipartite. Hence, given a graph, the maximum number of vertices that correspond to straight people is the total number of vertices in all bipartite connected components.

Similarly, all vertices in a non-bipartite component of a graph are guaranteed to correspond to homosexuals.

Here I would like to name these graphs. If a graph doesn’t have a bipartite connected component I will call this graph an all-homosexual graph. The sequence for which the n-th term is the number of all-homosexual graphs with n vertices for n > 0 starts as 0, 0, 1, 3, 16, 96, 812… and is sequence A157016 in the Online Encyclopedia of Integer Sequences. The smallest all-homosexual graph is a complete graph with 3 vertices.

I would like to name not all-homosexual graphs as someone-can-be-straight graphs. The corresponding sequence is A157015.

Thank you to the people who helped me to calculate and clean these two sequences. I received more help with these two sequences than all the sequences I’ve tried to submit to the Encyclopedia. And it is definitely not because they are about sex, because I purposefully didn’t tell them that I was going to relate these sequences to sex. Thanks to Max Alekseyev, Edwin Clark, Brendan McKay and Wouter Meeussen.

I was interested for some time in the divisibility of odd Fibonacci numbers. Fibonacci numbers are closely related to Lucas numbers. Lucas numbers L_n follow the same recurrence as Fibonacci numbers: L_n = L_n-1 + L_n-2, but with a different start: L₀ = 2, L₁ = 1. Obviously, every third Fibonacci and every third Lucas number is even.

Primes that divide odd Lucas numbers divide odd Fibonacci numbers. Let us prove this. Suppose a prime p divides an odd Lucas number L_k, then we can use the famous identity F_2k = F_kL_k. We see that p divides F_2k. The fact that L_k is odd means that k is not divisible by 3 and so is 2k. Thus F_2k is an odd Fibonacci that is divisible by p.

We see that primes that divide odd Lucas numbers are a subset of primes dividing odd Fibonacci numbers. It is easy to see that it is a proper subset. The smallest prime that divides an odd Fibonacci and doesn’t divide any Lucas number is 5.

The next natural question to ask: is there a prime number that divides an odd Fibonacci, doesn’t divide an odd Lucas number, but divides an even Lucas number? Below I show that such a prime doesn’t exist. In other words, that the set of prime factors of odd Lucas numbers is the intersection of the set of prime factors of odd Fibonacci numbers with the set of prime factors of all Lucas numbers.

Let us consider a Fibonacci-like sequence a_n in a sense that a_n = a_n-1 + a_n-2 for n > 1. Let me denote by b_n, the sequence that is a_n modulo a prime number p. The sequence b_n has to be periodic. It could happen that b_n is never 0. For example, Lucas numbers are never divisible by 5. Suppose the sequence b_n contains a zero. Let us denote r(p) the difference between the indices of two neighboring zeroes in b_n. We can prove that r(p) is well-defined, meaning that is doesn’t depend on where you choose your neighboring zeroes. Moreover r(p) doesn’t depend on the sequence you start with (see 9 Divides no Odd Fibonacci for the proof). The number r(p) is called the rank of apparition of the prime p.

As the Fibonacci sequence starts with a zero, then the terms divisible by a prime p are exactly the terms with indices that are multiples of the corresponding rank of apparition. The Lucas sequence doesn’t start with a zero, but we know that L_-n = (-1)ⁿL_n. That means, if a Lucas number is ever divisible by a prime p, then the smallest positive index for such a number has to be r(p)/2. Also, the indices of the Lucas numbers divisible by p will be odd multiples of r(p)/2.

We know that the indices of even Fibonacci or Lucas numbers are multiples of 3. Hence, a prime number p that divides an odd Fibonacci number must have a rank of apparition that is not divisible by 3, That means that if p ever divides a Lucas number, then it divides a Lucas number with an index of r(p)/2, which is not divisible by 3, meaning that p divides an odd Lucas number. QED.

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 2ⁿ + k is opposite of the odiousness of k, if k is less than 2ⁿ. That means if we already know the odiousness of the numbers below 2ⁿ, the next 2ⁿ terms of the odiousness sequence is the bitwise negation of the first 2ⁿ 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 2^n-1(2ⁿ+1) are zeroes. Also, the number of ones is infinite because all the terms with indices of the form 2^2n-1(2^2n-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.

My knowledge about vampires comes mostly from the two TV series Buffy The Vampire Slayer and Angel. If you saw these series you would know that vampires can’t stand the sun. Therefore, they can’t get any tan at all and should be very pale. Angel doesn’t look pale but I never saw him going to a tanning spa. Nor did I ever see him taking vitamin D, as he should if he’s avoiding the sun.

But this is not why I’m confused about vampires. My biggest concerns are about vampires that are numbers.

Vampire numbers were invented by Clifford A. Pickover, who said:

If we are to believe best-selling novelist Anne Rice, vampires resemble humans in many respects, but live secret lives hidden among the rest of us mortals. Consider a numerical metaphor for vampires. I call numbers like 2187 vampire numbers because they’re formed when two progenitor numbers 27 and 81 are multiplied together (27 * 81 = 2187). Note that the vampire, 2187, contains the same digits as both parents, except that these digits are subtly hidden, scrambled in some fashion.

Some people call the parents of a vampire number fangs. Why would anyone call their parents fangs? I guess some parents are good at blood sucking and because they have all the power, they make the lives of their children a misery. So which name shall we use: parents or fangs?

Why should parents have the same number of digits? Maybe it’s a gesture of gender equality. But there is no mathematical reason to be politically correct, that is, for parents to have the same number of digits. For example, 126 is 61 times 2 and thus is the product of two numbers made from its digits. Pickover calls 126 a pseudovampire. So a pseudovampire with asymmetrical fangs, is a disfigured vampire, one whose fangs have a different number of digits. Have you ever seen fangs with digits?

In the first book where vampires appeared Keys to Infinity the vampire numbers are called true vampire numbers as opposed to pseudovampire numbers.

We can add a zero at the end of a pseudovampire to get another pseudovampire, a trivial if obvious observation. To keep the parents equal, we can add two zeroes at the end of a vampire to get another vampire. Adding zeroes is not a very intellectual operation, but a vampire that can’t be created by adding zeroes to another vampire is more basic and, thus, more interesting. In the book Wonders of Numbers: Adventures in Mathematics, Mind, and Meaning a vampire where one of the multiplicands doesn’t have trailing zeroes is called a true vampire, as opposed to just a vampire. Thus, the trueness of vampires changes from book to book, adding some more confusion. It looks like the second definition of a true vampire is more widely adopted, so I will stick to it.

By analogy, we should call pseudovampires that do not end in zeroes, true pseudovampires. It’s interesting to note that by adding zeroes we can get a true vampire from any pseudovampire that is not a vampire. You see how easy it is to build equality? Just add zeroes.

A true vampire might not be true as a pseudovampire. For example, a vampire number 1260 = 20 * 61 is generated by adding a zero to a pseudovampire 126 = 2 * 61. In this case, the pseudovampire is truer than the vampire. Why does something more basic get a prefix “pseudo”?

Here’s another question. Why do vampires have to have two fangs? Can a vampire have three fangs? For example, 11439 = 9 * 31 * 41. This generalization of vampires should be called mutant vampires. Or multi-gender vampires.

To create more confusion, a mutant vampire can, at the same time, be a simple vampire: 1395 = 31 * 9 * 5 = 15 * 93.

Of course, nothing prevents a mutant vampire from being politically correct, that is, to have multiple and equal parents with the same number of digits, as in 197925 = 29 * 75 * 91.

People continue creating a mess with vampires. For example, a definition of a prime vampire number is floating around the Internet. When you look at this name, your first reaction is that a prime vampire is a prime number. But a vampire is never prime as it is always a product of numbers. By definition a prime vampire is a vampire with prime multiplicands, for example 124483 = 281 * 443. So “prime vampire number” is a very bad name. We should call these vampires prime-fanged vampires — this would be much more straightforward.

To eliminate some of this confusion, we mathematicians should go back and rename vampires consistently. But in the meantime, check out the illustration of vampire numbers shown above that I found at flickr.com with this description:

Like the count von Count in Sesame Street, there is a tradition that vampires suffer terribly from arithromania: the compulsion to count things. To keep vampires from wreaking murderous havoc at night, poppy seeds were strewn about their resting places. On waking, the vampire would be compelled to count the seeds. It would take him all night, and keep him from mischief.

My knowledge about vampires comes mostly from the two TV series Buffy The Vampire Slayer and Angel . If you saw these series you would know that vampires can’t stand the sun. Therefore, they can’t get any tan at all and should be very pale. Angel doesn’t look pale but I never saw him going to a tanning spa. Nor did I ever see him taking vitamin D, as he should if he’s avoiding the sun.

But this is not why I’m confused about vampires. My biggest concerns are about vampires that are numbers.

Vampire numbers were invented by Clifford A. Pickover, who said:

If we are to believe best-selling novelist Anne Rice , vampires resemble humans in many respects, but live secret lives hidden among the rest of us mortals. Consider a numerical metaphor for vampires. I call numbers like 2187 vampire numbers because they’re formed when two progenitor numbers 27 and 81 are multiplied together (27 * 81 = 2187). Note that the vampire, 2187, contains the same digits as both parents, except that these digits are subtly hidden, scrambled in some fashion.

Some people call the parents of a vampire number fangs. Why would anyone call their parents fangs? I guess some parents are good at blood sucking and because they have all the power, they make the lives of their children a misery. So which name shall we use: parents or fangs?

Why should parents have the same number of digits? Maybe it’s a gesture of gender equality. But there is no mathematical reason to be politically correct, that is, for parents to have the same number of digits. For example, 126 is 61 times 2 and thus is the product of two numbers made from its digits. Pickover calls 126 a pseudovampire. So a pseudovampire with asymmetrical fangs, is a disfigured vampire, one whose fangs have a different number of digits. Have you ever seen fangs with digits?

In the first book where vampires appeared Keys to Infinity the vampire numbers are called true vampire numbers as opposed to pseudovampire numbers.

We can add a zero at the end of a pseudovampire to get another pseudovampire, a trivial if obvious observation. To keep the parents equal, we can add two zeroes at the end of a vampire to get another vampire. Adding zeroes is not a very intellectual operation, but a vampire that can’t be created by adding zeroes to another vampire is more basic and, thus, more interesting. In the book Wonders of Numbers: Adventures in Mathematics, Mind, and Meaning a vampire where one of the multiplicands doesn’t have trailing zeroes is called a true vampire, as opposed to just a vampire. Thus, the trueness of vampires changes from book to book, adding some more confusion. It looks like the second definition of a true vampire is more widely adopted, so I will stick to it.

By analogy, we should call pseudovampires that do not end in zeroes, true pseudovampires. It’s interesting to note that by adding zeroes we can get a true vampire from any pseudovampire that is not a vampire. You see how easy it is to build equality? Just add zeroes.

A true vampire might not be true as a pseudovampire. For example, a vampire number 1260 = 20 * 61 is generated by adding a zero to a pseudovampire 126 = 2 * 61. In this case, the pseudovampire is truer than the vampire. Why does something more basic get a prefix “pseudo”?

Here’s another question. Why do vampires have to have two fangs? Can a vampire have three fangs? For example, 11439 = 9 * 31 * 41. This generalization of vampires should be called mutant vampires. Or multi-gender vampires.

To create more confusion, a mutant vampire can, at the same time, be a simple vampire: 1395 = 31 * 9 * 5 = 15 * 93.

Of course, nothing prevents a mutant vampire from being politically correct, that is, to have multiple and equal parents with the same number of digits, as in 197925 = 29 * 75 * 91.

People continue creating a mess with vampires. For example, a definition of a prime vampire number is floating around the Internet. When you look at this name, your first reaction is that a prime vampire is a prime number. But a vampire is never prime as it is always a product of numbers. By definition a prime vampire is a vampire with prime multiplicands, for example 124483 = 281 * 443. So “prime vampire number” is a very bad name. We should call these vampires prime-fanged vampires — this would be much more straightforward.

To eliminate some of this confusion, we mathematicians should go back and rename vampires consistently. But in the meantime, check out the illustration of vampire numbers shown above that I found at flickr.com with this description:

Like the count von Count in Sesame Street, there is a tradition that vampires suffer terribly from arithromania: the compulsion to count things. To keep vampires from wreaking murderous havoc at night, poppy seeds were strewn about their resting places. On waking, the vampire would be compelled to count the seeds. It would take him all night, and keep him from mischief.

When I came to the US, I heard about Mensa — the high IQ society. My IQ had never been tested, so I was curious. I was told that there was a special IQ test for non-English speakers and that my fresh immigrant status and lack of English knowledge was not a problem. I signed up.

There were two tests. One test had many rows of small pictures, and I had to choose the odd one out in each row. That was awful. The test was English-free, but it wasn’t culture-free. I couldn’t identify some of the pictures at all. We didn’t have such things in Russia. I remember staring at a row of tools that could as easily have been from a kitchen utensil drawer as from a garage tool box. I didn’t have a clue what they were.

But the biggest problem was that the idea of crossing the odd object out seems very strange to me in general. What is the odd object out in this list?

Cow, hen, pig, sheep.

The standard answer is supposed to be hen, as it is the only bird. But that is not the only possible correct answer. For example, pig is the only one whose meat is not kosher. And, look, sheep has five letters while the rest have three.

Thus creative people get fewer points. That means, IQ tests actually measure how standard and narrow your mind is.

The second test asked me to continue patterns. Each page had a three-by-three square of geometric objects. The bottom right corner square, however, was empty. I had to decide how to continue the pattern already established by the other eight squares by choosing from a set of objects they provided.

This test is similar to continuing a sequence. How would you continue the sequence 1,2,3,4,5,6,7,8,9? The online database of integer sequences has 1479 different sequences containing this pattern. The next number might be:

• 10, if this is the sequence of natural numbers;
• 1, if this is the sequence of the digital sums of natural numbers;
• 11, if this the sequence of palindromes;
• 0, if this is the sequence of digital products of natural numbers;
• 13, if this is the sequence of numbers such that 2 to their powers doesn’t contain 0;
• 153, if this is the sequence of numbers that are sums of fixed powers of their digits;
• 22, if this is the sequence of numbers for which the sum of digits equals the product of digits; or
• any number you want.

Usually when you are asked to continue a pattern the assumption is that you are supposed to choose the simplest way. But sometimes it is difficult to decide what the testers think the simplest way is. Can you replace the question mark with a number in the following sequence: 31, ?, 31, 30, 31, 30, 31, … You might say that the answer is 30 as the numbers alternate; or, you might say that the answer is 28 as these are the days of the month.

Towards the end of my IQ test, the patterns were becoming more and more complicated. I could have supplied several ways to continue the pattern, but my problem was that I wasn’t sure which one was considered the simplest.

When I received my results, I barely made it to Mensa. I am glad that I am a member of the society of people who value their brains. But it bugs me that I might not have been creative enough to fail their test.