Antiprimes

This post originally ran 31 August 2009.

Everybody knows that a prime number is one which can only be evenly divided by itself and 1. Thus, for example, 13 is prime because no number except itself and 1 divides it. There has always been interest in primes, and lots of fun to be had with them (especially in cryptography, where your author got his start). More than that, primes are foundational to mathematics, as the Fundamental Theorem of Arithmetic attests: every natural number greater than 1 can be written as a unique product of prime numbers: every number is constructed from the raw material of primes. Isn’t that cool?

There are an infinite number of primes (here’s Euclid’s slick proof); further, and most curiously, primes appear to be salted “randomly” throughout the numbers. By this, I mean that there does not (yet?) appear to be any known list of premises from which we can deduce the primes. Another way of saying this is that there is no known formula for generating the primes.1 The implications of this are deep and vast.

The best all-around book on primes is Ribenboim’s, Book of Prime Number Records: beware, however, that this book requires at least basic familiarity with number theory.

Primes, if you like, are stingy with their divisors; but there are other numbers which are profligate. Antiprimes, which are usually known by the less euphonious title “highly composite numbers,” are the opposite of primes in the sense that they are numbers which have the largest number of divisors. Incidentally, theories about this class of numbers first came from Ramanujan.

The definition of antiprime is this: an (integer) number that has a larger number of divisors than any number less than itself. The first antiprime is 1: it has one divisor and no integers less than itself. 2 is the second antiprime: it has two divisors (itself and 1), which is more than the number 1 had. 3 is not antiprime because it has two divisors, tied with the two divisors of 2—to be antiprime it needed to beat the number of divisors of all numbers less than itself and it didn’t. This makes 4 an anitprime because it has 3 divisors; one more than 3 or 2 had. The first few antiprimes are: 1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260 (it’s fun to check some of these by hand).

Several of these are familiar, are they not? For example, most of us know that the Earth spins once around each day. It would be useful to divide this period into increments that are easily manageable. 10 such chunks seem ideal: call these chunks hours. There is a lot to recommend 10 as an hour base. 10 can be split into two even chunklettes, one for day and one night, for example. And finger counting is a trick easy to master.2 But what if we wanted to divide the day up into quarters for, say, standing watch? Can’t do it evenly with 10, because 4 doesn’t divide it. In fact, 10’s measly three other divisors (1, 2, and 5) limit its ability to make differently (integer) sized chunks.

12 certainly works: it rates a healthy six divisors (1,2,3,4,6), so we have a lot of room to play. But 24 is even better with eight (1,2,3,4,6,8,12). As a bonus, five divisors of 24 are themselves antiprimes: this gives us lots of room to maneuver if we want to carve up the day into manageable, manipulatable, and malleable pieces. And those first five divisors are almost the first five integers, the naturally divisors to any block (one-half, one-third, one-fourth, and so on). The Egyptians, Babylonians and other peoples who originated the 24-hour day might have thought about the number 24’s special properties.

Now, once you have hours, you still have to divide up the time inside an hour. Small, but not too small, chunks seem to be optimal. Minutes, and inside them seconds, as everybody knows, are used. There are 60 of each of them and 60 is, of course, anitprime. 100 isn’t wonderful because it can’t be, for example, divided by three. The Babylonians, who gave us these divisions, liked 60 astrologically: the heavens are divided into 60 (arc minutes) times 6 equals 360 degrees.

Also interesting is that most antiprimes are next to primes: 2 itself is prime, so start with 4: both of its neighbors are prime; so are both of 6’s and 12’s. Only one neighbor of 24’s and 36’s. The problem starts with 120: both of its mates are composite (119 is divided by 7 and 17, and 121 is divided by 11).

I’m not aware of the common use of antiprimes larger than 60. Do you know of any?

———————————————————

1 There are plenty of formulas to identify prime numbers, and even algorithms to generate some primes, but none that gives us all primes.

212-finger counting is also easy. Ignore your thumb and look at your fingers. Count sections of the fingers separated by the joints and viola! 12 emerges. It is said that Sumerians counted like this.

