Does having prime neighbors make you more composite?

Lately I’ve been thinking about the number 60.

Babylonian accountants and land surveyors did their arithmetic in base 60, presumably because sexagesimal num­bers help with wrangling fractions. When you organize things in groups of 60, you can divide them into halves, thirds, fourths, fifths, sixths, tenths, twelfths, fifteenths, twentieths, thirtieths, and sixtieths. No smaller number has as many divisors, a fact that puts 60 in an elite class of “highly composite numbers.” (The term and the definition were introduced by Srinivasan Ramanujan in 1915.)

There’s something else about 60 that I never noticed until a few weeks ago—although the Babylonians might well have known it, and Ramanujan surely did. The number 60, with its extravagant wealth of divisors, sits wedged between two other numbers that have no divisors at all except for 1 and themselves. Both 59 and 61 are primes. Such pairs of primes, separated by a single intervening integer, are known as twin primes. Other examples are (5, 7), (29, 31), and (1949, 1951). Over the years twin primes have gotten a great deal of attention from number theorists. Less has been said about the number in the middle—the interloper that keeps the twins apart. At the risk of sounding slightly twee, I’m going to call such middle numbers twin tweens, or more briefly just tweens.

Is it just a fluke that a number lying between two primes is outstandingly unprime? Is 60 unusual in this respect, or is there a pattern here, common to all twin primes and their twin tweens? One can imagine some sort of fairness principle at work: If \(n\) is flanked by divisor-poor neighbors, it must have lots of divisors to compensate, to balance things out. Perhaps every pair of twin primes forms a chicken salad sandwich, with two solid slabs of prime bread surrounding a squishy filling that gets chopped up into many small pieces.

As a quick check on this hypothesis, let’s plot the number of divisors \(d(n)\) for each integer in the range from \(n = 1\) to \(n = 75\):

Figure 1.

In Figure 1 twin primes are marked by light blue dots, and their associated tweens are dark blue. Highly composite numbers—those \(n\) that have more divisors than any smaller \(n\)—are distinguished by golden haloes. Note that 1and 2 are listed as highly composite numbers even though they are not composite at all. Go figure. The graph reveals that several twin tweens (4, 6, 12, and 60) are indeed record-setting highly composite numbers, but other tweens are not (18, 30, 42, and 72). And some highly composite numbers (24, 36, 48) do not lie between twin primes. Still, all the dark blue dots float somewhere near the upper margin of the plot, leaving the clear impression that twin tweens tend to have a lot of divisors, more than a typical integer of the same size.

The interval 1–75 is a very small sample of the natural numbers, and an unusual one, since twin primes are abundant among small integers but become quite rare farther out along the number line. For a broader view of the matter, consider the number of divisors for all positive integers up to \(n = 10^8\). The champion of divisibility among these numbers is \(n =\) 73,513,440, which has 768 divisors. It is not a twin tween.The average value of \(d(n)\) over this range is 18.5751. But if you look only at the twin tweens—there are 440,312 of them less than \(10^8\)—the average divisor count is almost three times as large: 51.5889. Numbers that have a single prime neighbor (either \(n + 1\) or \(n - 1\) but not both) also have a high average \(d(n)\): 32.1199.

Figure 2 plots \(d(n)\) over the same range, breaking up the sequence of 100 million numbers into 500 blocks of size 200,000, and taking the average value of \(d(n)\) within each block.

Figure 2.

A glance at the graph leaves no doubt that numbers living next door to primes have many more divisors, on average, than numbers without prime neighbors. It’s as if the primes were heaving all their divisors over the fence into the neighbor’s yard. Or maybe it’s the twin tweens who are the offenders here, vampirishly sucking all the divisors out of nearby primes.

Allow me to suggest a less-fanciful explanation. All primes (with one notorious exception) are odd numbers, which means that all nearest neighbors of primes (again with one exception) are even. In other words, the neighbors of primes have 2 as a divisor, which gives them an immediate head start in the race to accumulate divisors. Twin tweens have a further advantage: All of them (with one exception) are divisible by 3 as well as by 2. Why? Among any three consecutive integers, one of them must be a multiple of 3, and it can’t be either of the primes, so it must be the tween.

