At 07:52 PM 12/31/2007, Marc LeBrun wrote:
Plausible programming exercises ... can these be hacked by hand?
They turn out to be quite manageable by hand. If anyone wants to try these, stop reading now; spoilers ahead...
A104628: What 5 integer powers of the golden ratio sum to 2008?
First, write 2008 as a (greedy) sum of Lucas numbers (A000032): 2008 = 1364 + 521 + 123 = L(15) + L(13) + L(10). Using the identity L(n) = phi^n + (-phi)^-n, we have 2008 = phi^15 + phi^13 + phi^10 + phi^-10 - phi^-13 - phi^-15. Now, get rid of the pesky negative terms by repeatedly splitting the smallest positive term (via phi^k = phi^{k-1} + phi^{k-2}): 2008 = phi^15 + phi^13 + phi^10 + phi^-10 - phi^-13 - phi^-15 = phi^15 + phi^13 + phi^10 + phi^-11 + phi^-12 - phi^-13 - phi^-15 = phi^15 + phi^13 + phi^10 + phi^-11 + phi^-14 - phi^-15 = phi^15 + phi^13 + phi^10 + phi^-11 + phi^-16. [There are other solutions, since phi^15 + phi^13 + phi^10 = phi^15 + 2 phi^12 = 2 phi^14 + phi^12, but this is the unique solution as a sum of non-consecutive powers.]
A060667: What's the GCD of the numbers with Euler totient 2008?
Since the totient is multiplicative, if phi(N) = 2008 = 2^3 251, then there must be some prime p dividing N such that phi(p) is divisible by 251 and divides 2^3 251. Thus phi(p) = p - 1 = 2^k 251, for some k from 0 to 3. These values of k yield p = 252, 503, 1005 or 2009, but only 503 is actually a prime (2009 = 7^2 41). Thus N = 503 k, where phi(k) = 4 (and k is coprime to 503, which is actually no further restriction). Since k = 5 and k = 8 work, the GCD of all possible N is 503 (the other possibilities are k = 10 and k = 12). -- Fred W. Helenius fredh@ix.netcom.com