Not Polyomino-related at all: Mental Factorisation

I should spell it 'factorization' a few times so it shows up in searches when Americans look for it.

Contents

Introduction

I'll tell you how this one came about. For a while I worked in software development and I was that fantastic combination of being both not good at my job, and not terribly interested in it. And as a result, I found more and more of my job was consisting of what can be called covert dicking around. That is, the little doodles in the margins of notebooks grew to engulf entire pages, the window near me spent a lot of time getting looked out of, and I began trying to factorise the line numbers of wherever I was supposed to be makin' code at that particular time.

When I was up at the top of a document it wasn't much of a problem, they were little numbers and I was just reverse engineering the times tables I'd learnt in little school. But sometimes I'd find myself at the bottom of a huge file thousands of lines long, and it'd take a little bit more effort to pry a number like, say, 899 or 3451 into its factors. So I developed a little bit of a toolkit for factorising numbers of about this size entirely in my head, generally in under a minute or so.

The really easy stuff: checking for factors of 2, 3, 5 and 11

These are the standard issue divisibilty checks that I think you learn in high school most places. I was certainly taught them then, though thinking back now I can't remember if they were actually on the syllabus or just something a random teacher showed me because I was the kid who liked maths a lot and they thought I might find it cool. Anyway, here they are.

Eyeballing it for larger primes

Sometimes you'll be able to rule out a prime as a potential factor just by inspection. Take for example, the number 263, and imagine youre trying to see if it'll divide by 13 without remainder. 263 can be split like 26|3 (the '|' has no mathematical meaning here, just imagine drawing a line through the number to literally split it up) and notice the 26 divides nicely by 13 but the 3 doesn't. In cases like this where one part of the number divides and the other doesn't, you can conclude that the whole number won't divide. (If both partitions divide then it will divide, and if neither do they you can't really say - it might or it might not.)

And that's all well and good for finding a factor of your number. But what we want here is the full decomposition of the number into prime factors - how many times that factor goes into it. Which takes a little more work.

Removing these factors once you've found them

Essentially it's just long division, minus the writing down part. But sometimes there are little tips and tricks that make certain numbers easier to 'do'. Here's a few off the top of my head.

Case 1: numbers that partition into obvious multiples of p (where p is the current prime factor):
Example: Dividing 2151 by 3. These are the cases you live for, just by inspection we can see this is 21 joined to 51, and both of these are multiples of 3. So just divide each bit individually and re-concatenate: 21/3=7 and 51/3=17, so 2151/3 = 717. Piece of piss.

Oh yeah, you're going to want to get familiar with the multiples of 3, 5, 7 etc. above and beyond the times tables you learn in school. Just being able to know at a glance that 91 divides by 7.
And the prime numbers upto 100 too. Which isn't that bad; there's only 25 of them and since you're reading this site you're probably mathematically inclined anyway (or a friend/relative of mine (hi Mam)) so you'll probably know most of them anyway.

Case 2: Dividing by 5
Dead easy. If it ends in '0' take out the multiple of 2 and 5 together then divide by 10. I shouldn't have to tell you how to divide a number by 10. If it ends in 5 then do this:

