cp's OEIS Frontend

A341749 Numbers k such that gcd(k, phi(k)) > log(log(k)).

%I A341749 #20 Feb 20 2021 04:27:58
%S A341749 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,20,21,22,24,25,26,27,28,30,
%T A341749 32,34,36,38,39,40,42,44,45,46,48,49,50,52,54,55,56,57,58,60,62,63,64,
%U A341749 66,68,70,72,74,75,76,78,80,81,82,84,86,88,90,92,93,94,96
%N A341749 Numbers k such that gcd(k, phi(k)) > log(log(k)).
%C A341749 First differs from A080197 at n = 28.
%C A341749 Erdős et al. (2008) proved that the asymptotic density of numbers k such that gcd(k, phi(k)) > (log(log(k)))^u for a real number u > 0 is equal to exp(-gamma) * Integral_{t=u..oo} rho(t) dt, where rho(t) is the Dickman-de Bruijn function and gamma is Euler's constant (A001620). For this sequence u = 1, and therefore its asymptotic density is 1 - exp(-gamma) = 0.43854... (A227242).
%C A341749 There are only 8 cyclic numbers (A003277) in this sequence: 1, 2, 3, 5, 7, 11, 13, 15. All the other terms are in A060679. The first term of A060679 which is not in this sequence is 1622.
%H A341749 Amiram Eldar, <a href="/A341749/b341749.txt">Table of n, a(n) for n = 1..10000</a>
%H A341749 Paul Erdős, Florian Luca and Carl Pomerance, <a href="http://www.math.dartmouth.edu/~carlp/PDF/gcdnphin14.pdf">On the proportion of numbers coprime to a given integer</a>, in: J.-M. De Koninck, A. Granville and F. Luca (eds.), Anatomy of Integers, AMS, 2008, pp. 47-64.
%H A341749 Wikipedia, <a href="https://en.wikipedia.org/wiki/Dickman_function">Dickman function</a>.
%e A341749 16 is a term since gcd(16, phi(16)) = gcd(16, 8) = 8 > log(log(16)) = 1.0197...
%e A341749 17 is not a term since gcd(17, phi(17)) = gcd(17, 16) = 1 < log(log(17)) = 1.0414...
%t A341749 Select[Range[100], GCD[#, EulerPhi[#]] > Log[Log[#]] &]
%o A341749 (PARI) isok(k) = (k==1) || (gcd(k, eulerphi(k)) > log(log(k))); \\ _Michel Marcus_, Feb 19 2021
%Y A341749 Cf. A000010, A001620, A003277, A009195, A060679, A080130, A227242, A341750.
%K A341749 nonn
%O A341749 1,2
%A A341749 _Amiram Eldar_, Feb 18 2021