I grew up with Countdown as part of my diet. I had a crush on Carol Vorderman (before she went all advertisey and weird). I loved the numbers game, obviously – although I still have some slight resentment that Ian Scarrott was class champion rather than me. A few years back, I implemented a numbers game solver and thought no more about it.

Until the estimable @PlaneMirrorArt tweeted:

… and I remembered about an interesting connection between words and the Fundamental Theorem of Arithmetic, and thought I’d have a go at that, too.

## FTA FTW!

The Fundamental Theorem of Arithmetic is the one that says every positive integer ((except, possibly, for 1)) is the product of a unique set of prime factors. You can write the factors in any order you like, and the number of each particular factor is important.

So how is that helpful? Well, you can create a one-to-one mapping between letters of the alphabet and a subset of the prime numbers - so, perhaps, A corresponds to 2, B to 3, C to 5 and so on up to Z <=> 101. Then you can represent any string of letters by the product of the corresponding prime numbers: for example, DAB would correspond to $7 \times 2 \times 3 = 42$. BAD would correspond to… 42 as well.

That looks like a bad thing - but in fact it’s good: the order of the letters in a word, as far as the game is concerned, is not important. If the same letters come out in a different order, the same words are available; and if DAB is available as a word on the board, then so is BAD.

But the kicker is better yet: DAB and BAD are possible answers to a board of letters if and only if 42 is a factor of the number corresponding to the board! Or, in general:

The Fundamental Theorem Of Countdown: let $w$ be a word, $b$ a board of letters, and $P(s)$ the product of the primes corresponding to the letters of $s$. Then $w$ can be made from $b$ if and only if $P(w)$ is a factor of $P(b)$.

## Why are you telling me this?

If, like Andrew, you want to find the most useful Countdown words to know, it’s a pain to search through all of the possible combinations of letters and match them against all of the possible words.

If you use the FTC, and especially if you index the words up front, so the computer knows that 42 corresponds to BAD and DAB, you can save yourself a lot of time.

Here’s how my code works:

• Run through a big list of words and list them according to their corresponding product.
• Generate random boards, $b$ of letters with the right frequencies
• If $P(b)$ is in the list of products, save the appropriate word
• If not, consider every eight-letter sub-board (then seven, six and five) doing the same thing
• Count how often each word is the best possible

(In fact, I work with the sum of the logs of the corresponding primes rather than the product of the primes themselves – I’m not sure that it’s any quicker in the long run, but I like it.)