Step 1: Chuck away the final digit (that's the 5 btw).
Step 2: Double what you've got left.
Step 3: Add 1. And you're done.

Example: Dividing 975 by 5: Lose the final 5 to get 97. Double it: 194. Then add 1, to get 195. And ooh look, it's got another multiple of 5 in there. That one can be your practice exercise.

Case 3: the rest of them. Okay, I thought there were more tricks. I was wrong. Basically, for the rest of these I just kind of split the number into a bunch of smaller numbers that 'overlap', i.e. some amount can be taken out of a digit and turned into tens and added to the column to its right, like 'carrying the 1' in reverse. Okay, this isn't going to make a lick of sense without an example so here it is.

I'm well aware that was possibly the worst explanation I could have given. Hell it all just amounts to long division or 'chunking' or whatevs anyway, just find your own way of visualising it, sheesh, I'm not your maths teacher.

A silver lining - you generally don't have to do this with numbers bigger than 3 or sometimes 7. Because once you're taking out two-digit prime factors things work a little differently, which we'll come to in due course.

Divisibility by 7

You will notice I didn't give a handy check for dividing by 7 earlier. And that's because my check for divisibility by 7 is a bit shit. It essentially amounts to looking for multiples of 70 or 700 etc. that can be subtracted from your number to give something a bit more manageable.

The 3-digits case

Just look for a multiple of 70 that's near your number, then hope and pray the difference between these two numbers if also a multiple of 7. Eg, say you're factoring 1533, and you've already taken the obvious factor of 3 out of it, whittling down our number to a mere 511. Notice that 490 is a multiple of 70 that's pretty close to 511. And the difference, 511-490 is exactly 21 which is a multiple of 7. So it divides with no remainder. Hells yeah. Now we've just got to find out how many times 7 goes into 511.
Again, fairly easy. It's 490 + 21. 490 is 70x7, 21 is 3x7. So our answer is 70+3 = 73. Which is prime so we have our full factorsation of 1533: 3x7x73.

(Fun fact: 511 is one of those numbers I don't even need to think to factorise, I just instantly see 7x73. Along with 2047=23x89. Because 511=2⁹-1 and 2047=2¹¹-1 and I read something about Mersenne numbers when I was at a really impressionable age clearly, and those two facts are just etched indelibly on my brain in the place where I'd probably be storing phone numbers if I had more than 3 friends...)

The 4 digits case

Any 4 digit number can be turned into a 3-digit number by the following nifty hack below, and then the above case can be employed.

7, 11 and 13

It is a useful fact that 1001 can be factorised as 7x11x13. Hence, subtracting multiples of 1001 from a 4-digit number will preserve its divisibility by those numbers. This is peachy for us because it means we can just keep subtracting 1001 from four-digit numbers to get a 3-digit number which is way easier to check divisibility on. And subtracting 1001 from a number in your head is fairly straightforward.

(Checking the primeness of 191 is an exercise for the reader.)

Tricks for dividing by 11

The 3-digit version

Lots of 3-digit multiples of 11 are really nice in that the middle digit is the sum of the first and last digit. E.g. 231 is 11x23, and that 3 in the middle is 2+1. In these cases, to divide by 11 just knock out the middle digit and there's your answer. 484 = 44x11, 198 = 18x11, etc. etc.

But it's never always that easy. Imagine your first and last digits sum to more than 10. Like 8 and 7. In this case, the middle digit is the second digit of the sum, and the tens digit overflows into the hundreds column, giving a number that isn't immediately obvious divides by 11: here, 957. So to divide by 11 by eyeballing it, we first rule out an easy case - 9+7 is way more than 10. Then we subtract 1 from the hundreds, add it to the units to get 8+7=15, and the units column matches our middle digit. Voila - we have 11x87. With a little practice these become just about as easy to spot as the cases that play it straight.

The 4-digit version

Use the adding up alternate digits method to check for divisibility. Then once you know it divides, you can often pick the 3-digit factor out by eye. Say your 4-digit number has digits abcd. Then the last digit of your factor is the same as the last digit of your big number: d, its first digit will probably be the same as the big numbers first digit, a, and your second-last digit will be c-d (or (10+c)-d if your unit is bigger then your ten.) Again, big digits that cause sums to be greater than 10 and overflow ruin this. But in a decent number of cases this method is still viable.

17 and 19

This is where it stops being fun and starts being a slog. Basically, by this point the number you'll be factorising will end in 1, 3, 7 or 9, because all the factors of 2 and 5 will have long since been discarded. What we want to do is add (or subtract) a multiple of our prime p to our number such that the total ends in 0. Then we can discard the zero and work on this new easier number with one fewer digit. For 17 we have the following:

So if we have 901, we want rid of that 1 and we do so by subtracting 51. That gives us 850. And if this divides by 17 then so will 85. (It's probably wise to get familiar with the multiples of 17 (and 19) under 100 to make this a faster process - there's not a lot to klearn, 17, 34, 51, 68, 85 and 19, 38, 57, 76, 95.)
So we're 3 less than 850, and 850 is 50x17. Which means our full number is 50-3=47 times 17. Sweet.

Sometimes if it's a two-step case like the example above, the second number might be even (shock!) or a multiple of 5 (horror!). Just divide it by 2 or 5 until it ends in 1, 3, 7 or 9 and keep on trucking. Of course this makes it merry hell to keep track of how many multiples of 17 or 19 are in the number in total; in this case it's best to just use this method as a divisibilty check, then roll your sleeves up for some good ol' fashioned long division afterwards.

Since 1003 is 17x59, you can sometimes subtract lots of 1003 from your original number to get a quick check for divisibility by 17 (or 59). But what's perhaps more useful is that 1020 is 17x60. It's a littler harder to subtract multiples of 1020 but when you're working out how many 17s total divide into your number, you'll be adding multiples of 60 which is far nicer than 59.

23 and 29

You can use the above method for these two as well (changing the totals you add to subtract to things like 23, 87, etc. obvs) but there's also a sneaky thing you can do along the lines of what we did with 7, 11 and 13. You see, 2001 = 3x23x29 so you can subtract 2001s from your number without affecting its divisibility by these.

Sadly, for numbers that have an odd thousands digit, this only makes the number a smaller 4-digit one, you can't often reduce it to 3 digits unless you can neutralise the units digit.

For 31, as well as most primes above 31, the best you can generally do is a variation on the 17/19 method. Just adding monstrous numbers like 93 to make a multiple of ten whose final digit you can discard. But a few numbers are just nice, and I'll mention a few below.

37

37x3=111. So multiples of 111 can be added or subtracted from a number to make it easier to check.

101, 103 (and sometimes 107 and 109)

Multiples of 101 just look funny. Something like 5757 where it's just a repeated pair of digits, take that 101 out first then you have to factor the way nicer 57. Likewise, a number like 1391, to the trained eye is obviously just 13 pushed up next to 7x13, or 13x107. In fact this is just a particular case of the 'eyeballing it' method of long division earlier on.

73

10001 is 73x137, so if you ever have the misfortune of having to check a 5-digit number for divisibilty by 73 you can take off multiples of 10001 until you have a 4-digit number. I mean, checking the divisibilty by 73 of a 4 digit number isn't an endeavour I'd wish upon anyone, but it is an improvement on the 5 digit case.

An Additional Technique - Difference Of Two Squares

Think of any square number, something like 7x7=49. Now, look at the number one below it, 48. Which can be thought of as 8x6. (or as 2⁴x3 if like me you're at the stage where you've been bitten and now compulsively factorise every number you see into its constituent primes...) The important thing here is that 6 and 8 are one less and one more than 7 respectively.
It's the same for other squares - 10x10=100, and 99=9x11. This can be generalised for numbers that are further than 1 below a square, too. Essentially we have

(x² - a²) = (x - a)(x + a)

that is, a number that's a less than x squared can be factorised as x-a times x+a. (I know. I'm using 'x' as a times sign and as a number. Fite me irl.) If you've got this far through this article you probably don't need all this explaining to you in as patronising a way as I'm doing, but I like to spell things out just in case there's, like, a kid or someone whose eyes glaze over when they see a formula reading. Lord knows I was in group A once and grew up to become one of group B. Anyway...

