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

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 30, 31, 37, 41, 42, 43, 47, 53, 59, 61, 66, 67, 70, 71, 73, 78, 79, 83, 89, 97, 101, 102, 103, 105, 107, 109, 110, 113, 114, 127, 130, 131, 137, 138, 139, 149, 151, 154, 157, 163, 165, 167, 170, 173, 174, 179, 181, 182, 186, 190, 191, 193

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

From Enrique Pérez Herrero, Jul 06 2012: (Start)

This sequence and A030229 partition the squarefree numbers: A005117.

Also solutions to the equation mu(n) = -1.

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]

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

The asymptotic density of this sequence is 3/Pi^2 (A104141). - Amiram Eldar, May 22 2020

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

References

• B. C. Berndt & R. A. Rankin, Ramanujan: Letters and Commentary, see p. 23; AMS Providence RI 1995.
• 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)).
• S. Ramanujan, Collected Papers, Ed. G. H. Hardy et al., Cambridge 1927; Chelsea, NY, 1962, p. xxiv, 21.

Links

• T. D. Noe, Table of n, a(n) for n = 1..1000
• Debmalya Basak, Nicolas Robles, and Alexandru Zaharescu, Exponential sums over Möbius convolutions with applications to partitions, arXiv:2312.17435 [math.NT], 2023. Mentions this sequence.
• S. Ramanujan, Irregular numbers, J. Indian Math. Soc. 5 (1913) 105-106.
• Eric Weisstein's World of Mathematics, Prime Factor
• Eric Weisstein's World of Mathematics, Moebius Function
• Eric Weisstein's World of Mathematics, Prime Sums
• H. S. Wilf, A Greeting; and a view of Riemann's Hypothesis, Amer. Math. Monthly, 94:1 (1987), 3-6.

Crossrefs

Cf. A000040, A001221, A005408, A007304, A008683, A030231, A051270, A123321, A030229, A005117, A088245, A104141.

Programs

Maple

a := n -> `if`(numtheory[mobius](n)=-1,n,NULL); seq(a(i),i=1..193); # Peter Luschny, May 04 2009
# alternative
A030059 := proc(n)
    option remember;
    local a;
    if n = 1 then
        2;
    else
        for a from procname(n-1)+1 do
            if numtheory[mobius](a) = -1 then
                return a;
            end if;
        end do:
    end if;
end proc: # R. J. Mathar, Sep 22 2020

Mathematica

Select[Range[300], MoebiusMu[#] == -1 &] (* Enrique Pérez Herrero, Jul 06 2012 *)

PARI

is(n)=my(f=factor(n)[,2]); #f%2 && vecmax(f)==1 \\ Charles R Greathouse IV, Oct 16 2015

PARI

is(n)=moebius(n)==-1 \\ Charles R Greathouse IV, Jan 31 2017

Python

from math import isqrt, prod
from sympy import primerange, integer_nthroot, primepi
def A030059(n):
    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)))
    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)))
    kmin, kmax = 0,1
    while f(kmax) > kmax:
        kmax <<= 1
    while kmax-kmin > 1:
        kmid = kmax+kmin>>1
        if f(kmid) <= kmid:
            kmax = kmid
        else:
            kmin = kmid
    return kmax # Chai Wah Wu, Aug 29 2024

Formula

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

a(n) < n*Pi^2/3 infinitely often; a(n) > n*Pi^2/3 infinitely often. - Charles R Greathouse IV, Sep 07 2017

Extensions

More terms from David W. Wilson