On Solutions of phi(n) = phi(n - 1) + phi(n

On Solutions of phi(n) = phi(n - 1) + phi(n - 2)

A Problem Proposal

Recall that Euler's totient function phi(n) is defined as the number of natural numbers less than n and relatively prime to n. In number theory texts, it is shown that if n has prime factorization into distinct primes n = p₁^a....p_k^r, then phi(n) = p₁^a-1(p₁ - 1)....p_k^r-1(p_k - 1).
Consider the equation
phi(n) = phi(n - 1) + phi(n - 2)
(which looks like the recursion in the definition of the Fibonacci sequence). For example, phi(23) = 22 = 10 + 12 = phi(22) + phi(21), and phi(101) = 40 + 60 = phi(100) + phi(99).
This equation determines a sequence a(k) consisting of its solutions n:
3, 5, 7, 11, 17, 23, 37, 41, 47, 101,....
(Note: These appear as sequence A065557 in the Online Encyclopedia of Integer Sequences by N. J. A. Sloane.) That is, a(k) is the k-th solution in increasing order. Observe that the first few terms listed above are all primes.
Problems

Are all the terms of this sequence primes?

Is this sequence infinite?

For more on solving equations involving phi(n), see "Recreations in the Theory of Numbers" by A. Beiler (Dover, 1966).
I invite readers to communicate their solutions or comments by contacting me at the email address below. I will report any progress on these problems in this web page, and of course, acknowledge correct solutions.
Joseph L. Pe
iDEN System Engineering Tools and Statistics
Motorola Center
Schaumburg, IL
email:josephpe@excite.com

Update (30 November 2001)
Vladeta Jovovic notes that n = 1037 is the smallest counterexample to the first conjecture since 1037= 17*61, phi(1037)=16*60=960, 1036=2^2*7*37, phi(1036)=2*6*36=432, 1035=3^2*5*23, phi(1035)=6*4*22=528, 960=432+528. Also, he observes that a(n) could be square-free.
Update (1 December 2001) Jason Earls has calculated a good number of terms of the sequence:
3,5,7,11,17,23,37,41,47,101,137,233,257,857,1037,1297,1541, 1601,2017,4337,6527,9179,14401,16097,30497,55387,61133, 62801,65537,72581,77617,110177,152651,179297,244967,299651, 603461,619697,686737
All terms above are square-free. Prove or disprove: a(k) is always square-free.

You are visitor number