Seven

After my post on five-fold symmetry, I can hardly keep myself from writing about seven. It seems unlikely, but the number seven does have some surprising properties, which I will illustrate. For instance, despite being called an octave, the diatonic musical scale really consists of seven notes: C, D, E, F, G, A, and B. With a remarkable sense of synesthesia, some people like to think each note has a color to it. I have folded my concept of the colors of notes into a paper aperture for your amusement.

Musicians like Alexander Scriabin developed systems to assign colors to key signatures based on the circle of fifths. The famous Hungarian composer and piano virtuoso, Franz Liszt, had a famous quarrel with Russian composer Nikolai Rimsky-Korsakov about the colors of the various key signatures; they saw them quite differently.

Seven is an odd prime number. Because it divides evenly into 1001 (and 1001*999 is one less than one million) its reciprocal has a six-digit repeat block, and thus seven the first number to have a repeat block that has length equal to the number minus one. It is a noble prime.

999999 = 3*3*3*7*11*13*37

Note that 7 and 13 have six-digit reciprocals, but 7 is often associated with good luck and 13 is often associated with bad luck.

An odd, prime number like 7 would seem to be impossibly irregular until you try to lay out seven pennies upon the table, as I did when I was five or so. I was surprised that it made the most elegant, regular arrangement possible.

And the seven pennies introduced young me to hexagonal packing. You can see that seven hexagons can make a hexagonal cluster. This is because it is a hexagonal number. The numbers 1, 7, 19, 37, ... , expressed as

1 + 6*T(n)

(where T(n) is the nth triangular number), are called hexagonal numbers because they give the exact number of smaller hexagons that can be put together to form a larger hexagon.

The clusters themselves can be fitted together. into an elegant offset packing, here shown using my Tile Patterns application. And a little help from Painter.

When I constructed this tiling, I had to work it out by hand first before I could enter it properly into Tile Patterns.

Here is my sketch of this tiling, giving some indication of the way I wanted to see it. Perhaps if we had hexagonally-packed eyes like the honeybee, and saw everything in these patterns, we would make our homes like they make their honeycombs.

It is only because my eyes are not hexagonally packed, I know, that I couldn't quite get the proportions right.

The green dashed parallelogram shows the repeat block of the offset tile pattern. It is because I like to think in squares and cubes that I can see it.

Seven is an interesting number for cubes as well, because it is one less than the cube of two.

Here I have illustrated that concept for you. It's always easier to see it visually than to just read it, I think.

Put one cube in the missing corner and you can make a 2x2x2 block. Two cubed is eight. So this shows seven cubes. Plus, I like a good graphic!

When it comes to seven, we do spend a bit of time dancing around six and eight.

The first diagram I showed was a folded paper aperture with seven sides. Its outline is a seven-sided regular polygon, called a heptagon.

Connect the corners of a heptagon and you can make various forms of seven-pointed stars.

Many countries use five-, six-, seven-, and eight-pointed stars as their symbols. Normally there are the wide star and the thin star. The Sheriff's Badge symbol uses a seven-pointed star that's somewhere in-between the two.

Other than these I don't really know other ways that the seven-pointed star gets used. This illustration I have created is a mandala form. I have applied a little color so you can see the various shapes better.

Seven dots on a grid can be situated in several different ways. But if you look at seven as two times four minus one, then you can see how a corner of one square may be shared with the corner of another square.

Each number is unique and interesting. In music, there is more to seven than just the diatonic scale. There is also music that features seven beats per measure, like Money by Pink Floyd, Solsbury Hill by Peter Gabriel, and the final Precipitato from Prokofiev's Piano Sonata No. 7 in B-flat. When I get in a mood, I will use this time signature. Usually it is broken up into two-two-three.

Finally, did you know that graph theory is based upon Leonhard Euler's solution to the problem of the Seven Bridges of Königsberg? Walk through the city, crossing each of the seven bridges exactly once. Once again the number seven provokes thought. Euler abstracted the two sides of the river and the two islands into four nodes and the bridges were thus abstracted into the seven arcs between them. The number of arcs attached to each node is called the degree of the node. If a node has even degree, then any path can enter and leave the node in an equal pairing. But if a node has an odd degree, then either the path must start or end there. It is easy to see that if more then two nodes have odd degree it is impossible for a single path to traverse all nodes, using the arcs between them. This is because a path must have only two endpoints. Königsberg's graph has four nodes of odd degree. Thus no such walk can exist.

