Listener 4010: Euclid's Algorithm by Aedites

[midazolam]

Here is the link to the numerical listener crossword

[IntoTheBlue]

MartianAlien like you I've worked out that the final digit is a 0 but I've hit a bit of a brick wall.

As far as I can see you can get a valid number if you have one of the following combinations...
2*3*5*7*11*? (? upto 43) or...
2*3*5*11*13*? (? being 17,19 or 23) or...
2*3*5*7*13*? (? being 17,19,23,29 or 33)

I'm assuming that of the 9 combined factors between Y and 17 that they only share 3 and have 3 unique factors each as the clue for Y17 gives fnt.

I'm also assuming that 2 of the common factors must be 2 and 5 as we have the 0 but it's here that I lose the plot...

As far as I can see from the available combinations 4 factors would have to be common to Y and 17 so how does that work ?????

Hats off to everyone who's finished this so far as when it comes to these quarterly mathematical challenges the fog very quickly descends on my brain...

[midazolam]

you are nearly there

3 factors are the same, 3 factors are different. It should be obvious which 3 are the same and which letters they correspond to as a group. I noticed a trend in the grid that made me realise the exact identity of these 3 (after hours and hours of scribbling, dead ends, and worthless spreadsheets)

keep at it

[IntoTheBlue]

Thanks midazolam, I feel that it wouldn't take a lot for me to crack this one even with the fog that rapidly descends when I see a numbers puzzle. (I know exactly where you're coming from with worthless spreadsheets !!)

I've got a hunch that nt are 5 and 2 respectively but I still can't see a combination of 6 factors under 43 that gives 3 unique to Y and 17... I will keep looking !!

[lordbadger]

Would anybody object to me pointing out that n has to be 2?

I�m afraid this so-called �crossword� doesn�t get any more exciting no matter how hard I try to like it. What were its merits exactly? I feel a �Dear Sir� coming on.

Lord 588226111

[jamesah]

After spending an idle hour working out all the factors of the 66 5-digit numbers I am lost in admiration of Aedites. How on earth does he do it? And to arrange things so that the puzzle is actually soluble.I think that these numerical puzzles must be more difficult to devise than proper crosswords.

[Clamzy]

Well Jamesah, I've pondered the same question i.e., how is it done. In a similar idle moment I estimated there are around eight and a half thousand 5 digit integers between 10,000 and 99,000, which have prime factors only. So how to find these 66? I think it must be done by spreadsheets and the like, used by many solvers. I haven't the foggiest idea what they are, and so have to use logic and the well tested trial and error.

[beermagnet]

Integers between 10,000 and 99,999 that have unique prime factors only using those from the first 22 (2 through 79):
I make that 2,875 :
20 with 6 factors
579 with 5
1560 with 4
716 with 3

[Deviant]

OK, I give up. I've managed to make a start three times, working completely separately. I've got between 10 and 16 values before I find a problem. I must be missing something - I was really careful (or at least I thought I was). Each of the 3 answers is almost identical - but D gets me every time!

This is what I hate about the maths Listeners - they're so unforgiving of errors. With a word one, you can still do the rest of the puzzle and then see the error of your ways!

[Clamzy]

Beermagnet
Obviously I was way out in my estimate. I had made a list of some containing 79 and found roughly eight in each block of a thousand, and inferred from this sample there would be 8,000+ - wrong:-)
I would be fascinated to know how you obtained such exact figures.

[perseverer]

Have to agree with most of the comments already made. All the logic and reasoning tended to come early on, but for a large part of the crossword it was just about plodding on. The thing that redeems the puzzle in my view is, as also had been said, admiration for how the setter constructed it.

And for the second week in a row, John Green has hundreds of circular grids to check. Not easy

[Flocko]

What I found most interesting about this puzzle was that most of the time I was just going by the factors that any given entry had to have. In other words I rarely used the fact that we were given the lowest common factor of intersecting answers. Frequently I found that a given entry had only one possibility given its required factors and matching the digits I already had, and so I didn't have to also check that there were not other common factors. And yet I still was able to arrive at a unique solution.

