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.