Hazard

Techniques for Factoring Numbers in Your Head January 2, 2018

I’ve been factoring times while I walk my son to sleep, and it’s become kind of a game: can I factor the current time faster than he can fall asleep? After a few big matches, he’d developed quite a win streak, and I needed to up my game. I kept getting bogged down in the double digits. I needed a way to check a number’s divisibility faster than doing the mental long division.

Long division is not only a terrible algorithm to do mentally, it’s also kind of a terrible algorithm. It’s mostly trial and error. Personally, I spend a lot of time rounding and guessing. Mental long division is even worse. Even if you don’t have to do any guessing, you still have to keep track of a lot of numbers. Long division gains speed by consuming memory–just look at all the paper it uses. Good mental math algorithms require the opposite tradeoff, taking longer to execute but demanding less of your short-term memory.

Consequently, long division is a costly way to hunt for a number’s factors. While you’ll need the quotient if you find a factor, factors are sparse. Most primes won’t be factors of any given given number, and all the work of division will be wasted. What you need to get a leg up on your mental factoring game is a quicker way of rejecting primes as factors.

The first three primes have elementary techniques for checking divisibility. Two is a factor of any number ending in 0, 2, 4, 6, or 8, and 5 is a factor of numbers ending in 0 or 5. Any number with 3 as a factor has the curious feature that its digits add up to a number that’s evenly divisible by 3, a property we’ll take a closer look at later. Primes above 5 aren’t so easy to check, but it turns out that neither are they as hard to check as doing the long division.

David Wilson’s post “Divisibility by 7 is a Walk on a Graph” reveals an interesting technique that goes beyond 7. I’ve recreated David’s graph and algorithm below, and then I’ll explain how to extend his concept to numbers greater than 7.

  1. Given a number $n$, break it into digits $n_1$, $n_2$, $n_3$, etc., where $n_1$ has the largest place value.
  2. Put your finger on the above graph at zero.
  3. Move your finger along the gray arrows $n_1$ times.
  4. If there are any digits left to consider, move your finger along one red arrow, then repeat from Step 3 using the next digit. If there are no digits left, your finger is on the remainder of $n$ when divided by 7.

As an example, let’s see if 7 is a factor of 243. Starting at 0 at the top, go clockwise along the circle 2 steps to 2. Follow the red arrow to 6. Continue around the circle 4 steps to 3. Follow the red arrow to 2. Around the circle 3 steps to 5. The remainder when dividing 243 by 7 is 5, so 7 isn’t a factor of 243.

The logic behind David’s graph is this: the red arrows point from $i$ to $10i \space modulo \space 7$. Whenever we move to the next digit, we multiply by 10 and take the remainder when dividing by 7, thus slowly moving all values to their proper place values while at the same time subtracting out multiples of 7 and keeping all our numbers small. Keeping numbers few and small is important for doing the process in your head.

Let’s look at the graph for 11.

Following the red arrows becomes as simple as reflecting across to the other side of the circle—1 points to 10, 2 points to 9, 3 points to 8, and so on up to 10, which points back to 1. Where David’s algorithm for checking 7 requires memorizing a seemingly arbitrary graph, checking 11 needs nothing more than knowing what number gets you to 11.

It turns out that this gives us a trick for checking 11 that’s a close cousin to the summing-digits trick we use for 3. Notice that the red arrows in the graph for 11 never change your distance to 0, only whether 0 is ahead or behind you. In other words, rather than following a red arrow before feeding in the next digit, you could just reverse the direction of the gray arrows. In fact, a graph isn’t even necessary for checking 11. You can just alternate between adding and subtracting digits. Is 11 a factor of 341? $0 + 3 - 4 + 1 = 0$, so yes.

Let’s revisit the curious shortcut for checking 3, in which we instead check if the sum of the number’s digits is divisible by 3. Nine, though it isn’t prime, has a similar rule: if all the digits add up to a number that’s evenly divisible by 9, the original number is also evenly divisible by 9. This always struck me as strange. Why should adding up a number’s digits tell us anything about its factors? And why 3 and 9 should be the only numbers for which this works? The Wilson graphs for 3 and 9 shed some light on the mystery.

The red arrows don’t change your place on either graph. Following the gray arrows around the circle is simply addition modulo 3 or 9. The fact that 3 and 9 are the only cases of this property stems not from 3, but from 9. I’ve been drawing these graphs in base 10, but drawing graphs in some other bases reveals that when the number in question is one less than the base, the red arrows all loop back to the number they started at. Nine looks like this in base 10, and so does 3 by virtue of it being a factor of 9. In base 13, not only do you get 42 when multiplying 6 by 9, but adding up a number’s digits can tell you if the number is divisible by 2, 3, 4, 6, and 12.

For primes beyond 11, Wilson graphs are interesting to look at but difficult to use. Here they are for 13, 17, and 19.

That’s only half of the weird trick for factoring numbers in your head, we now need the other half—a way to remember where the red arrows point. Instead of plotting $10n \space modulo \space 13$ on a circle, let’s look at it as a scatter plot.

At the heart of this plot are the integers on the line $10x$. Any value greater than 13 has had its thirteens subtracted out, leaving us with a set of surprisingly well-organized dots. Notice how they fall into parallel lines. Two of these lines in particular are worth taking a closer look at: the positively sloped line through $(0,0)$ and the point nearest it, and the negatively sloped line through $(0,p)$ and the point nearest it. The equations for these lines are $\frac{1}{4}x$ and $-3x+13$.

