A110179 Least k such that phi(n+k) = 2*phi(n), where phi is Euler's totient function.

2, 1, 2, 1, 10, 2, 6, 7, 4, 5, 14, 3, 22, 7, 2, 1, 34, 3, 18, 12, 14, 3, 46, 8, 16, 9, 10, 7, 58, 2, 30, 19, 8, 17, 30, 3, 36, 19, 26, 11, 82, 3, 86, 11, 20, 23, 94, 3, 80, 5, 34, 13, 106, 3, 68, 9, 16, 29, 118, 4, 82, 15, 10, 21, 32, 9, 94, 17, 20, 34, 142, 32, 112, 17, 48, 15, 66, 26

Offset: 1

Author

T. D. Noe, Jul 15 2005

Keywords

• nonn

Comments

Makowski shows that a k exists for each n. It appears that k <= 2n. For prime n, it appears that n-1 <= k <= 2n.

References

• Richard K. Guy, Unsolved Problems in Number Theory, 3rd Ed., New York, Springer-Verlag, 2004, Section B36, p. 138.

Links

• Donovan Johnson, Table of n, a(n) for n = 1..10000
• Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
• Andrzej Makowski, On the equation phi(n+k)=2*phi(n), Elem. Math., Vol. 29, No. 1 (1974), p. 13.

Crossrefs

Cf. A000010, A050473 (least k such that phi(n+k) = 2*phi(k)).

Programs

Mathematica

Table[k=1; e=EulerPhi[n]; While[EulerPhi[n+k] != 2e, k++ ]; k, {n, 100}]

PARI

a(n) = vecmin(select(x -> x > n, invphi(2*eulerphi(n)))) - n; \\ Amiram Eldar, Nov 05 2024, using Max Alekseyev's invphi.gp