Conway’s factoring trick

The numbers 152 through 156 have a lot of small prime factors. I'll be more explicit about that shortly, but take my word for it for now. John Conway [1] took this simple observation and turned it into a technique for mentally factoring integers.

Conway's factoring method

To look for factors of a number n, write n as a multiple of 150 and a remainder:

n = 150k + r.

We started from the assumption that the numbers 152 through 156 are interesting, so let j = 2 through 6 and observe

n = (150 + j)k + (r - jk).

So n is divisible by one of the factors of 150 + j if and only if r - jk is divisible by the same factor. So we can test n for divisibility by any of the factors of the numbers 152 through 156 by testing r - jk for divisibility by the same factors. Here r is less than 150, so you're working with moderately small numbers.

Details and examples

Here are the factorizations of the numbers 152 through 156:

152 = 2^3 * 19
153 = 3^2 * 17
154 = 2 * 7 * 11
155 = 5 * 31
156 = 2^2 * 3 * 13

So the method above will test for divisibility by 2, 3, 5, 7, 11, 13, 17, 19, and 31, which is all of the primes below 41 except for 23, 29, and 37. Conway created a variation of his method to cover these primes, and another variation to cover primes up to 67. See [1] for details.

First example

So let's do an example. Let n = 817. Then

817 = 750 + 67 = 150*5 + 67

and so k = 5 and r = 67.

It's easy to see that n is not divisible by 2, 3, or 5. (You could test n directly for divisibility by 2, 3, and 5 or test r.)

Now let's look at 67 - 5j for j = 2 through 6. First, 57 = 19 * 3, so 817 is divisible by 19 (the largest prime factor of 152). Next, 52 is not divisible by 17 (the largest prime factor of 153). 47 is not divisible by 7 or 11, so neither is 817 divisible by 7 or 11. 42 is not divisible by 31, so 817 is not divisible by 31. And finally, 37 is not divisible by 13 and so neither is 817.

Second example

In the discussion above, we rounded down to the nearest multiple of 150. We could round up as well, writing n as

n = 150k - r

and looking at

n = (150 + j)k - (r + jk).

So instead of subtracting multiples of k, from r, we add multiples of k.

Take, for example, n = 887.

887 = 150 * 6 - 13.

So k = 6 and r = 13.

We can verify that 887 is not a multiple of 2, 3, or 5. Then we see that 13 + 2*6 = 25 is not divisible by 19, 13 + 3*6 = 31 is not divisible by 17, 13 + 5*6 = 37 is not divisible by 7 or 11, 13 + 5*6 = 43 is not divisible by 31, and finally 13 + 6*6 = 49 is not divisible by 13. So 887 is not divisible by any of the primes our method is capable of testing divisibility by. In fact 887 is prime.

Finger math

Conway associated the largest prime factors of 152 through 156 with the consecutive fingers: thumb for 19,. index finger for 17, etc. So as he subtracted factors of k, he'd keep track of what prime he's testing divisibility for by putting down consecutive fingers.

Why 150?

The premise of Conway's factoring method is that the interval [152, 156] is unusually rich in small prime factors. Is this interval unique in some sense?

The set of prime factors of the numbers in [152, 156] include all the primes up to 19. The following Python script searches for intervals [n, n + 4] whose factors also include all primes up to 19.

 from sympy import factorint for n in range(1, 1000): prod = n*(n+1)*(n+2)*(n+3)*(n+4) f = factorint(prod) if set([2,3,5,7,11,13,17,19]).issubset(f): print(n, factorint(prod))

This shows that 152 is the smallest value of n. The next value of n is 285, but it has a couple of disadvantages. The range also contains 9 prime factors, but the largest is 41 rather than 31.

The interval [986, 990] is possibly interesting. Its prime factors include all primes up to 29, as well as 43 and 47. It's certainly easy to subtract off multiples of 1000, and so you could create a rule analogous to Conway's rule with 1000 playing the role of 150. The downside is that now j runs from -10 to -14 rather than 2 to 6, so you're working with larger numbers when subtracting off multiples of k.

Related posts

• Testing divisibility by 7, 11, and 13
• Divisibility rules in hexadecimal
• Casting out z's
• John Conway and mental exercise rituals

[1] Arthur T. Benjamin (2018) Factoring Numbers with Conway's 150 Method, The College Mathematics Journal, 49:2, 122-12. Available here.

The post Conway's factoring trick first appeared on John D. Cook.