Being divisible by both 2 and 3, a twin tween is also divisible by 6. Any other prime factors of the tween combine with 2 and 3 to produce still more divisors. For example, a number divisible by 2, 3, and 5 is also divisible by 10, 15, and 30. Figure 3.Given this multiplicative effect, it seems possible that divisibility by 2 and 3 is all that’s needed to explain the tweens’ distinc­tive abun­dance of divisors. According to this hypothesis, the proximity of primes has nothing to do with it; tweens are divisor-rich simply because they are mul­tiples of 6. Figure 3 supports this idea. For \(n \le 10^8\), integers congruent to zero modulo 6 have more than twice as many divisors as any other residue class. (The primes are in classes 1 and 5.)

However, a closer look at Figure 3 gives reason for caution. In the graph the mean \(d(n)\) for numbers divisible by 6 is about 43, but we already know that for tweens—for the subset of numbers divisible by 6 that happen to live between twin primes—\(d(n)\) is greater than 51. That further enhancement argues that nearby primes do, after all, have some influence on divisor abundance.

Further evidence comes from another plot of \(d(n)\) for numbers with and without prime neighbors, but this time limited to integers divisible by 6. Thus all members of the sample population have the same “head start.” Figure 4 presents the results of this experiment.

Figure 4.

If prime neighbors had no effect (other than ensuring divisibility by 6), the blue, green, and red curves would all trace the same trajectory, but they do not. Although the tweens’ lead in the divisor race is narrowed somewhat, it is certainly not abolished. Numbers with two prime neighbors have about 20 percent more divisors than the overall average for numbers divisible by 6. Numbers with one prime neighbor are also slightly above average. Thus factors of 2 and 3 can’t be the whole story.

Here’s a hand-wavy attempt to explain what might be going on. In the same way that any three consecutive integers must include one that’s a multiple of 3, any five consecutive integers must include a multiple of 5. If you choose an integer \(n\) at random, you can be certain that exactly one member of the set \(\{n - 2, n - 1, n, n + 1, n + 2\}\) is divisible by 5. Since \(n\) was chosen randomly, all members of the set are equally likely to assume this role, and so you can plausibly say that 5 divides \(n\) with probability 1/5.

But suppose \(n\) is a twin tween. Then \(n - 1\) and \(n + 1\) are known to be prime, and neither of them can be a multiple of 5. You must therefore redistribute the probability over the remaining three members of the set. Now it seems that \(n\) is divisible by 5 with probability 1/3. You can make a similar argument about divisibility by 7, or 11, or any other prime. In each case the probability is enhanced by the presence of nearby primes.

The same argument works just as well if you turn it upside down. Knowing that \(n\) is even tells you that \(n - 1\) and \(n + 1\) are odd. If \(n\) is also divisible by 3, you know that \(n - 1\) and \(n + 1\) do not have 3 as a factor. Likewise with 5, 7, and so on. Thus finding an abundance of divisors in \(n\) raises the probability that \(n\)’s neighbors are prime.

Does this scheme make sense? There’s room for more than a sliver of doubt. Probability has nothing to do with the distribution of divisors among the integers. The process that determines divisibility is as simple as counting, and there’s nothing random about it. Imagine you are dealing cards to players seated at a very long table, their chairs numbered in sequence from 1 to infinity. First you deal a 1 card to every player. Then, starting with player 2, you deal a 2 card to every second player. Then a 3 card to player 3 and to every third player thereafter, and so on. When you finish (if you finish!), each player holds cards for all the divisors of his or her chair number, and no other cards.

This card-dealing routine sounds to me like a reasonable description of how integers are constructed. Adding a probabilistic element modifies the algorithm in a crucial way. As you are dealing out the divisors, every now and then a player refuses to accept a card, saying “Sorry, I’m prime; please give it to one of my neighbors.” You then select a recipient at random from the set of neighbors who lie within a suitable range.

Building a number system by randomly handing out divisors like raffle tickets might make for an amusing exercise, but it will not produce the numbers we all know and love. Primes do not wave off the dealer of divisors; on the contrary, a prime is prime because none of the cards between 1 and \(n\) land at its position. And integers divisible by 5 are not scattered along the number line according to some local probability distribution; they occur with absolute regularity at every fifth position. Introducing probability in this context seems misleading and unhelpful.

And yet… And yet…! It works.

Figure 5.

Figure 5 shows the proportion of all \(n \le 10^8\) that are divisible by 5, classified according to the number of primes adjacent to \(n\). The overall average is 1/5, as it must be. But among twin tweens, with two prime neighbors, the proportion is close to 1/3, as the probabilistic model predicts. And about 1/4 of the numbers with a single prime neighbor are multiples of 5, which again is in line with predictions of the probabilistic model. And note that values of \(n\) with no prime neighbors have a below-average fraction of multiples of 5. In one sense this fact is unsurprising and indeed inescapable: If the average is fixed and one subgroup has an excess, then the complement of that subgroup must have a deficit. Never­theless, it seems strange. How can an absence of nearby primes depress the density of multiples of 5 below the global average? After all, we know that multiples of 5 invariably come along at every fifth integer.

