%I #94 Feb 16 2025 08:32:35

%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="https://mathworld.wolfram.com/PrimeFactor.html">Prime Factor</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/MoebiusFunction.html">Moebius Function</a>

%H Eric Weisstein's World of Mathematics, <a href="https://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,changed

%O 1,1

%A _N. J. A. Sloane_

%E More terms from _David W. Wilson_