The Original Taxi Cab Number in a New Light

Today I turned 25829 days old and, amongst the number's many different properties, one in particular caught my eye. The property was that it is a member of OEIS A262054: Euler pseudoprimes to base 7: composite integers such that:$$ |7^{(n-1)/2}| \equiv 1 \pmod {n}$$Now there's no sign of 1729, the original taxi cab number, but we'll get there. Firstly however, how did 1729 earn its sobriquet? Here an excerpt from Wikipedia:

The name is derived from a conversation in about 1919 involving mathematicians G. H. Hardy and Srinivasa Ramanujan. As told by Hardy: 

"I remember once going to see him [Ramanujan] when he was lying ill at Putney. I had ridden in taxi-cab No. 1729, and remarked that the number seemed to be rather a dull one, and that I hoped it was not an unfavourable omen. "No," he replied, "it is a very interesting number; it is the smallest number expressible as the sum of two [positive] cubes in two different ways."

Figure 1

The two different ways are: \(1^3 + 12^3\) and \(9^3 + 10^3\).

I won't go further into taxicab numbers here as the Wikipedia article explains things well enough. What I want to do is cast a new light on 1729, the number that Hardy originally thought was a rather dull number. The light I'm casting comes from the Euler pseudoprimes. 

I've already discussed pseudoprimes in two earlier posts: Fermat Pseudoprimes and Carmichael Numbers. I did make make passing mention of Euler pseudoprimes in the former post but didn't go into the matter further. Figure 1 shows a screenshot of part of what Wikipedia has to say about Euler pseudoprimes. 

The excerpt in Figure 1 concludes with the observation that:

The absolute Euler pseudoprimes are a subset of the absolute Fermat pseudoprimes, or Carmichael numbers, and the smallest absolute Euler pseudoprime is 1729 = 7×13×19.

It's surprising then that a mathematician of Hardy's calibre should not have recognised 1729 as having quite some claim to fame. In fact, the Online Encyclopaedia of Integer Sequences (OEIS) has 794 entries for the number so it is far from dull. Let's consider some of the other entries for 1729 in the OEIS. 

One entry is not surprising when the factorisation of 1729 is considered and the factors are arranged in descending order: 19 x 13 x 7. Let's add a 1 to give 19 x 13 x 7 x 1. The numbers 19, 13, 7 and 1 form an arithmetic sequence and this shows 1729 to be a so-called sextuple factorial. This can be written as 19!!!!!! or 19!6.

1729 counts the ways that a 2 x 2 matrix can be populated with integers from -7 to +7 in such a way that every matrix is singular (that is has a determinant of zero). It thus forms part of OEIS A209981. 

Figure 2: 35 points in a body-centered cubic lattice, 
forming two cubical layers around a central point

In the realm of figurate numbers, 1729 is a centred cube number. These are numbers of the form:\((n+1)^3+n^3\) and of course 1729 can be written as \(10^3+9^3\). Figure 2 shows the example of the centred cube number 35 and Wikipedia explains:

A centred cube number is a centred figurate number that counts the number of points in a three-dimensional pattern formed by a point surrounded by concentric cubical layers of points, with \(i^2\) points on the square faces of the \(i\)-th layer. Equivalently, it is the number of points in a body-centred cubic pattern within a cube that has \(n + 1\) points along each of its edges. 

The first few centred cube numbers are:

1, 9, 35, 91, 189, 341, 559, 855, 1241, 1729, 2331, 3059, 3925, 4941, 6119, 7471, 9009, ... (sequence A005898 in the OEIS).

1729 is also an heptagonal number, a 12-gonal or dodecagonal number, a 24-gonal or icosotetragonal number but that's probably enough for the moment.

Fermat Pseudoprimes

Today I turned 25351 days old and the number 25351 turns out to have some quite interesting properties connected with pseudoprimes. To quote from Wikipedia:

In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem. Fermat's little theorem states that if p is prime and a is coprime to p, then \(a^{p−1} − 1 \) is divisible by p. 

For an integer a > 1, if a composite integer x divides \( a^{x−1} − 1, \) then x is called a Fermat pseudoprime to base a. In other words, a composite integer is a Fermat pseudoprime to base a if it successfully passes the Fermat primality test for the base a. It follows that if x is a Fermat pseudoprime to base a, then x is coprime to a. 