---

In presenting these notes on the quirks of tweens, I don’t mean to suggest there is some deep flaw or paradox in the theory of numbers. The foundations of arithmetic will not crumble because I’ve encountered more 5s than I expected in prime-rich segments of the number line. No numbers have wandered away from their proper places in the sequence of integers; we don’t have to track them down and put them back where they belong. What needs adjustment is my understanding of their distribution. In other words, the question is not so much “What’s going on?” but “What’s the right way to think about this?”

I know several wrong ways. The idea that twin primes repel divisors and tweens attract them is a just-so story, like the one about the crocodile tugging on the elephant’s nose. It might be acceptable as a metaphor, but not as a mechanism. There are no force fields acting between integers. Numbers cannot sense the properties of their neighbors. Nor do they have personalities; they are not acquisitive or abstemious, gregarious or reclusive.

The probabilistic formulation seems better than the just-so story in that it avoids explicit mention of causal links between numbers. But that idea still lurks beneath the surface. What does it mean to say “The presence of prime neighbors increases a number’s chance of being divisible by 5”? Surely not that the prime is somehow influencing the outcome of a coin flip or the spin of a roulette wheel. The statement makes sense only as an empirical, statistical observation: In a survey of many integers, more of those near primes are found to have 5 as a divisor than those far from primes. This is a true statement, but it doesn’t tell us why it’s true. (And there’s no assurance the observation holds for all numbers.)

Probabilistic reasoning is not a novelty in number theory. In 1936 Harald Cramér wrote:

With respect to the ordinary prime numbers, it is well known that, roughly speaking, we may say that the chance that a given integer \(n\) should be a prime is approximately \(1 / \log n\).

Cramér went on to build a whole probabalistic model of the primes, ignoring all questions of divisibility and simply declaring each integer to be prime or composite based on the flip of a coin (biased according to the \(1 / \log n\) probability). In some respects the model works amazingly well. As Figure 6 shows, it not only matches the overall trend in the distribution of primes, but it also gives a pretty good estimate of the prevalence of twin primes.

Figure 6.

However, much else is missing from Cramér’s random model. In particular, it totally misses the unusual properties of twin tweens. In the region of the number line shown in Figure 6, from 1 to \(10^7\), true tweens have an average of 44 divisors. The Cramér tweens are just a random sampling of ordinary integers, with about 16 divisors on average.

Fundamentally, the distribution of twin tweens is inextricably tangled up with the distribution of twin primes. You can’t have one without the other. And that’s not a helpful development, because the distribution of primes (twin and otherwise) is one of the deepest enigmas in modern mathematics.

---

Throughout these musings I have characterized the distinctive properties of tweens by counting their divisors. There are other ways of approaching the problem that yield similar results. For example, you can calculate the sum of the divisors, \(\sigma(n)\) rather than the count \(d(n)\), a technique that leads to the classical notions of abundant, perfect, and deficient numbers. A number \(n\) is abundant if \(\sigma(n) > 2n\), perfect if \(\sigma(n) = 2n\) and deficient if \(\sigma(n) \lt 2n\). When I wrote a program to sort tweens into these three categories, I was surprised to discover that apart from 4 and 6, every twin tween is an abundant number. Such a definitive result seemed remarkable and important. But then I learned that every number divisible by 6, other than 6 itself, is abundant.

Another approach is to count the prime factors of \(n\), rather than the divisors. These two quantities are highly correlated, although the number of divisors is not simply a function of the number of factors; it also depends on the diversity of the factors.

Figure 7.

As Figure 7 shows, counting primes tells a story that’s much the same as counting divisors. A typical integer in the range up to \(10^8\) has about four factors, whereas a typical tween in the same range has more than six.

We could also look at the size of \(n\)’s largest prime factor, \(f_{\max}(n)\), which is connected to the concept of a smooth number. A number is smooth if all of its prime factors are smaller than some stated bound, which might be a fixed constant or a function of \(n\), such as \(\sqrt n\). One measure of smoothness is \(\log n\, / \log f_{\max}(n)\). Computations show that by this definition tweens are smoother than average: The ratio of logs is about 2.0 for the tweens and about 1.7 for all numbers.

