## Euclid’s Algorithm by Aedites

### Detailed Solution

The first step is to use the clues to construct a table of known factors for each entry, as below.

EntryFactorsEntryFactors EntryFactorsEntryFactors EntryFactors
A k N alm 1 fnuw 15 rv 29 fnt
B km O fgt 2 lnu 16 flr 30 bfnt
C P eu 3 bkn 17 fkntuw 31 gkntw
D af Q krw 4 fn 18 fknt 32 nst
E acft R akvw 5 abf 19 aknt 33 aer
F bltw S denr 6 kl 20 flnt 34 efl
G alns T fkntu 7 kp 21 uw 35 bl
H abn U bfu 8 flmr 22 dhl 36 bfr
I fhlnu V bdlw 9 akrt 23 aflm 37 eftu
J fp W akru 10 btw 24 38 hlrt
K flt X ckns 11 bdlt 25 cdt 39 brtw
L afnw Y aflnrt 12 alt 26 afkrt 40 ahlt
M ah Z alrtw 13 afr 27 bet
14 a 28 glt

 (1) This shows that Y and ‘17’ both have six factors, with only three factors in common. Of the 20 possible numbers with six factors, there are three possible pairs:    67830 = 2.3.5.7.17.19 and 98670 = 2.3.5.11.13.23,    82110 = 2.3.5.7.17.23 and 81510 = 2.3.5.11.13.19,    91770 = 2.3.5.7.19.23 and 72930 = 2.3.5.11.13.17. Hence (f,n,t) = (2,3,5). Looking at the common factors in Y1 to Y20, if 2 appears in one of a set of four, it must appear in the other three, since the ending is even; a similar argument holds for 5. Hence f = 3. The digits of Y are divisible by n in the pattern nxxxn and by t in the pattern xxtxt; none of the numbers above starts with 5, so n = 2 and t = 5, giving Y = 81510 and ‘17’= 82110, with (k,u,w) = (7,17,23) and (a,l,r) = (11,13,19). T and (‘29–32’) end in 0, and E, F, K, O and (‘25’–‘28’), (‘29’–‘32’) and (‘37’–‘40’) in 0 or 5. E and F are in the outer ring and must end in 5. O intersects (‘29’–‘32’) which are even but does not contain the factor n, hence O is odd, ending in 5. Similarly ‘28’ intersects S and must end in 5. f = 3n = 2t = 5 (2) Z = alrtw = 13585w implies w = 7 and Z = 95095. Hence (k,u) = (17,23). w = 7 (3) W contains no small factors, so W = akru = 391ar with second digit 1; hence W = 81719 with l = 13 and (a,r) = (11,19). l = 13 (4) ‘16’ has factors f,r,l and ends in 81. There are few sets of five factors, not including 2, that are in range and none ends 81. Hence it is equal to 3.11.13.z or 3.13.19.z where z is a prime between 29 and 79. The only possibility is 3.13.19.41, so ‘16’ = 30381; hence r = 19 and a = 11. a = 11r = 19 (5) ‘23’ has factors a,f,l,m and is not divisible by n,t. Hence ‘23’ = 429m and the only possibility ending in 99 is ‘23’ = 13299 with m = 31 implying ‘8’ = 22971. L has factors a,f,n,w and is not divisible by k,l,t,u, so L = 462z with z a prime between 29 and 79; hence L = 32802. m = 31 (6) R has factors a,k,v,w, is not divisible by 2, 3 or 5 and ends in 31. Hence R = 7.11.17.v or R = 7.11.23.v with v a prime between 29 and 79. The only possibility is R = 77231 with k = 17 and v = 59. Hence u = 23. Then T = 11730, ‘26’ = 53295 and ‘9’ = 17765 since no other factors are possible in either case. ‘15’ ends in 8381 and is divisible by 19 and 59; hence ‘15’ = 68381. k = 17v = 59u = 23 (7) ‘31’ = 1190g and is not divisible by 3 or 7. The first digit is 5 implying g = 43 and ‘31’ = 51170. g = 43 (8) ‘13’ has the pattern x32x1. There are few sets of five factors, not including 2 and 5, that are in range and none has this format. Hence it is 627z, z a prime between 29 and 79. The only possibility is ‘13’ = 33231. ‘14’ is divisible by 11, so ‘14’ = 22231. (9) ‘37’ is odd and divisible by e,f,t,u and not by a,l,r,w. Hence it has four factors and is 345e with e between 29 and 79. The only possibilities with the third digit zero are 3.5.23.29 = 10005 and 3.5.23.61 = 21045. P is not visible by 5 since P37 is eu; hence ‘37’ = 21045 and e = 61. ‘38’ is odd with factors h,l,t,r. The only five digit possibility is 3.5.13.19.23 = 85215; hence ‘38’ = 1235h, so h = 47 and ‘38’= 58045 and I = 84318. ‘40’is odd with actors a,h,l,t, so ‘40’ = 33605. ‘39’ ends in 4605 and is divisible by 19, hence ‘39’ = 24605 and b = 37. H is divisible by 11, so H = 25234. F has factors b,l,t,w and is not divisible by 3 (it intersects ‘29’ and ‘30’); hence F = 16835 and ‘27’ = 11285. e = 61h = 47b = 37 (10) V has factors b,d,l,w and d is at least 29. Hence V = 7.13.29.37, so V = 97643 and d = 29. Hence S = 67222 and ‘11’ = 69745. ‘22’ has factors d,h,l and ends in 719. Hence ‘22’ = 13.29.47, so ‘22’ = 17719. Also N is 7.4433, so N = 30131. d = 29 (11) E begins with 11 and has factors a,c,f,t. Hence it has four factors and c = 67 or 71. The former gives E = 11055 (impossible on the rim) so c = 71 and E = 11715, and ‘25’ = 10295. c = 71 (12) X has factors c,k,n,s and starts with 98. Hence s = 41 and X = 98974. s = 41 (13) ‘1’ is 41xx8 and is divisible by 2,3,7,23; hence ‘1’ = 41538. Q has factors k,r,w and starts 65, hence Q = 65569. U is x403x and has factors b,f,u; hence U = 74037. (14) ‘7’ has factors k,p, where p is 53, 67, 73 or 79; so ‘7’ is divisible by 901, 1139, 1241 or 1343, so the other factor must be x1, x9, x1 or x7 respectively. We find that 63971 = 71.901. Hence p = 53 and ‘7’ = 63971. p = 53 (15) We have now recovered all the primes, and completed all three inner rings and nearly 60% of the outer two rings. Completion of the remainder is straightforward.