%I #93 Aug 29 2024 11:12:52
%S 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 73,78,79,83,89,97,101,102,103,105,107,109,110,113,114,127,130,131,
%U 137,138,139,149,151,154,157,163,165,167,170,173,174,179,181,182,186,190,191,193
%N Numbers that are the product of an odd number of distinct primes.
%C From _Enrique Pérez Herrero_, Jul 06 2012: (Start)
%C This sequence and A030229 partition the squarefree numbers: A005117.
%C Also solutions to the equation mu(n) = -1.
%C 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 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 The asymptotic density of this sequence is 3/Pi^2 (A104141). - _Amiram Eldar_, May 22 2020
%C 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 B. C. Berndt & R. A. Rankin, Ramanujan: Letters and Commentary, see p. 23; AMS Providence RI 1995.
%D 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 S. Ramanujan, Collected Papers, Ed. G. H. Hardy et al., Cambridge 1927; Chelsea, NY, 1962, p. xxiv, 21.
%H T. D. Noe, <a href="/A030059/b030059.txt">Table of n, a(n) for n = 1..1000</a>
%H 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 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PrimeFactor.html">Prime Factor</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MoebiusFunction.html">Moebius Function</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PrimeSums.html">Prime Sums</a>
%H 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 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 a(n) < n*Pi^2/3 infinitely often; a(n) > n*Pi^2/3 infinitely often. - _Charles R Greathouse IV_, Sep 07 2017
%p a := n -> `if`(numtheory[mobius](n)=-1,n,NULL); seq(a(i),i=1..193); # _Peter Luschny_, May 04 2009
%p # alternative
%p A030059 := proc(n)
%p option remember;
%p local a;
%p if n = 1 then
%p 2;
%p else
%p for a from procname(n-1)+1 do
%p if numtheory[mobius](a) = -1 then
%p return a;
%p end if;
%p end do:
%p end if;
%p end proc: # _R. J. Mathar_, Sep 22 2020
%t Select[Range[300], MoebiusMu[#] == -1 &] (* _Enrique Pérez Herrero_, Jul 06 2012 *)
%o (PARI) is(n)=my(f=factor(n)[,2]); #f%2 && vecmax(f)==1 \\ _Charles R Greathouse IV_, Oct 16 2015
%o (PARI) is(n)=moebius(n)==-1 \\ _Charles R Greathouse IV_, Jan 31 2017
%o (Python)
%o from math import isqrt, prod
%o from sympy import primerange, integer_nthroot, primepi
%o def A030059(n):
%o 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 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 kmin, kmax = 0,1
%o while f(kmax) > kmax:
%o kmax <<= 1
%o while kmax-kmin > 1:
%o kmid = kmax+kmin>>1
%o if f(kmid) <= kmid:
%o kmax = kmid
%o else:
%o kmin = kmid
%o return kmax # _Chai Wah Wu_, Aug 29 2024
%Y Cf. A000040, A001221, A005408, A007304, A008683, A030231, A051270, A123321, A030229, A005117, A088245, A104141.
%K nonn,easy,nice
%O 1,1
%A _N. J. A. Sloane_
%E More terms from _David W. Wilson_