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

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, 43, 44, 47, 48, 49, 50, 51, 52, 53, 55, 57, 59, 61, 65, 67, 68, 69, 70, 71, 72, 73, 76, 77, 79, 81, 83, 85, 87, 89, 91, 92, 93, 95, 97, 98, 101, 103, 107, 108, 109, 110, 111, 112

Offset: 1

Author

Jason Earls, Aug 13 2001

Keywords

• nonn

Comments

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

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

Links

• Harry J. Smith, Table of n, a(n) for n = 1..1000
• Krishnaswami Alladi, On the probability that n and Omega(n) are relatively prime, Fibonacci Quarterly 19:3 (1981), pp. 228-232.

Crossrefs

Cf. A001222, A275616.

Programs

Mathematica

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

PARI

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

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