cp's OEIS Frontend

A030059 Numbers that are the product of an odd number of distinct primes.

%I A030059 #94 Feb 16 2025 08:32:35
%S A030059 2,3,5,7,11,13,17,19,23,29,30,31,37,41,42,43,47,53,59,61,66,67,70,71,
%T A030059 73,78,79,83,89,97,101,102,103,105,107,109,110,113,114,127,130,131,
%U A030059 137,138,139,149,151,154,157,163,165,167,170,173,174,179,181,182,186,190,191,193
%N A030059 Numbers that are the product of an odd number of distinct primes.
%C A030059 From _Enrique Pérez Herrero_, Jul 06 2012: (Start)
%C A030059 This sequence and A030229 partition the squarefree numbers: A005117.
%C A030059 Also solutions to the equation mu(n) = -1.
%C A030059 Sum_{n>=1} 1/a(n)^s = (zeta(s)^2 - zeta(2*s))/(2*zeta(s)*zeta(2*s)). (End) [See A088245 and the Hardy reference. - _Wolfdieter Lang_, Oct 18 2016]
%C A030059 The lexicographically least sequence of integers > 1 such that for each entry, the number of proper divisors occurring in the sequence is equal to 0 modulo 3. - _Masahiko Shin_, Feb 12 2018
%C A030059 The asymptotic density of this sequence is 3/Pi^2 (A104141). - _Amiram Eldar_, May 22 2020
%C A030059 Solutions to the equation Sum_{d|n} mu(d)*sigma(d) = -n, where sigma(n) is the sum of divisors function (A000203). - _Robert D. Rosales_, May 20 2024
%D A030059 B. C. Berndt & R. A. Rankin, Ramanujan: Letters and Commentary, see p. 23; AMS Providence RI 1995.
%D A030059 G. H. Hardy, Ramanujan, AMS Chelsea Publishing, 2002, pp. 64 - 65, (misprint on p. 65, line starting with Hence: it should be ... -1/Zeta(s) not ... -Zeta(s)).
%D A030059 S. Ramanujan, Collected Papers, Ed. G. H. Hardy et al., Cambridge 1927; Chelsea, NY, 1962, p. xxiv, 21.
%H A030059 T. D. Noe, <a href="/A030059/b030059.txt">Table of n, a(n) for n = 1..1000</a>
%H A030059 Debmalya Basak, Nicolas Robles, and Alexandru Zaharescu, <a href="https://arxiv.org/abs/2312.17435">Exponential sums over Möbius convolutions with applications to partitions</a>, arXiv:2312.17435 [math.NT], 2023. Mentions this sequence.
%H A030059 S. Ramanujan, <a href="http://www.imsc.res.in/~rao/ramanujan/CamUnivCpapers/Cpaper4/page1.htm">Irregular numbers</a>, J. Indian Math. Soc. 5 (1913) 105-106.
%H A030059 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PrimeFactor.html">Prime Factor</a>
%H A030059 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/MoebiusFunction.html">Moebius Function</a>
%H A030059 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PrimeSums.html">Prime Sums</a>
%H A030059 H. S. Wilf, <a href="https://www.jstor.org/stable/2323497">A Greeting; and a view of Riemann's Hypothesis</a>, Amer. Math. Monthly, 94:1 (1987), 3-6.
%F A030059 omega(a(n)) = A001221(a(n)) gives A005408. {primes A000040} UNION {sphenic numbers A007304} UNION {numbers that are divisible by exactly 5 different primes A051270} UNION {products of 7 distinct primes (squarefree 7-almost primes) A123321} UNION {products of 9 distinct primes; also n has exactly 9 distinct prime factors and n is squarefree A115343} UNION.... - _Jonathan Vos Post_, Oct 19 2007
%F A030059 a(n) < n*Pi^2/3 infinitely often; a(n) > n*Pi^2/3 infinitely often. - _Charles R Greathouse IV_, Sep 07 2017
%p A030059 a := n -> `if`(numtheory[mobius](n)=-1,n,NULL); seq(a(i),i=1..193); # _Peter Luschny_, May 04 2009
%p A030059 # alternative
%p A030059 A030059 := proc(n)
%p A030059     option remember;
%p A030059     local a;
%p A030059     if n = 1 then
%p A030059         2;
%p A030059     else
%p A030059         for a from procname(n-1)+1 do
%p A030059             if numtheory[mobius](a) = -1 then
%p A030059                 return a;
%p A030059             end if;
%p A030059         end do:
%p A030059     end if;
%p A030059 end proc: # _R. J. Mathar_, Sep 22 2020
%t A030059 Select[Range[300], MoebiusMu[#] == -1 &] (* _Enrique Pérez Herrero_, Jul 06 2012 *)
%o A030059 (PARI) is(n)=my(f=factor(n)[,2]); #f%2 && vecmax(f)==1 \\ _Charles R Greathouse IV_, Oct 16 2015
%o A030059 (PARI) is(n)=moebius(n)==-1 \\ _Charles R Greathouse IV_, Jan 31 2017
%o A030059 (Python)
%o A030059 from math import isqrt, prod
%o A030059 from sympy import primerange, integer_nthroot, primepi
%o A030059 def A030059(n):
%o A030059     def g(x,a,b,c,m): yield from (((d,) for d in enumerate(primerange(b+1,isqrt(x//c)+1),a+1)) if m==2 else (((a2,b2),)+d for a2,b2 in enumerate(primerange(b+1,integer_nthroot(x//c,m)[0]+1),a+1) for d in g(x,a2,b2,c*b2,m-1)))
%o A030059     def f(x): return int(n+x-primepi(x)-sum(sum(primepi(x//prod(c[1] for c in a))-a[-1][0] for a in g(x,0,1,1,i)) for i in range(3,x.bit_length(),2)))
%o A030059     kmin, kmax = 0,1
%o A030059     while f(kmax) > kmax:
%o A030059         kmax <<= 1
%o A030059     while kmax-kmin > 1:
%o A030059         kmid = kmax+kmin>>1
%o A030059         if f(kmid) <= kmid:
%o A030059             kmax = kmid
%o A030059         else:
%o A030059             kmin = kmid
%o A030059     return kmax # _Chai Wah Wu_, Aug 29 2024
%Y A030059 Cf. A000040, A001221, A005408, A007304, A008683, A030231, A051270, A123321, A030229, A005117, A088245, A104141.
%K A030059 nonn,easy,nice
%O A030059 1,1
%A A030059 _N. J. A. Sloane_
%E A030059 More terms from _David W. Wilson_