Sharps and Flats

After I wrote the previous essay, a friend of mine figured out the right way to think about intermediates. I'd been complaining to him that I couldn't get a handle on them … I could think about 7² by associating it with 7, but I couldn't find a good way to think about the intermediate between 7² and 8². I couldn't associate it with 7½, because my concept of 7½ isn't strong enough to attach anything to, and I didn't want to arbitrarily associate it with either 7 or 8. So … my friend's bright idea was to make an analogy to music, and let the intermediate be both 7^♯ (7 sharp) and 8^♭ (8 flat). The more I thought about the idea, the more I liked it, so now here it is for your enjoyment. Here are some official-looking definitions.

n♯	= n2 + n = n(n+1)
n♭	= n2 − n = n(n−1)

And, here's a table of the first few sharps. I wanted to write them down just to familiarize myself with them, then I thought I might as well let you see them too.

1	2	11	132
2	6	12	156
3	12	13	182
4	20	14	210
5	30	15	240
6	42	16	272
7	56	17	306
8	72	18	342
9	90	19	380
10	110	20	420

It's funny to me how unfamiliar the numbers are, given how simple the formula is. There are a few that I recognize for unrelated reasons … 342 is the number of encoded bytes in an Apple II disk sector (basically 256 × 8/6); 132 is (I think) the number of columns an Epson MX-80 could print in condensed mode; and of course 42 is the answer. But, I could swear I've never seen the number 182 in a mathematical context before.

Finally, here's a funny little result I discovered … it's hardly even worth mentioning, but I like how it ties together three different famous things. Looking at the table, it struck me that most of the sharps are highly composite. Of course, any sharp (except 1^♯) has at least two distinct prime factors, since n^♯ = n(n+1), and the adjacent numbers n and n+1 can't share factors. However, we can do better than that … it turns out that almost all sharps have at least three distinct prime factors. Here's a quick proof.

Look at the numbers n and n+1 again (for n ≥ 2). One of them must be divisible by 2, and that gives us one distinct prime factor. Now, remove all factors of 2 from that number. If there's anything left, then that and the factor(s) of the other number give us at least two more distinct factors, and we're done. So, for any counterexample, one of the numbers must be a power of 2 (or must be 2 itself).

In that case, what about the other number? Well, if it has two distinct factors, then once again we're done; so the other number must be a prime, or a power of a prime. But, in the second case, Catalan's conjecture comes into play, and tells us that the only adjacent powers are the numbers 8 and 9! So, that gives us one counterexample, and tells us that the other number must be a prime.

In other words, we're looking for primes of the form 2^k±1. But, primes of the form 2^k−1 are Mersenne primes … you know, those rare numbers that people use supercomputers and distributed computing to search for. At present, only 42 are known. And, primes of the form 2^k+1 are Fermat primes … and as far as anyone knows, there are only five of those: k = 2^r for 0 ≤ r ≤ 4. (Actually k = 0 works too, but it's no use here because it produces an even number.)

So … we have one special case (n = 1), one Catalan solution, 42 Mersenne primes, and five Fermat primes, which gives a total of 49 numbers n such that n^♯ doesn't have three distinct prime factors. Here are the first few values of n.

1 2 3 4 7 8 16 31 127 256 8191 65536 131071 524287

Note that the prime 3 isn't double-counted, even though it's both Fermat and Mersenne. As a Fermat prime it produces the counterexample 2^♯, while as a Mersenne prime it produces 3^♯.