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.

Where Do Ideas Come From?

Sometimes I have too many ideas. The problem becomes: which ideas might pan out, and how do they interrelate? But for most, it's more a question of: where do ideas come from? Let's talk about the various places.

Spontaneous Head Combustion

Sometimes an idea just pops into your head. I think this is because brains are always processing in the background. I had a calculus teacher in high school, Mr. Pearson, who said that the solution to a particular differential equation he had been working on would sometimes come to him while shaving.

Though that was a fairly nerdy thing to say, he wasn't far off my point.

The process of spontaneous idea generation is related to why we dream: the brain always wants to exercise in periods of disuse. When shaving or driving, your brain is not fully engaged. This means there are cycles that can be put to use. We will return to this later. But some people dream in ways that are connected to stuff they are working on. During my most productive periods when I get a cool idea and then rush to implement it (especially a very complex one that will probably take several days of constant work) I am told that I sometimes talk in my sleep: I'm mumbling variables and data structures. This definitely happened to me when I was working on Mosaics in Painter.

Hmm. Maybe I work too much!

But a simple way to use this is to think about a problem before you go to sleep, and your mind may come up with a solution while you sleep. In fact, I used to listen to music in my head right when I was going to sleep. I liked to listen to Beethoven's 9th Symphony in this state. Not really listening, per se. Actually just hearing it in my mind, every note and phrase. It was great practice for musical composition.

Sketch It Up

I like to sketch things out, and get ideas that way too. I guess it's because I'm a visual person. But, for me, lots of graphical ideas work themselves out on paper. A doodle can quickly become something larger.

I was working on borders and corners one day when I realized, as many people have, that you could represent the corners as four image pieces and the edges as another four image pieces. And the edges could be stretched or repeated. So I drew one of my favorite things, and I have reproduced it at left. I suppose it's a good example of three-dimensional thinking.

I draw in guide lines that showed the corner pieces and the edge pieces succinctly. Then I realized that these corners and edges could be filled with pretty much any image.

So i drew cylinders with pipes interconnecting them, like you see at right here. I realized that even shadows could be part of these clipped images. Note: this 3 x 3 partitioning is used to create buttons and other UI elements, also. In fact, that was what I was using it for at the time.

But I didn't want the UI to be constrained to be a rectangle. No matter! These pieces will still work, as long as all the corners are squarish. For instance:

At right, I have shown something that can be made out of the usual eight pieces, just rearranged in a different fashion from the typical arrangement I have shown so far.

This goes to show that it doesn't matter how you design it. If you take a little care, that design can service a much larger class of objects.

This design really hinged on two things: the corners and the edges. So I concentrated on the corners. What could the corner possibly be? A number of three-dimensional things popped into my head, and I sketched them up.

Here are a number of possibilities that occurred to me, drawn as corners. To left: a gabled approach that exhibits shading and has pyramidal corners. To right: that same approach, but with different edges. The edges can have their own articulations as well.  There are plenty of three-dimensional things that can grace the corner of a design.

Here, I explore the use of cubes and balls. To right I considered using a stake at each corner and a taut piece of rope in between. And knots on the rope in between the corners.

Of course, there are a number of articulations on the edge that can be used in addition to knots and spikes. Really, any repeating line pattern can be employed along the edge.

Here are some line patterns: wavy lines, beads, and twisted rope. Of course braids and yarn motifs are useful as well. But plain patterns, like stripes and diagonal "candy" stripes are also useful.






Exercising Your Brain

When I am otherwise not mentally engaged, I use that time for practice. Sometimes I do something tedious like factoring five-digit numbers in my head. You know, I like prime numbers. For instance, today I passed a house on San Jose-Soquel Road that had a number of 24,769. (I look on the right side as I'm driving home and there are often odd numbers like this one, which means they won't be divisible by 2.) I'll cut to the chase and tell you that it's 17 x 31 x 47. It took me about 4 minutes to determine that, performing long division in my head. Then, when I got home, I checked it using Siri.