This leads me to wonder whether we were actually (for once) given more information than was needed. We were given common factors between every pair of intersecting answers. Could Aedites have gotten away with just some of those clues, I wonder?

And, by the way, I personally made very extensive use of Excel and other computing tools to solve this, and I'm not too proud to admit to it. I understand that these puzzles are solvable with just pencil and (lots of) paper, but I just don't trust myself to do so without making a dumb error early on.

[cluelessJoe]

Flocko - re your last paragraph, I am in awe of those solvers of year gone by. Some 40 years ago I managed to pass maths and further maths at A level yet I still have to resort sheepishly to spreadsheets to help me through these mathematicals. I gather that way back, there were many more than just 4 per year of the Listener numerics ... and yet this was a time when hand-held calculators were sci-fi material, when a rudimentary computer barely fitted in the back of an articulated lorry. Sure, these puzzles are indeed solvable with pencil and paper .. it would just take 100 times as long. Don't apologise for using a spreadsheet - it can't be any worse than the Chambers Dictionary CD Rom as used by the current holder of the Solvers' Silver Salver to help him crack the verbal crosswords!

[MartianAlien]

Anyone willing to confirm that Y starts with 7 and D 39?
A wall of silence is acceptable.
I've already booked the next available flight home!

[perseverer]

Sorry. By my reckoning, neither is correct.

[jamesah]

My maths is of the same standard as cluelessjoe's but my IT skills are much poorer. I took about 4 hours with pencil, paper and calculator after a very slow start. I wouldn't have a clue how to solve using spreadsheets or Excel (whatever that is).

[IntoTheBlue]

Having been pointed in the right direction by Midazolam and Lord Badger I've finally cracked this one. I totally agree with the comments made above about the 'plodding' element of filling the grid.Once I had reasoned the answers for 17 and Y (having finally found the right combination for the factors that I'd missed on my first couple of passes) it became quite a straight forward process of elimination to match up the factors with the letters before the 'grind' of filling in the rest of the grid.

Keep going MartianAlien, Midazolam is correct when he says you are nearly there when you have answers for Y and 17 set.

Whilst I enjoyed the diversion of a numerical challenge thank heavens we are back to 'normal' tomorrow and I won't have to dust off my excel skills for another 3 months.

IntoThe 674843

[beermagnet]

Clamzy: I wondered same as you so on Monday when I got to work where I have access to a Unix box and more particularly some sophisticated programming tools, I wrote a quick and dirty program that used a sledgehammer approach:
Taking the 22 primes and multiplying every one by every other one where p1<p2<p3 (and so on) for the 3, 4 5 and 6 Factor cases then selecting the results between 10,000 and 99,999. (I only took up to 43 for the 6 factor case cause I knew from previous tinkering at home that no higher prime could be involved there and I was a bit worried about the approx. 22^6 i.e. 100M calcs it would do there - in fact the thing ran in a matter of secs).
Cheers, 23397403493090
Nuhhr, nuhhr! My moniker's the biggest ;-}

[Flocko]

BM: Interesting. I took the opposite approach: factored every number from 10000 to 100000, tossed the primes and any with repeating factors and any with factors > 79 and reported the rest into a spreadsheet. Then I was able to sort by number of factors to isolate those with six factors. Also added a column to separate out last three digits of each number so I could sort by that too, to assist in finding matches. Finally was able to use it to help check everything when I was all done. Some might call this brute force solving but I don't have the time any more to do these things by hand.

[perseverer]

BM, sorry, but you are barred. Your moniker, like mine, has repeated primes.

[Clamzy]

Thanks to Beermagnet and also Flocko for enlightening me on the "how to". Obviously I couldn't have done this (see above). If however I could take an evening school class or something, and learn how to use spreadsheets, would it spoil the enjoyment /sense of achievement I now have, time not being a factor for me?