login
Numbers k such that phi(k) < phi(k - phi(k)).
5

%I #33 Feb 19 2024 01:58:26

%S 30,60,66,120,132,138,174,210,240,246,264,276,318,330,348,420,480,492,

%T 498,510,528,534,552,630,636,660,678,690,696,786,840,870,910,960,984,

%U 996,1020,1038,1056,1068,1074,1104,1122,1146,1260,1272,1320,1330,1356

%N Numbers k such that phi(k) < phi(k - phi(k)).

%C If p is a Sophie Germain prime greater than 3 and n is a natural number then 2^n*3*p is in the sequence. That is because if m = 2^n*3*p then phi(m) = 2^n*(p-1) and phi(m - phi(m)) = phi(2^n*3*p - 2^n*(p-1)) = phi(2^n*(2p+1)) = 2^n*p so phi(m) < phi(m-phi(m)) and m is in the sequence. - _Farideh Firoozbakht_, Jun 19 2005

%C Erdős (1980) proposed the problem to prove that this sequence is infinite and has an asymptotic density 0. Grytczuk et al. (2001) proved that this sequence is infinite with an upper asymptotic density < 0.45637. - _Amiram Eldar_, May 22 2021

%D Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section B42, p. 150.

%D József Sándor, Dragoslav S. Mitrinovic and Borislav Crstici, Handbook of Number Theory I, Springer Science & Business Media, 2005, Chapter III, p. 209.

%H Amiram Eldar, <a href="/A051488/b051488.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..1000 from T. D. Noe)

%H Paul Erdős, <a href="https://books.google.com/books?id=KBD87GWw9mMC&amp;lpg=PA381&amp;pg=PA505">Problem P. 294</a>, Canad. Math. Bull., Vol. 23, No. 4 (1980), p. 505.

%H Aleksander Grytczuk, Florian Luca and Marek Wojtowicz, <a href="https://www.researchgate.net/profile/Marek-Wojtowicz-2/publication/266273753_A_conjecture_of_Erdos_concerning_inequalities_for_the_Euler_totient_function">A conjecture of Erdős concerning inequalities for the Euler totient function</a>, Publ. Math. Debrecen, Vol. 59, No. 1-2, (2001), pp. 9-16.

%t Select[Range[1360], EulerPhi[ # ] < EulerPhi[ # - EulerPhi[ # ]] &] (* _Farideh Firoozbakht_, Jun 19 2005 *)

%o (Haskell)

%o a051488 n = a051488_list !! (n-1)

%o a051488_list = [x | x <- [2..], let t = a000010 x, t < a000010 (x - t)]

%o -- _Reinhard Zumkeller_, Apr 12 2014

%Y Cf. A051487, A005384.

%Y Cf. A000010, A051953.

%K nonn,nice,easy

%O 1,1

%A _R. K. Guy_

%E More terms from _James A. Sellers_