So the number seven was actually the doorway to graph theory in the eighteenth century!

Factoring Numbers In My Head

I do have some fun hobbies: writing songs, drawing, thinking about the future, piano improvisation, and even some marketing. But the oddest hobby I have is this: I like to factor numbers in my head. While going to work, I pass by Summit Road, where the numbers are five digits long. I pick the odd size of the street, find a number, and factor it into the canonical product of prime numbers. While driving.

So I'm going to tell you how I do it.

The prime numbers are a sequence of whole numbers that are not divisible by any number other than 1 and itself. And 1 is not a prime number (for our purposes) because otherwise a canonical factorization could contain any number of powers of 1. The prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ....

So, the canonical factorization of 100 would be 2*2*5*5, or two squared times five squared.

When I factor a target number, I keep the factors I have extracted so far in my short term memory. The result of dividing out those factors is then called the new target number, and I only have to remember that one. The original target number doesn't matter. Only the factors matter (and the current target number). If I need the original target number, I can multiply all the factors by each other to recompute it.

So, rule number 1:

• minimize the number of things you have to remember

Small Factors

You can quickly rule out some small prime factors quickly using some tests that allow you to avoid long division. There are a number of shortcuts to factoring. They involve some simple numerical tricks that are a natural consequence of our numbering system (base 10) and the whole numbers themselves. The first rule is:

• if the last digit is even, then the number is divisible by two

This one is obvious. Of course, after you have been using the rules for years, they all are obvious. To explain, because 2 and 5 evenly divide 10, the base of our number system, it is trivial to determine if 2 and 5 are factors just by looking at the last digit of the target number, as shown here. For 5, the rule is really simple, by virtue that our number base (10) is divisible by 5:

• if the number ends in a five or a zero, then the number is divisible by five

You can look for multiple of four, eight, and so forth:

• if the last two digits are divisible by four, then the number is divisible by four

• if the last three digits are divisible by eight, then the number is divisible by eight

Here are some 3-related rules. These two rules are as old as the hills, and there are probably millions of people that know them.

• if the sum of the number's digits is divisible by three, then the number is divisible by three

• if the sum of the number's digits is divisible by nine, then the number is divisible by nine

So the number 23181 has a digit sum of 2+3+1+8+1 which is 15. If I use these rules, I can see 23181 is divisible by 3, but not by 9. But most people don't know this rule about 11:

• if the number's odd-position digits minus the number's even-position digits is divisible by eleven, then the number is divisible by eleven

For instance, the target number 81796 has an odd-position digit (green) sum of 8+7+6 =21 and an even-position digit (red) sum of 1+9=10, and their difference is 11 (which is divisible by 11), so therefore the number 81796 is evenly divisible by 11. In the diagram, you can also see this method show that 40247 is not evenly divisible by 11.

There are some clever rules for 7 and 13, but they are probably too complicated to perform in your head while driving.

The second part of extracting small factors is dividing by the small factor, once you have determined that the number is divisible. I guess I have become an expert at dividing by two, and three since I have the multiples of two and three memorized. To divide by five is easy: just multiply by two and divide by ten (shift out a zero). For the rest of the small factors, it really helps if you know your multiples of 7, 11, 13, 17, etc. inside and out.

Strategies

The standard method for factoring a target number is to divide it by all primes less than or equal to its square root. If you find a prime that divides it evenly, then you compute the quotient and factor the lesser number. If the number isn't divisible by any of the potential factors, then the target number is itself prime.

So that's the next step, if you have exhausted the small factor tests. Start trying to divide the number by successive prime numbers. But wait, what about strategy? There is one target number we are trying to factor, and lots of small prime numbers we would like to try to divide into it. So, actually we would like to rule out as many prime factors as possible. We want to quickly be able to say that a particular prime does not divide into the number.

