login
Numbers n such that n and Omega(n) are relatively prime, where Omega(n) is the number of prime divisors of n (with repetition).
3

%I #17 Dec 15 2017 17:35:24

%S 1,2,3,5,7,8,9,11,13,15,17,19,20,21,23,25,28,29,31,32,33,35,37,39,41,

%T 43,44,47,48,49,50,51,52,53,55,57,59,61,65,67,68,69,70,71,72,73,76,77,

%U 79,81,83,85,87,89,91,92,93,95,97,98,101,103,107,108,109,110,111,112

%N Numbers n such that n and Omega(n) are relatively prime, where Omega(n) is the number of prime divisors of n (with repetition).

%C Numbers n such that Omega(n)^phi(n) == 1 (mod n), where Omega(n) is the number of prime divisors of n counted with multiplicity (A001222) and phi(n) is the Euler totient function (A000010). - _Michel Lagneau_, Dec 21 2012

%C Alladi shows that the density of this sequence is 6/Pi^2, that is, a(n) ~ (Pi^2/6)n. - _Charles R Greathouse IV_, Aug 03 2016

%H Harry J. Smith, <a href="/A063743/b063743.txt">Table of n, a(n) for n = 1..1000</a>

%H Krishnaswami Alladi, <a href="http://www.fq.math.ca/Scanned/19-3/alladi.pdf">On the probability that n and Omega(n) are relatively prime</a>, Fibonacci Quarterly 19:3 (1981), pp. 228-232.

%t fQ[n_] := GCD[PrimeOmega[n], n] == 1; Select[Range@115, fQ] (* _Robert G. Wilson v_, Dec 24 2012 *)

%o (PARI) j=[]; for(n=1,300, if(gcd(n,bigomega(n))==1,j=concat(j,n))); j

%o (PARI) n=0; for (m=1, 10^9, if (gcd(m, bigomega(m))==1, write("b063743.txt", n++, " ", m); if (n==1000, break))) \\ _Harry J. Smith_, Aug 29 2009

%Y Cf. A001222, A275616.

%K nonn

%O 1,2

%A _Jason Earls_, Aug 13 2001