22 Comments

  1. Computer screen and television screen resolutions often come in sizes that use antiprimes. Both dimensions are not necessarily antiprimes, but often one is probably for the reason that is divisible into so many groups.

    For example, 480i television [http://en.wikipedia.org/wiki/480i] is 720×480. The width is an antiprime, and the height is a function of the aspect ratio.

  2. A lot of egg timers seem to be set to 180 seconds, or three minutes. Not sure why, but I seem to get those a lot.

  3. All,

    360 was there! (The ‘heavens’.)

    Ben,

    I had no idea. Interesting. Now who wants to play with ratios of neighboring antiprimes, for surely the ratio in screens matters. For example, the second 18 divided by the first 18 gives the string (to two digits):

        ratios = 2, 2, 1.5, 2, 2, 1.5, 1.33, 1.25, 2, 1.5, 1.33, 1.5, 2, 1.17, 1.5, 1.33, 1.5, 2

    and 720/480 = 1.5 ratio. Lots of doublings in there: associated with prime partners? I’ll let you guys figure it out.

  4. When did the decimal point make it to western math? And how long until the “commoners” were using it? All the standard units had lots of divisors.

    12 inches = 1 foot
    36 inches = 1 yard
    5280 feet = 1 mile
    12 pence = 1 shilling
    16 oz = 1 pound
    640 acres = 1 squre mile

    Government bonds traders are the last holdouts refusing decimal notation. They price their securites in eights of thirty-seconds. The notation would be 100-133. The 2 digits after the dash are in 32’s, the last digit is 8ths of 32’s.

  5. Ben, Briggs, I’m afraid the TV standards don’t work out as neatly as Ben suggests. First, TV systems were defined first by the vertical resolution, with the horizontal figure coming many decades later. Second, even 480i has only been around for a little over a decade. Analogue US TV systems use a 525 line standard (ie. the time for each frame is sufficient for 525 scan lines to be drawn – in wonderful Australia, plus India, Europe etc, 625 lines are used). Of these 525 lines, about 485 lines carried picture info (the rest was called the ‘vertical blanking interval’).

    The horizontal res was quite variable because we are talking about blips in an analogue signal. What with such issues as the Kell Effect, horizontal resolution on CRT TVs was typically rather less than 500 ‘pixels’ (they were called lines).

    This was rounded down to 480 lines with the introduction of DVD, in large part I suspect to make it a match for the VGA computer display standard (in Australia, of the 625 lines, about 585 carried picture info in analogue TV, and this was rounded down to 576 for digital TV).

    With DVD, because the video is held if the form of a series of digital images (both temporally and spatially compressed, of course), it became necessary to define a hard horizontal resolution. That’s where the 720 came from. In other words, antiprime though it may be, it was secondary to the vertical resolution. And it was not the only one. Other legit horizontal resolutions defined for DVD are 704 and 352 pixels … but not 360, oddly enough. Some early Panasonic DVD recorders actually used 704 pixels, and many DVD recorders use 352 for their higher compression recording modes.

    Finally, even 720 pixels isn’t a neat derivation from the vertical resolution and the aspect ratio. With a vertical resolution of 480, square pixels would demand 640 horizontal pixels (like VGA) for a 4:3 aspect ratio, and 853.33 for 16:9 (for Australia, etc, 768 and 1024 respectively, which may give a hint of why 576 was chosen as the vertical number). I suspect that 720 was chosen as a compromise between 640 and 853/4.

    Finally, just to round things off, for the first few years DVD player were incapable of delivering the full 720 pixels of resolution because they had analogue outputs delivering what came to be called 480i (576i here). Only when they went progressive scan and, better, digital (via DVI and HDMI) was the full horizontal resolution made available to consumer displays).

    Blu-ray does use square pixels and at 720p (ie. 1,280 x 720 pixels), 1080i and 1080p (1,920 by 1,080) resolutions it is restricted to 16:9 output only.

  6. In fact, there is a known polynomial (with twenty-six variables, if I recall correctly) whose positive values are precisely the set of prime numbers. This is a straightforward application of the Matijasevic-Robinson-Davis-Putnam Theorem showing that every computably enumerable set is Diophantine, which settled Hilbert’s Tenth Problem.

  7. “Also interesting is that most antiprimes are next to primes: 2 itself is prime, so start with 4: both of its neighbors are prime; so are both of 6’s and 12’s. Only one neighbor of 24’s and 36’s. The problem starts with 120: both of its mates are composite (119 is divided by 7 and 17, and 121 is divided by 11).”

    This seems pretty reasonable to me, since neither n and n-1 nor n and n+1 can share any prime factors. Since n, in this case, has a relatively large number of prime factors (more than any number smaller than it), then n’s neighbours have a restricted list of primes to choose from. (I specify prime factors, but I think this works for divisors in general.)

    Incidentally, your first footnote is (unintentionally, I assume) incorrect. There are algorithms that will generate all primes, but there are none that will generate an arbitrary (ie, the 10000th) prime.

  8. I was intrigued by the antiprimes and thought to generate some more with a Visual Basic program. They proved to be very sparse. The 40th antiprime is 1,441,440 and it took 8 hours 15 minutes to find it. I assumed the antiprimes are all even, otherwise I might still be calculating.

    After the first 16 given in the article, the series continues 1680 2520 5040 7560 10,080 15,120 20,160 25,200 27,720 45,360 50,400 55.440 83,160 110,880 (the 30th)

    Most of the differences of this series are themselves antiprime. There are only 5 differences in the first 40 that are not antiprime. 2520 and 5040 are quite common as is 55,440 (6 times in the first 40).

    The ratios of successive antiprimes are drawn from a small set. There are only a 10 in the first 40 antiprimes and they are all ratios of quite small numbers. The oddest ratio is 18/11 (45360/27720). The commonest ratios are 3/2 (12 times), 4/3 (8 times) and 2 (7 times).

  9. 8 hours?

    A number can be reduced to a product of prime factors.

    N=2^a * 3^b * 5^c….
    The number of factors has N is (a+1) * (b+1) * (c+1)…

    If N is anti-prime, a >= b >= c ….

    This isn’t sufficient to calculate all anti-primes, but in a hurry we can calculate a few hundred candidates, the number of factors for each candidate, and eliminate those that are not antiprime.

    It isn’t too hard to get pretty far into the series by guess work. Certain patterns in the ratios repeat. But, sometimes they don’t. 11 is a factor of 27,720. It isn’t a factor of the next two in the series (hence the 8/11 ratio), and it is a factor from 55,440 on.

  10. Anti-primes are the reason why whenever some idiot just blindly says “The Metric system is the better system for EVERYTHING” you can easily deduce that they are idiots.

  11. > the heavens are divided into 60 (arc minutes) times 6 equals 360 degrees.

    Arc-minutes are 1/60th of a degree, which renders this sentence incoherent. Six times sixty arc-minutes equals _six_ degrees.

  12. Years ago after reading a newspaper article about the difficult discovery of the (then) largest known prime I played with Matlab at work (lowly engineer who distracts easily) and plotted a histogram of the intervals between the first 10,000 or so primes to see if there was a pattern. I was surprised to see a significant spike at 6. Apparently it’s called a Jumping Champion and the value actually changes over much larger intervals of primes and you can then consider Jumping Champions of Jumping Champions, etc. I’m sure I’ve butchered the math lingo… In any case, any thoughts on anti-Jumping Champions?

  13. About the hand to the hand:
    If one were to be a churlish stick in the mud or a silly billy and insist on classical definitions alone other than for a point of interest or clarity, one would say something like:

    “CLEVER people would say phalanges or phalanx.”
    Or the anatomical word which we use, in the trade, for the bones of the fingers not counting the joints in the hand is….”

    Still, anatomy doesn’t change, people don’t discount the thumb, even an unborn baby which is especially fond of thumbs and familiar with them.

    It would be to throw out data to support a theory.

    There is a separate classical word for thumb but it only ever appears with reference to soft tissue attachment in anatomy. They are all called digits, the thumb is number one (They do each have various functions.) The thumb is not an outlier, there is no such thing.

    Now someone can pick over the story and talk about soldiers and throngs and fingers and phalanxes and archers but they will still be wrong about the human hand and whether or not thumbs are discounted instinctively by man except by prior arrangement!

    Perchance in a battle or in some kind of long distance sign language but that is overlay.
    The first method is to count all of the digits. You need as many as you can find, even toes are recruited.

    If a person says, which they have, they ‘had that, helicopter backwards.’
    Or “an integral hernia”,
    Or has just seen the archaeologist or ornithologist, the best thing is to know what they meant because you understand context and bite your cheek hard.

    Either you have to proceed to the crux of the puzzle for speed and so on, or you want to linger on the lingo until the time’s up.

    You will never play the viola easily with eight digits anyway, right!

  14. @Briggs:

    Your footnote is potentially misleading for the set of primes is computable and it is fairly easy to give an algorithm that enumerates the set, that is, an algorithm that generates the nth element in the set in finite time.

  15. 120, although not in ubiquitous use, has at least its own name (in English), the gross; as does 12 (the dozen).

    Question to those better versed in linguistics internationally or historically – are there “special” names for other numbers, especially for antiprimes? (7 for “times” or notions like “the perfect number” are likely here less relevant, but I am ready to be corrected on this point).

Leave a Comment

Your email address will not be published. Required fields are marked *