So we word our interrogation like this: if the number is divisible by this prime then the following must be true. For instance: if I subtract a multiple of 7 from the number, then the number is divisible by 7 if and only if the remainder is divisible by 7.

Now, doing long division in your head can get a little complicated. So, even with long division there are a few tricks that I use. At this point, I have an odd number that I know isn't divisible by 2, 3, 5, or 11.

All the target numbers that are left must end in 1, 3, 7, or 9.

And any quotient I will get by dividing my number by such a prime must also end in 1, 3, 7, or 9. This is because the target number must be a product of primes or it must be a prime itself. This knowledge in and of itself is useful.

For instance, if I'm trying to divide 23181 by a prime ending in 7, I know that the last digit of the quotient must be a 3 because 7 times 3 ends in a 1. Or, symmetrically, if I'm trying to divide 23181 by a prime ending in a 3, I know that the last digit of the quotient must be a 7.

Here is a quick diagram of all the last digits of a factor ending in 1, 3, 7, or 9 (columns) and the numbers 0 through 9 (rows). Like a sudoku, each column contains all ten possible digits exactly once. With 0 and 5 being in predetermined places.

So, just by knowing my multiplication table, I have narrowed down the long division quotient by one digit. And I can repeat this, because I'm only trying to see if the potential factor divides the number of not (emphasis on the not, because it's the common case).

So, you can perform the long division from the top digits down, which requires doing lexical comparisons, or better yet, from the bottom digits up, which requires only matching the last digit. Your choice. With any particular number and any particular prime you are dividing it by, one of the two ways will be easier than the other.

Usually, I find long division easier when dividing up from the right. Especially if we are only trying to reject the factor.

Let's see if 23181 is divisible by 13. Most likely it is not (12 times out of 13).

To be divisible by 13, since the number's last digit is 1, and 13 ends in a 3, we can see that the quotient must end in a 7. So, we want to subtract 7 times 13 or 91 from the number. If I subtract it off, I get 23090. I know that if 23090 is divisible by 13, then 2309 must be divisible by 13 (uhh... since 10 and 13 share no common factors). Now, 2309 ends in a 9, so for 2309 to be divisible by 13, the quotient must end in an 3. So I need 3 times 13, which is 39 to be subtracted from 2309, which makes 2270. I know that if 2270 is divisible by 13, then 227 must be divisible by 13. So, 227 ends in a 7 digit, and this means that the quotient must end on a 9. So I must subtract 9 times 13 or 117 from 227. This leaves 110. In order for 110 to be divisible by 13, then 11 must be divisible by 13. And I can stop here because I know 11 is not divisible by 13. So therefore the number 23181 is not divisible by 13.

This is called deductive reasoning by mathematical induction.

You will note that the dividend always loses one digit when I do long division from the right. This is not so when you do long division from the left. But it is effectively so, because the subtrahend always moves right by one digit each time. But note that you have to memorize the multiples of 13 in order to make the decision of which multiple to subtract. This is not so when you are doing long division from the right. In that case, you only have to know the last-digit rules.

If however I get to the end and determine that the number is divisible by the prime, then I will have to perform long division to get the quotient and then go to the next step. Well, actually I have already performed long division, backwards. I reverse the digits and that's the quotient.

Sometimes I do long division in the left-to-right order instead. I can make use of the bottom-up technique to predict what the remainder should be at the last digit. And sometimes this saves me time. Or, I can look at the remainder and recognize it as a prime, and then I know that it is not divisible by the candidate factor.

The most important thing about long-division in the left-to-right order is that you don't have to keep the quotient around. Remember, you are only trying to see if the divisor evenly divides the quotient, and so, when you subtract something off of one end of the quotient or the other, you can reduce the size of the quotient. Then long division gets easier as you progress.

Of course, once you decide that a factor does divide the number evenly, then you have to perform an actual divide and then the quotient does matter, because it's about to become the next target number.

Lots of shortcuts abound that make the process of factoring easier. And possible to do entirely in my head.

Estimating Square Roots and Cube Roots

When you are dividing a target number by a prime dividend and you get a quotient that is less than the dividend, then you have exceeded the square root of the target number and you are done.