One more miscellaneous fact: No tween except 4 is a perfect square. Proof: Suppose \(n = m^2\) is a tween. Then \(n - 1 = m^2 - 1\), which has the factors \(m - 1\) and \(m + 1\), and so it cannot be prime. An extension of this argument rules out cubes and all higher perfect powers as twin tweens.

---

When I first began to ponder the tweens, I went looking to see what other people might have said on the subject. I didn’t find much. Although the literature on twin primes is immense, it focuses on the primes themselves, and especially on the question of whether there are infinitely many twins—a conjecture that’s been pending for 170 years. The numbers sandwiched between the primes are seldom mentioned.

The many varieties of highly composite numbers also have an enthusiastic fan club, but I have found little discussion of their frequent occurrence as neighbors of primes.

Could it be that I’m the first person ever to notice the curious properties of twin tweens? No. I am past the age of entertaining such droll thoughts, even transiently. If I have not found any references, it’s doubtless because I’m not looking in the right places. (Pointers welcome.)

I did eventually find a handful of interesting articles and letters. The key to tracking them down, unsurprisingly, was the Online Encyclopedia of Integer Sequences, which more and more seems to function as the Master Index to Mathematics. I had turned there first, but the entry on the tween sequence, titled “average of twin prime pairs,” has only one reference, and it was not exactly a gold mine of enlightenment. It took me to a 1967 volume of Eureka, the journal of the Cambridge Archimedians. All I found there (on page 16) was a very brief problem, asking for the continuation of the sequence 4, 6, 12, 18, 30, 42,…

There the matter rested for a few weeks, but eventually I came back to the OEIS to follow cross-links to some related sequences. Under “highly composite numbers” I found a reference to “Prime Numbers Generated From Highly Composite Numbers,” by Benny Lim (Parabola, 2018). Lim looked at the neighbors of the first 1,000 highly composite numbers. At the upper end of this range, the numbers are very large \((10^{76})\) and primes are very rare—but they are not so rare among the nearest neighbors of highly composite numbers, Lim found.

Another cross reference took me off to sequence A002822, labeled “Numbers \(m\) such that \(6m-1\), \(6m+1\) are twin primes.” In other words, this is the set of numbers that, when multiplied by 6, yield the twin tweens. The first few terms are: 1, 2, 3, 5, 7, 10, 12, 17, 18, 23, 25, 30, 32, 33, 38. The OEIS entry includes a link to a 2011 paper by Francesca Balestrieri, which introduces an intriguing idea I have not yet fully absorbed. Balestrieri shows that \(6m + 1\) is composite if \(m\) can be expressed as \(6xy + x - y\) for some integers \(x\) and \(y\), and otherwise is prime. There’s a similar but slightly more complicated rule for \(6m - 1\). She then proceeds to prove the following theorem:

The Twin Prime Conjecture is true if, and only if, there exist infinitely many \(m \in N\) such that \(m \ne 6xy + x - y\) and \(m \ne 6xy + x + y\) and \(m \ne 6xy - x - y\), for all \(x, y \in N\).

Other citations took me to three papers by Antonie Dinculescu, dated 2012 to 2018, which explore related themes. But the most impressive documents were two letters written to Neil J. A. Sloane, the founder and prime mover of the OEIS. In 1984 the redoubtable Solomon W. Golomb wrote to point out several publications from the 1950s and 60s that mention the connection between \(6xy \pm x \pm y\) and twin primes. The earliest of these appearances was a problem in the American Mathematical Monthly, proposed and solved by Golomb himself. He was 17 when he made the discovery, and this was his first mathematical publication. To support his claim of priority, he offered a $100 reward to anyone who could find an earlier reference.

The second letter, from Matthew A. Myers of Spruce Pine, North Carolina, supplies two such prior references. One is a well-known history of number theory by L. E. Dickson, published in 1919. The other is an “Essai sur les nombres premiers” by Wolfgang Ludwig Krafft, a colleague of Euler’s at the St. Petersburg Academy of Sciences. The essay was read to the academy in 1798 and published in Volume 12 of the Nova Acta Academiae Scientiarum Imperialis Petropolitanae. It deals at length with the \(6xy \pm x \pm y\) matter. This was 50 years before the concept of twin primes, and their conjectured infinite supply, was introduced by Alphonse de Polignac.

Myers reported these archeological findings in 2018. Sadly, Golomb had died two years earlier.