The smallest base-2 Fermat pseudoprime is 341. It is not a prime, since it equals 11·31, but it satisfies Fermat's little theorem: \( 2^{340} ≡ 1 \) (mod 341) and thus passes the Fermat primality test for the base 2. Pseudoprimes to base 2 are sometimes called Poulet numbers, after the Belgian mathematician Paul Poulet, Sarrus numbers, or Fermatians (sequence A001567 in the OEIS). 

A Fermat pseudoprime is often called a pseudoprime, with the modifier Fermat being understood. An integer x that is a Fermat pseudoprime for all values of a that are coprime to x is called a Carmichael number.

Now 25351 is a member of OEIS A005936: Pseudoprimes to base 5. This is because \( 5^{25350} ≡ 1 \) (mod 25351). However, it turns out that 25351 is not simply a Fermat pseudoprime. It is also a strong pseudoprime defined by Wikipedia as:

In number theory, a probable prime is a number that passes a primality test. A strong probable prime is a number that passes a strong version of a primality test. All primes pass these tests, but a small fraction of composites also pass, making them "false primes". Unlike the Fermat pseudoprimes, for which there exist numbers that are pseudoprimes to all coprime bases (the Carmichael numbers), there are no composites that are strong pseudoprimes to all bases.

Formally, an odd composite number \(n = d \times 2^s + 1 \) with d also odd is called a strong (Fermat) pseudoprime to a base a when one of the following conditions holds:$$ a^{d} \equiv 1\! \mod n \text{ or}$$$$a^{d\cdot 2^{r}}\equiv -1 \!\mod n\quad {\mbox{ for some }}0\leq r < s $$ If a number n satisfies one of the above conditions and we don't yet know whether it is prime, it is more precise to refer to it as a strong probable prime to base a. But if we know that n is not prime, then one may use the term strong pseudoprime. The definition is trivially met if a ≡ ±1 mod n so these trivial bases are often excluded. Guy mistakenly gives a definition with only the first condition, which is not satisfied by all primes.

Now 25351 = 2 * 12675 + 1 satisfies the \(n = 12675\times 2^s + 1 \) form and 

\( 5^{12675} ≡ 1 \) (mod 25351). Hence 25351 is a strong pseudoprime. This condition may seem somewhat arbitrary but there is good explanation of why it's so at WolframAlpha.

Things get more complicated still when we learn that 25351 is also a Euler pseudoprime but I'm not going to delve any deeper at the moment. That's probably enough except that I'll finish up by saying a little about the Carmichael numbers that satisfy Fermat's little theorem to all coprime bases. The first of these numbers are 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841 and 29341. Carmichael numbers have at least three positive prime factors e.g. 561 = 3 * 11 * 17.

ADDENDUM: entered on March 11th 2020

I'm revisiting pseudoprimes because it's a topic about which I always seem to get confused. I've mentioned them previously in the following posts:

• Fermat Pseudoprimes on the 30th August 2018
• Carmichael Numbers on the 30th January 2019  
• The Original Taxi Cab Number in a New Light on the 21st December 2019

What brought to mind again was the number 25909, the number of days old that I was yesterday. One of its properties is that it's a member of OEIS A020267: strong pseudoprimes to base 41. Now it's easy enough to show that it's a pseudoprime to base 41 because$$41^{25908}-1 \equiv 0 \bmod{25909}$$However, to show 25909 is a strong pseudoprime, it needs to fulfil one of two possible conditions. Formally, an odd composite number \(n = d \times 2^s + 1\) with d also odd is called a strong (Fermat) pseudoprime to a base, when one of the following conditions holds:$$ a^{d} \equiv 1\! \mod n \text{ or}$$$$a^{d\cdot 2^{r}}\equiv -1 \!\mod n\quad {\mbox{ for some }}0\leq r \leq s $$So in the case of 25909 we have: $$25909=25908+1=2^2 \times 3 \times 17 \times 127+1=6477 \times 2^2+1$$The value of \(d\) here is 6477 so let's test it out using the first condition. We find that:$$41^{6477} \equiv 8805 \bmod{25909}$$Clearly it does not pass the first test, so let's try the second.$$41^{6477*2} \equiv -1 \bmod 25909$$It passes and so 25909 can claim to be a strong pseudoprime. Note that \( 0 \leq r < s\) and \(r\) must be 0 or 1 and the latter satifies.