Here are similar plots for 17, 19, and 23.

Parallel lines seem to be a common feature of these plots. Here’s a list of the aforementioned line slopes for all primes from 7 to 89.

$p$ positive negative
$7$ $3$ $-\frac{1}{2}$
$11$ $\frac{5}{6}$ $-1$
$13$ $\frac{1}{4}$ $-3$
$17$ $\frac{3}{2}$ $-\frac{4}{3}$
$19$ $\frac{1}{2}$ $-\frac{8}{3}$
$23$ $\frac{4}{5}$ $-\frac{3}{2}$
$29$ $\frac{1}{3}$ $-\frac{9}{2}$
$p$ positive negative
$31$ $\frac{9}{4}$ $-\frac{1}{3}$
$37$ $\frac{3}{4}$ $-\frac{7}{3}$
$41$ $10$ $-\frac{1}{4}$
$43$ $\frac{7}{5}$ $-\frac{3}{4}$
$47$ $\frac{3}{5}$ $-\frac{7}{4}$
$53$ $\frac{7}{6}$ $-\frac{3}{5}$
$59$ $\frac{1}{6}$ $-\frac{9}{5}$
$p$ positive negative
$61$ $10$ $-\frac{1}{6}$
$67$ $\frac{3}{7}$ $-\frac{7}{6}$
$71$ $10$ $-\frac{1}{7}$
$73$ $10$ $-\frac{3}{7}$
$79$ $\frac{1}{8}$ $-\frac{9}{7}$
$83$ $10$ $-\frac{9}{8}$
$89$ $\frac{1}{9}$ $-\frac{9}{8}$

Can you spot the connection between a prime and its slopes? Let me pick out the slopes that show the relation most clearly, and make all of them fractions.

$p$ slope
$7$ $\frac{3}{1}$
$11$ $-\frac{1}{1}$
$13$ $-\frac{3}{1}$
$17$ $\frac{3}{2}$
$19$ $\frac{1}{2}$
$23$ $-\frac{3}{2}$
$29$ $\frac{1}{3}$
$p$ slope
$31$ $-\frac{1}{3}$
$37$ $\frac{3}{4}$
$41$ $-\frac{1}{4}$
$43$ $-\frac{3}{4}$
$47$ $\frac{3}{5}$
$53$ $-\frac{3}{5}$
$59$ $\frac{1}{6}$
$p$ slope
$61$ $-\frac{1}{6}$
$67$ $\frac{3}{7}$
$71$ $-\frac{1}{7}$
$73$ $-\frac{3}{7}$
$79$ $\frac{1}{8}$
$83$ $-\frac{9}{8}$
$89$ $\frac{1}{9}$

The relationship is subtle. For prime $p$ and slope $\frac{a}{b}$ (where $b$ is always positive), $p = 10b - a$. So $7 = 10 \cdot 1 - 3$, $11 = 10 \cdot 1 - (-1)$, $13 = 10 \cdot 1 - (-3)$, $17 = 10 \cdot 2 - 3$, and so on. In fact, the first listing of slopes has several primes for which both fractions exhibit this pattern: $29 = 10 \cdot 2 - (-9)$, $31 = 10 \cdot 4 - 9$, $37 = 10 \cdot 4 - (-7)$, etc. This is a general pattern, though the way I selected lines didn’t always pick the right ones. In the scatter plot of 17, you can find parallel lines with the slopes $\frac{3}{2}$ as well as ones with the slopes $\frac{-7}{1}$.

So here’s the second weird trick for factoring numbers, and the more general one. It’s useful for primes from 13 to 89.

  1. Given the number $n$ and prime $p$, calculate $a$ and $b$. $a$ is $p$ subtracted from the nearest multiple of 10. $b$ is that same multiple of 10 divided by 10.
  2. Break $n$ into its digits, $n_1$, $n_2$, $n_3$, etc.
  3. Start with $n_1$.
  4. Multiply by $a$.
  5. If $b$ evenly divides it, divide by $b$. If not, add or subtract $p$ until the result is evenly divisible by $b$, then divide by $b$.
  6. Take the remainder when divided by $p$.
  7. If there are any digits left to consider, add it to the result and continue at Step 4. If there are no more digits, the result is the remainder of $n$ when divided by $p$.

Try it out with $n = 986$ and $p = 17$. The multiple of 10 closest to 17 is 20, so $a = 3$ and $b = 2$. Starting with $9$, $9 \cdot 3 = 27$, $27 - 17 = 10$, $10 \div 2 = 5$. Add the second digit, $8$, to get $13$ and repeat: $13 \cdot 3 = 39$, $39 - 17 = 22$, $22 \div 2 = 11$. Add the last digit, $6$, to get $17$, which is, clearly, evenly divisible by 17, so 17 is a factor of 986.

This turns out to be a good algorithm for mental factoring, since you never have to multiply by more than 3, you divide by numbers less than 10, and otherwise you add and subtract primes. Additionally, you only have to hold onto a few numbers from the beginning of the algorithm to the end, three of which stay never change ($p$, $a$, and $b$). The process itself is simple enough and repetitious enough to quickly get the hang of.

I can’t always factor the current time faster than my son falls asleep, but armed with this algorithm, I now have a fighting chance. If you have any other interesting mental math shortcuts, I’m happy to hear them. Contact me on Twitter or by email .