login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #49 Mar 01 2020 04:44:55

%S 3,5,7,11,17,23,37,41,47,101,137,233,257,857,1037,1297,1541,1601,2017,

%T 4337,6527,9179,14401,16097,30497,55387,61133,62801,65537,72581,77617,

%U 110177,152651,179297,244967,299651,603461,619697,686737,1876727

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

%C 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

%C There are 233 terms < 10^12. - _Jud McCranie_, Jan 02 2013

%C 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

%D A. H. Beiler, Recreations in the Theory of Numbers, Dover Pub., NY, 1966.

%D Stanley J. Bezuszka and Margaret Kenney, Number Treasury: A Sourcebook of Problems for Calculators and Computers, Dale Seymour Publications, 1982, pp. 126 and 179.

%D Mihai Caragiu, Sequential Experiments with Primes, Springer, 2017, chapter 4, p. 152.

%D Jean-Marie De Koninck, Those Fascinating Numbers, American Mathematical Society, 2009, p. 117, entry 1037.

%D József Sándor and Borislav Crstici, Handbook of Number Theory II, Kluwer Academic Publishers, 2004, chapter 3, p. 224.

%H Jud McCranie, <a href="/A065557/b065557.txt">Table of n, a(n) for n = 1..321</a> (first 85 terms from Harry J. Smith)

%H Anders Bagers, <a href="https://www.jstor.org/stable/2321224">Problem E2833</a>, The American Mathematical Monthly, Vol. 87, No. 5 (1980), p. 404, <a href="https://www.jstor.org/stable/2320521">solution</a>, ibid., Vol. 88, No. 8 (1981), p. 622.

%H Florian Luca and Pantelimon Stanica, <a href="https://doi.org/10.4064/aa128-2-4">Linear equations with the Euler totient function</a>, Acta Arithmetica, Vol. 128 (2007), pp. 135-147.

%H J. L. Pe, <a href="http://numeratus.net/phibrec/phibrec.html">On Solutions of phi(n) = phi(n-1) + phi(n-2): A Problem Proposal</a>

%e phi(23) = phi(22) + phi(21) (22=10+12), so 23 is in the sequence.

%e phi(101) = phi(100) + phi(99) (100=40+60), so 101 is in the sequence.

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

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

%o (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

%Y Cf. A000010. A065572 gives nonprime solutions.

%K nonn

%O 1,1

%A _Joseph L. Pe_, Nov 28 2001

%E More terms from _Jason Earls_, _Robert G. Wilson v_ and _Dean Hickerson_, Nov 30 2001