A110179 - OEIS

%I #11 Nov 05 2024 19:05:41

%S 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,

%T 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,

%U 68,9,16,29,118,4,82,15,10,21,32,9,94,17,20,34,142,32,112,17,48,15,66,26

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

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

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

%H Donovan Johnson, <a href="/A110179/b110179.txt">Table of n, a(n) for n = 1..10000</a>

%H Max Alekseyev, <a href="https://oeis.org/wiki/User:Max_Alekseyev/gpscripts">PARI/GP Scripts for Miscellaneous Math Problems</a> (invphi.gp).

%H Andrzej Makowski, <a href="https://www.e-periodica.ch/digbib/view?pid=edm-001%3A1974%3A29%3A%3A7#19">On the equation phi(n+k)=2*phi(n)</a>, Elem. Math., Vol. 29, No. 1 (1974), p. 13.

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

%o (PARI) a(n) = vecmin(select(x -> x > n, invphi(2*eulerphi(n)))) - n; \\ _Amiram Eldar_, Nov 05 2024, using _Max Alekseyev_'s invphi.gp

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

%K nonn

%O 1,1

%A _T. D. Noe_, Jul 15 2005