# Listen With Others

## L1916: Can You Do Division? by Rhombus

Posted by Encota on 10 March 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