It may be tedious, but it does help to keep my brain sharp when it comes to numbers. Another activity I do while driving is writing songs. I compose the melody and lyrics simultaneously. When I get an idea, I record it into Voice Notes, an iPhone app. I will go over the lyrics a few times and record a verse or a refrain.

This process keeps my creativity working while I would otherwise be bored. Exercising the right side of my brain. I used to turn on the radio while driving. I don't do that any more. I let my mind fill the silence.

I also got a great idea for a novel while driving. So I used Voice Notes to get it all down.

And, by the way, it might be a good idea to pull over, if you get too involved in an idea while driving!

Know Your Subject?

When I am wracking my brain for ideas on a particular thing, I can easily come to a standstill. It is at moments such as this that I take a step back. Specifically, this is called meta-level thinking. This process can actually be impeded by knowing too much about a subject. You can get into the mindset of thinking that it's all been said and done.

When writing a novel, it can be as simple as taking a step back and considering a character's arc. When writing music, this can manifest itself as rearranging the structure. Or adding in a full break or another device that so often makes songs interesting to our ears.

The Beatles practiced this. In We Can Work It Out, for instance, there is a section that breaks into triplets in an otherwise foursquare piece. On the back side of Abbey Road, they ran all the songs together into a single homogenous piece, a structural device.  In Getting Better, one of the verses becomes one long melody instead of several broken up melodies. On All You Need Is Love, the verses contain an extra half-measure per phrase, which helps to offset the otherwise foursquare melody (the Beatles called it the Dirge), the device of changing the time signature.  Or just having two authors can create a cognitive dissonance that can make a piece remarkable. On I've Got A Feeling, arguably the last composition that Lennon and McCartney wrote together (unless you consider the back side of Abbey Road to be a single piece), their contributions are quite different, and improve the song immeasurably. It goes on and on.

When programming, it helps to look at the problem in a different way. This can be a meta-level approach when you look at multiple ways of solving the problem, or you find a way to combine what would otherwise be different methods. This is particularly good when there is something you are missing.

Sometimes it's just a matter of employing multiple modes of thought at the same time.

Ideas Travel In Groups

When finding another person that is likewise creative, it is often possible to have a huge idea session. This has happened to me countless times with various people, including Tom Hedges and John Derry, the co-authors of early Painter.

A single session can generate hundreds of good ideas, I have found. When you get onto an interesting or fruitful subject, the result can be a veritable treasure trove of ideas.

This may be the Lennon and McCartney effect: the influence of two brains on creation is synergistically better than if the two created separately.

I have experienced this effect with John Derry on several occasions. Together we thought up Painter's image hose, for instance.

Combining Expertise

When you become an expert on one subject, it can help to give you the ability to solve problems in that subject. But is thorough research a ticket to stagnation?

I have found that it helps to be an expert on several subjects and then to combine the knowledge between the subjects. I'm a pretty good programmer, for instance, and I know how to draw. Combining them produced Painter.

Anyway, it's hard to ignore the profound influence of general thinking: knowing a reasonable amount about several subjects and thinking about how they relate.

Grist For the Mill

I'm not sure why it is, but I am equally sure that this is true: when we have emotional experiences, we are driven to create. This is typified by Lord Byron clutching his forehead at the top of the stair: the tortured artist. Or by Michelangelo undergoing great pains to complete the Sistene Chapel's frescoes: the agony and the ecstasy. Is it a cliché that only through pain can we create?

No, I don't think that it is. After hitting a patch of black ice and crashing my car in Denmark on the night of December 28, 1995, I sat down and wrote 7 really good poems. Sure, I write song lyrics, but poems? I was in a rare mood that evening after some wonderful "Good Samaritan" Danes stopped to pick me up and kindly delivered me to my Hotel in Copenhagen. Note that this near-death experience is not chronicled in my post Handling Serious Events. It seems I have more than my share of such events.

But, seriously, how many love songs are there? How many my baby done left me songs are there? I tell you: there's something to this theory of emotional distress and creativity. It's grist for the mill.

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.