If your number is a square away from a bigger square, you can find two factors right off the bat using this. Can't guarantee they're prime, but it's a start.

Unfortunately, to really get the most out of this method, you need to be know by heart the big square numbers like 1521 and 5929 and 2025 and stuff. Squares under 1000 (well, 961=31²) are a must, higher are optional and I'll confess I don't even know these. I know a scattered few but not many. But times when this method is actually applicable are fairly few and far between so don't sweat it.

Some full worked examples

Test your newfound skillz

If you're itching to test out these new superpowers, and you happen to have python installed on your computer, the following script will play as a little game in the console window, feeding you numbers that you have to factorise (and input strictly in ascending order with dots delimiting them... I wasn't kidding about the whole bad and lazy programmer thing). Save it as MentalFactoring.py or something and away you go.

# Mental Factoring v1.5
# By Lewis Patterson
# 23/11/2023

import math
import random
import time

def nextFactor(n):
    if n % 2 == 0:
        return 2

    for a in range (1, (math.ceil(math.sqrt(n)//2) + 1)):
        if n % ((2*a)+1) == 0:
            return ((2*a)+1)
    else:
        return n

def factorise(n):
    if n == 1:
        return 1
    
    lastfactor = 0
    factorlist = []
    remainder = n
    while lastfactor <= remainder:
        lastfactor = nextFactor(remainder)
        factorlist.append(lastfactor)
        remainder = remainder // lastfactor
    return factorlist

def GetSuperHardNumber(minv, maxv):
    acceptNumber = False

    while acceptNumber == False:
        k = random.randint(minv, maxv)
        fact = factorise(k)
        if 2 not in fact:
            if 3 not in fact:
                if 5 not in fact:
                    if 7 not in fact:
                        acceptNumber = True

    return k

def GetNumber(minValue, maxValue, filterValues):
    acceptNumber = False
   
    while acceptNumber == False:
        r = random.randint(minValue, maxValue)
        if r not in filterValues:
            acceptNumber = True
           
    return r

def StandardGame(questions, minValue, maxValue):
    totalCorrect = 0
    filterValues = []
    
    t0 = time.time()

    for x in range (0, questions):

        if superhard == True:
            r = GetSuperHardNumber(minValue, maxValue)
        else:
            r = GetNumber(minValue, maxValue, filterValues)
            
        print(r)
        factors = '.'.join(str(i) for i in factorise(r))

        playerAnswer = input()

        if playerAnswer == 'x':
            print("Player manually quit.")
            return

        if (playerAnswer == factors):
            print("CORRECT!")
            totalCorrect += 1
        else:
            print("WRONG! ", factors)
            
        filterValues.append(r)

    t1 = time.time()

    diff = t1 - t0
    minutes = math.floor(diff / 60)
    seconds = round((diff - (60 * minutes)), 2)

    print("Well done, you got", totalCorrect, "out of", questions, "right.")
    if (minutes > 0):
        print("Time taken:", minutes, "m", seconds, "s.")
    else:
        print("Time taken:", seconds, "s.")

def SurvivalMode(lives):
    roundno = 0
    filterValues = []

    minv = 100
    maxv = 300

    t0 = time.time()

    while lives > 0:
        r = GetNumber(minv, maxv, filterValues)
        print(r)
        factors = '.'.join(str(i) for i in factorise(r))

        playerAnswer = input()

        if playerAnswer == 'x':
            print("Player manually quit.")
            return
        
        if (playerAnswer == factors):
            print("CORRECT!")
        else:
            lives -= 1
            print("WRONG! ", factors, " -- ", lives, "lives remaining.")

        roundno += 1
        minv += 200
        maxv += 200

    t1 = time.time()

    diff = t1 - t0
    minutes = math.floor(diff / 60)
    seconds = round(diff - (60 * minutes), 2)

    print("Well done, you survived", roundno, "rounds.")
    if (minutes > 0):
        print("Time taken:", minutes, "m", seconds, "s.")
    else:
        print("Time taken:", seconds, "s.")

# RUNS from here:

print("MENTAL FACTORING v1.5")
print("")
print("How 3 play:")
print("A number will appear on the screen. Simply type its prime factors out")
print("in ascending order, separated by full stops. E.g. for 90 you would ")
print("type:")
print("")
print("2.3.3.5")
print("")
print("...just like that. If the number is prime, just type the number as is.")

canQuit = False

while canQuit == False:

    maxValue = 1000
    minValue = 100
    questions = 10
    superhard = False

    print("")
    print("Select a difficulty level:")
    print("")
    print("[1] EASY (10 questions at 100-1000)")
    print("[2] INTERMEDIATE (10 questions at 1000-2500)")
    print("[3] 'ARD (10 questions at 1000-10000)")
    print("")
    print("[4] MARATHON (100 questions, 1 to 1000)")
    print("[5] PRACTICE MODE (10 questions at 2-100)")
    print("[6] SURVIVAL: ENDLESS")
    print("")
    print("[7] Super Hard (10 questions, no factors < 10)")
    print("[0] CUSTOM")

    choice = input()

    if choice == "1":
        maxValue = 1000
        minValue = 100
    elif choice == "2":
        maxValue = 2500
        minValue = 100
    elif choice == "3":
        maxValue = 10000
        minValue = 1000
    elif choice == "4":
        maxValue = 1000
        minValue = 2
        questions = 100
    elif choice == "5":
        maxValue = 100
        minValue = 2
    elif choice == "0":
        print("Number of questions:")
        questions = int(input())
        print("Set max value:")
        maxValue = int(input())
    elif choice == "7":
        maxValue = 10000
        minValue = 1000
        superhard = True
        questions = 10

    if choice == "6":
        SurvivalMode(3)
    else:
        StandardGame(questions, minValue, maxValue)

    print("Press Enter to play again, or type 'x' to exit.")
    retryinput = input()
    if retryinput == 'x':
        canQuit = True

External links, further reading etc.

There's a paper by Hilarie Orman and Richard Schroeppel here that covers pretty much everything I've talked about (way better explained than some of my shambling attempts at coherency too!) plus a whole lot more advanced stuff too. Go check it out.

[ Home > Mental Factorisation ]

Lewis Patterson. Last updated 23/11/23.