A065557 Solutions k of the equation phi(k) = phi(k-1) + phi(k-2). Also known as Phibonacci numbers.

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, 1876727

Offset: 1

Author

Joseph L. Pe, Nov 28 2001

Keywords

• nonn

Comments

All terms listed here are squarefree. (Thanks to Vladeta Jovovic for this observation.) The first two nonsquarefree terms are 72340252337 and 179115011177. There are 205 terms < 5*10^11. Most early terms are prime but later most terms are composite. - Jud McCranie, Feb 21 2012

There are 233 terms < 10^12. - Jud McCranie, Jan 02 2013

Bagers (1981) named these numbers Phibonacci numbers and asked about the existence of composite terms. According to the solution, P. J. Weinberg found 70 terms below 2*10^8, of which 46 are composite. The existence of an even term was discussed, and if it exists, it exceeds 10^1600. - Amiram Eldar, Mar 01 2020

Examples

			phi(23) = phi(22) + phi(21) (22=10+12), so 23 is in the sequence.
phi(101) = phi(100) + phi(99) (100=40+60), so 101 is in the sequence.
		

References

• A. H. Beiler, Recreations in the Theory of Numbers, Dover Pub., NY, 1966.
• Stanley J. Bezuszka and Margaret Kenney, Number Treasury: A Sourcebook of Problems for Calculators and Computers, Dale Seymour Publications, 1982, pp. 126 and 179.
• Mihai Caragiu, Sequential Experiments with Primes, Springer, 2017, chapter 4, p. 152.
• Jean-Marie De Koninck, Those Fascinating Numbers, American Mathematical Society, 2009, p. 117, entry 1037.
• József Sándor and Borislav Crstici, Handbook of Number Theory II, Kluwer Academic Publishers, 2004, chapter 3, p. 224.

Links

• Jud McCranie, Table of n, a(n) for n = 1..321 (first 85 terms from Harry J. Smith)
• Anders Bagers, Problem E2833, The American Mathematical Monthly, Vol. 87, No. 5 (1980), p. 404, solution, ibid., Vol. 88, No. 8 (1981), p. 622.
• Florian Luca and Pantelimon Stanica, Linear equations with the Euler totient function, Acta Arithmetica, Vol. 128 (2007), pp. 135-147.
• J. L. Pe, On Solutions of phi(n) = phi(n-1) + phi(n-2): A Problem Proposal

Crossrefs

Cf. A000010. A065572 gives nonprime solutions.

Programs

Mathematica

Select[ Range[3, 10^6], EulerPhi[ # ] == EulerPhi[ # - 1] + EulerPhi[ # - 2] & ]

PARI

for(n=3,10^8, if(eulerphi(n)==eulerphi(n-1)+eulerphi(n-2),print1(n,",")))

PARI

{ n=0; e1=eulerphi(2); e2=eulerphi(1); for (m=3, 10^9, e=eulerphi(m); if (e==e2 + e1, write("b065557.txt", n++, " ", m); if (n==100, return)); e2=e1; e1=e ) } \\ Harry J. Smith, Oct 22 2009

Extensions

More terms from Jason Earls, Robert G. Wilson v and Dean Hickerson, Nov 30 2001