## L1916: Can You Do Division? by Rhombus

Posted by Encota on 10 Mar 2017

I’d like to claim that it’s taken me 50 years to solve this one, following some music-induced haze that had resulted from listening to the 1967 releases of Sgt. Pepper, Pink Floyd’s The Piper At The Gates Of Dawn (aside: how surreal is *that* Chapter VII of The Wind In The Willows?) and The Velvet Underground & Nico but I can confess that Oyler kindly shared this puzzle with me when his ’50 years on’ L4438 Can’t You Do Division? came out in February 2017 – and of course I couldn’t resist the challenge.

So here is the puzzle…

I started by creating a small pencil-drawn grid with 10 to 90 along the top and 0 to 9 down the other, so I could *begin* to see how the number of factors distributed.

This allowed me to solve (for example) **clue b**, where the only two appropriately-sized numbers with 10 factors are 48 and 80 and, presuming that clue C doesn’t begin with a zero, **48** it is.

I wasn’t familiar with any of the mathematics behind factorising, so was childishly pleased with my *very* rusty skills when I managed to prove that, if p, q and r are prime, then

**p^a*q^b*r^c has (a+1)(b+1)(c+1) factors**

[Here I am using ^ to mean ‘raised to the power of’, e.g. 2^6 = 2*2*2*2*2*2 = 64 ]

Aside: this is actually a lot easier to prove than it may at first seem to non-mathematicians. If you know how many factors p^a has, then multiplying it by q^b gives you all the original factors and then a new same-sized set when the original factors are all multiplied by q, then another same-sized set when they are all multiplied by q-squared etc all the way up to q^b. So you have an *additional* b times the original number of factors (count them!), i.e. (b+1) times that number in total. This can be extended to as many primes multiplied together as you like, resulting in (a+1)(b+1)(c+1)(d+1)… factors – or to fewer, to prove the original p^a must have (a+1) factors.

Once you know this, it then becomes straightforward to see the relatively few options that are available for some of the answers. The ultimate example is **clue p** (down). Here the clue says there are 35 factors. The only ways to factorise 35 as a product of two integers are 1*35 or 5*7. For the first the answer would have to be prime^34. But even 2^34 is way too big, so the only other way is Prime1^4*Prime2^6, and the *only* one of those anywhere close to being between 1000 and 9999 is 3^4*2^6 = 4 * 1296 = **5184**.

**Clue N** with 5 factors had to be a prime’s fourth power, but 3^4 is 81 and 7^4 is way bigger than 999, so 5^4 and **625** it is. I *think* I knew being forced to learn all squares up to 25-squared at school would come in useful one day 😉

And **Clue a** had to be a nine digit prime to the tenth power. Now anything to the tenth power gets big very quickly – clearly 10^10 is too long with eleven digits (1 followed by 10 zeroes) and 5^10 is less than a thousandth of that so won’t have enough digits, so Clue a can only be **7^10**. Pencil and paper readily reveals this to be **282475249**. Some of you will have set your own rules for what help you allow yourself here – likely to be somewhere on the [I did it all in my head > pencil & paper > abacus > calculator > spreadsheets > Internet lists > Wolfram > programming] scale. I think I would have struggled without a pencil and paper…

Similarly **Clue A** is a prime^12 and the only one remotely the right size is **5^12** (which must end in 5).

**Clue e** is a prime^6, so with nine digits can only be 23^6, 29^6 or 31^6. A bit of jigsawing with Clue A allows it to be identified as 29^6, i.e. **594823321**.

Other answers where the number of factors was either prime or a product of two primes went in fairly quickly using the above, resulting in most of the central SW to NE entries being solvable. LOI was, if I recall right, clue T, which had to be a multiple of 3^12, i.e. a multiple of 531,441. As it ended in a 1 and needed to be around 1700 to result in a nine-digit number beginning in 9, it was soon clear that it could only be 531,441*1721, again given other jigsawing requirements.

So I finish my checking listening to the dulcet tones of Vivian Stanshall & co. on the Bonzo’s *Gorilla* and Captain Beefheart’s *Safe As Milk*, slightly worried by the quantity of 1967-released material in my music collection (given I was around five at the time).

cheers

Tim / Encota

## Leave a Reply