IMPORTANT: Please do not post solutions, hints, or other spoilers until at least 60 hours after the date of this message. Thanks. IMPORTANTE: Por favor, no enviéis soluciones, pistas, o cualquier otra cosa que pueda echar a perder la resolución del problema hasta que hayan pasado por lo menos 60 horas desde el envío de este mensaje. Gracias. IMPORTANT: S'il vous plaît, attendez au minimum 60 heures après la date de ce message avant de poster solutions, indices ou autres révélations. Merci. WICHTIG: Bitte schicken Sie keine Lösungen, Tipps oder Hinweise für diese Aufgabe vor Ablauf von 60 Stunden nach dem Datum dieser Mail. Danke. BELANGRIJK: Stuur aub geen oplossingen, hints of andere tips in de eerste 60 uur na het verzendingstijdstip van dit bericht. Waarvoor dank. VNIMANIE: Pozhalujsta ne shlite reshenija, nameki na reshenija, i voobshe lyubye podskazki v techenie po krajnej mere 60 chasov ot daty etogo soobshenija. Spasibo. Qing3 Zhu4Yi4: Qing3 Ning2 Deng3Dao4 Jie1Dao4 Ben3 Xin4Xi2 Zhi1Hou4 60 Xiao3Shi2, Zai4 Fa1Biao3 Jie3Da2, Ti2Shi4, Huo4 Qi2Ta1 Hui4 Xie4Lou4 Da2An4 De5 Jian4Yi4. Xie4Xie4. ---------------------------------------------------------------- Graham's function (named for Ronald L. Graham, director of research at AT&T Bell Labs) of a positive integer n is computed as follows: Find an increasing sequence of integers a0, a1, ..., a_k such that 1. a0 = n 2. The product of the integers is a perfect square 3. a_k is as small as possible. Then G(n) = a_k. For example, G(2) = 6. Why? It's no larger than 6, because the product of the elements of (2, 3, 6) is a perfect square. No such sequence can end with anything smaller than 6. Clearly it can't end with 3, since then it would have to be (2, 3) and 2*3 is not a perfect square. It can't end with 4, because if the product of (2, ..., 4) were a perfect square, then would be the product of (2, ...) without the 4, and therefore the last element of (2, ..., 4) would not be the smallest such possible. And it can't end with 5 either, because the product of (2, ..., 5) is divisible by 5 but not by 25, and so is not a perfect square. Similarly, G(3) = 8, because of (3, 6, 8). I leave it as an exercise to show that G(8) is no smaller than 8. G(4) is easy; it's just 4, and the sequence is just (4). In general, if n is already a perfect square, then G(n)=n. Here's a partial table of G(n): n G(n) ------------ 1 1 2 6 3 8 4 4 5 10 6 12 7 14 8 15 9 9 10 18 11 22 12 20 ... ... Write a function, 'Graham', which, given a positive integer n, returns G(n).