Note that if we don't keep the quotient around, then it isn't possible to decide easily if you have passed the square root of the target number. So I like to estimate the square root before I begin the process of factoring a target number, and after I have ruled out as many small factors as possible. I am familiar with small squares and cubes just because I've obsessed on numbers most of my life. These aid me in estimating square root and cube root. But, for you, I have reproduced a table of small squares and cubes. Very handy!

To estimate square root, you remove pairs of digits from the right end of the target number until only you have 1 or 2 digits, and the digits left give you the first digit of the square root by comparing it with the x squared table shown here. I find that there's not enough accuracy between 1 and 2, so I sometimes look at the rightmost three digits when the first digit is a 1 through 4. Each pair of digits that you removed from the right end of the number means you multiply your estimate by 10.

Example: what is the square toot of 23181? Remove a pair of digits to get 231 (or 232 if you like to round up) and I decide that the answer is between 15 and 16. But probably nearer 15. Multiply it by 10 and you get 150. Probably somewhere around 153. According to my iPhone, the correct square root is 152.253... Not a bad estimate, it seems!

One strategic thing is that, when you get past the cube root of your target number, there can only be two factors. And since both factors must be prime, this often reduces the possible number of factors you need to consider. It depends upon the sparsity of primes, and specifically where they are sparse.

Estimating cube root is similar, except you remove triples of digits from the right end of your target number. And you end up with 1, 2, or 3 digits (sometimes 4 when the first digit is 1 through 8). Of course, for every triple of digits you removed, you have to multiply the result by 10 again to scale it properly.

Example: what is the cube root of 23181? I first remove three digits to get 23. The answer is between 2 and 3, but much closer to 3. Multiply by ten and you get, say, 29. The exact answer is 28.513... Again, I'm pretty close.

But then, numbers are my specialty.

Prime Numbers

When you need to keep a secret, it's all in the numbers. The prime numbers.

Number theory is the basis of many cryptosystems these days. The famous RSA public-key cryptosystem is based on computing a number that is the product of two large primes. And because that number is hard to factor, your secret is safe.

When I was a kid, I became interested in numbers. It started when I read The Lore of Large Numbers, by Phillip J. Davis, first published in 1961. There was also Mathematical Recreations and Essays, by H. S. M. Coxeter and W. W. Rouse Ball. This led to unusual things like memorizing pi to 50 places, so I could recite it at any time. And I am sure I impressed my parents to death by reciting it. I can still hear the cadence of the digits in my head. Pretty soon I became interested in computation.

I often used to ride my bike to the San Jose State Math Library to pore through its stacks of math periodicals. I was especially interested in the Journal of the Mathematics of Computation (known as J. Math. Comp. in the biz). You can access the back issues of this journal online.

Yeah, to say that I was a nerd might have been understating the issue! But my obsession led to an interest in computation and, in particular, such things as prime numbers, factoring, and continued fractions.

Also, remember that this obsession happened in the late 1960s, before I even touched my first computer.

Prime Numbers

You can think of prime numbers as the basis set for all integers greater than 1 because every such integer can be formed by the product of primes. Kids first get exposure to prime numbers in the fourth grade (or earlier) when they learn to reduce fractions.

You probably know that the prime number sequence starts with 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...

The prime number sequence thins out as you get to larger and larger numbers. This is obvious because with larger numbers, there are more and more factors that can possibly divide a number. The prime number theorem states that, as x gets larger, the number of primes less than x generally approaches x/ln(x). Note that ln(x) is the logarithm base e (2.71828...).

In any case, there are a lot of primes. There are, for example, 50,847,534 primes less than a billion. You can easily prove that there are an infinite number of them.

Meeting a Number Theorist

In the summer of 1972, I was in a program at UC Berkeley for promising high-school-age mathematicians, sponsored by the NSF and chaired by Professor Frantisek Wolf. Having studiously read J. Math. Comp. for years, one of my idols was Derrick H. Lehmer, one of the world's foremost number theorists. Professor Lehmer was at Berkeley at the time. One day Paul Gootherts and I worked up our courage and went up the his office in Evans Hall and introduced ourselves to him.

Imagine my surprise when I found that he and his wife Emma were packing up his office! He was retiring that very week. So I struck up a conversation with him. It seems that we were both looking at continued fractions and their use in producing approximations to square roots using irreducible rational numbers. His interest was in factoring theory. Apparently constructing the continued fraction for the square root of a number was useful in producing factors near to the square root of a number, which was in turn useful in a certain primality testing method he was researching.

I accompanied him to the computer lab in the basement of Evans Hall and watched as he loaded a huge deck of card into an IBM card duplicating machine. When it failed and destroyed some of his cards, he exclaimed, "oh, lord! it's eaten my cards!". Of course, no one was more passionate about the use of computers in mathematics than Lehmer.

His wife Emma was apparently from Russia. I noticed that she had dozens of Russian volumes on the shelves in their joint office. I also spoke with her because I had read her paper on repunit primes. Repunits are decimal numbers consisting only of a long chain of 1's. An obvious factor of 10^n - 1.

They were surprised to say the least to find a 16-year-old kid with such an interest in number theory.

My friend Paul Gootherts had implemented a multi-precise arithmetic package in Fortran that we had run many huge calculations on, using a reasonably-fast Control Data Corporation computer that he had timeshare access to. So there was plenty to show and talk about. We had brought our books of calculations. I think we had calculated the cube roots of the first fifty primes to a thousand places each.

Prime Quads

When, for a given integer n, four numbers of the form 30n+11, 30n+13, 30n+17, and 30n+19 are all prime, they are collectively called a prime quadruplet. This is a very dense arrangement of prime numbers. Some ready examples are (11, 13, 17, 19), (101, 103, 107, 109), and (191, 193, 197, 199). I took a particular interest in this arrangement after looking at D. H. Lehmer's table of primes under 100,000. With my number-obsessed vision, they practically jumped out at me. Hell, they still do.

When I went to Caltech, I spoke with resident number theorist Marshall Hall about writing a program to find prime quads, which I did. It took advantage of the fact that the center number 30n+15 was a single number that you could subject to a barrage of tests. Divide it by a prime and compute its remainder. That remainder cannot be one of four values, otherwise one of the four numbers in the quad will be composite. It was an exceptionally fast method of determine whether a prime quadruplet seems interesting enough to try to factor all four numbers.

Because of my interest, Hall introduced me to the Markov Spectrum.

Factoring and Primality Testing

The dumbest way of factoring a number is simply to divide it by all the prime numbers less than or equal to its square root. But there is an easy way to speed it up: divide the number by another number that is the product of n primes. Then the remainder, which you design to be significantly smaller than the original number, may be divided by each of the n primes in turn, looking for a zero remainder. This process makes the search about n times faster. This is because the remainder is much smaller and thus the divisions into the remainder will take less work. You can organize this into a binary tree to speed it up even further.

These days, a number field sieve may be used to factor unusually large numbers. But, I suppose that you can choose a thousand-digit number and it simply cannot be factored on any known hardware.

In order for this technique to be useful, it is not enough that factoring is hard, but determining primality must be easy also. And it does appear to be easier than factoring, and these advances have occurred in the last ten years. In 2002, Agarwal, Kayal, and Saxena (AKS for short) found a polynomial-time primality test. It has since been improved by Bernstein and Lenstra. Unfortunately, even an improved AKS algorithm still takes about a year to determine primality of a 100-digit number.

But practically, a randomized algorithm such as the Rabin-Miller method for compositeness testing is, on the average, much faster. The Jacobi Sums algorithm is very practical, having been used to determine primality of exceptionally large numbers (up to 3395 digits). The Elliptic Curve Primality Proving (ECPP) algorithm has been used on a 15071-digit number, with a running time of 5.1 GHz-years. Of course, it can be distributed to multiple processors to speed it up. On ECPP, a 100-digit number takes about 2 seconds to prove primality on the average. Much faster than one year! The Rabin-Miller algorithm is feasible on numbers with a million digits, but remember that it can only produce a certificate of compositeness. But it is fast: a 300-digit number takes about 23 GHz-seconds to certify compositeness.

So, people have been combining the approaches, by doing a fast compositeness test in parallel with a primality test. In this way, the running time of primality testing (with an early-out for a composite number) is minimized.