cp's OEIS Frontend

A030229 Numbers that are the product of an even number of distinct primes.

%I A030229 #120 Jul 22 2025 18:20:43
%S A030229 1,6,10,14,15,21,22,26,33,34,35,38,39,46,51,55,57,58,62,65,69,74,77,
%T A030229 82,85,86,87,91,93,94,95,106,111,115,118,119,122,123,129,133,134,141,
%U A030229 142,143,145,146,155,158,159,161,166,177,178,183,185,187,194,201,202,203,205,206,209,210,213,214
%N A030229 Numbers that are the product of an even number of distinct primes.
%C A030229 These are the positive integers k with moebius(k) = 1 (cf. A008683). - _N. J. A. Sloane_, May 18 2021
%C A030229 From _Enrique Pérez Herrero_, Jul 06 2012: (Start)
%C A030229 This sequence and A030059 form a partition of the squarefree numbers set: A005117.
%C A030229 Also solutions to equation mu(n)=1.
%C A030229 Sum_{n>=1} 1/a(n)^s = (Zeta(s)^2 + Zeta(2*s))/(2*Zeta(s)*Zeta(2*s)).
%C A030229 (End)
%C A030229 A008683(a(n)) = 1; a(A220969(n)) mod 2 = 0; a(A220968(n)) mod 2 = 1. - _Reinhard Zumkeller_, Dec 27 2012
%C A030229 Characteristic function for values of a(n) = (mu(n)+1)! - 1, where mu(n) is the Mobius function (A008683). - _Wesley Ivan Hurt_, Oct 11 2013
%C A030229 Conjecture: For the matrix M(i,j) = 1 if j|i and 0 otherwise, Inverse(M)(a,1) = -1, for any a in this sequence. - _Benedict W. J. Irwin_, Jul 26 2016
%C A030229 Solutions to the equation Sum_{d|n} mu(d)*d = Sum_{d|n} mu(n/d)*d. - _Torlach Rush_, Jan 13 2018
%C A030229 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
%C A030229 From _Peter Munn_, Oct 04 2019: (Start)
%C A030229 Numbers n such that omega(n) = bigomega(n) = 2*k for some integer k.
%C A030229 The squarefree numbers in A000379.
%C A030229 The squarefree numbers in A028260.
%C A030229 This sequence is closed with respect to the commutative binary operation A059897(.,.), thus it forms a subgroup of the positive integers under A059897(.,.). A006094 lists a minimal set of generators for this subgroup. The lexicographically earliest ordered minimal set of generators is A100484 with its initial 4 removed.
%C A030229 (End)
%C A030229 The asymptotic density of this sequence is 3/Pi^2 (cf. A104141). - _Amiram Eldar_, May 22 2020
%D A030229 B. C. Berndt and R. A. Rankin, Ramanujan: Letters and Commentary, see p. 23; AMS Providence RI 1995
%D A030229 S. Ramanujan, Collected Papers, pp. xxiv, 21.
%H A030229 T. D. Noe, <a href="/A030229/b030229.txt">Table of n, a(n) for n = 1..1000</a>
%H A030229 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 A030229 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 A030229 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PrimeFactor.html">Prime Factor</a>
%H A030229 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/MoebiusFunction.html">Moebius Function</a>
%H A030229 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PrimeSums.html">Prime Sums</a>
%H A030229 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 A030229 a(n) < n*Pi^2/3 infinitely often; a(n) > n*Pi^2/3 infinitely often. - _Charles R Greathouse IV_, Oct 04 2011; corrected Sep 07 2017
%F A030229 {a(n)} = {m : m = A059897(A030059(k), p), k >= 1} for prime p, where {a(n)} denotes the set of integers in the sequence. - _Peter Munn_, Oct 04 2019
%e A030229 (empty product), 2*3, 2*5, 2*7, 3*5, 3*7, 2*11, 2*13, 3*11, 2*17, 5*7, 2*19, 3*13, 2*23,...
%p A030229 a := n -> `if`(numtheory[mobius](n)=1,n,NULL); seq(a(i),i=1..214); # _Peter Luschny_, May 04 2009
%p A030229 with(numtheory); t := [ ]: f := [ ]: for n from 1 to 250 do if mobius(n) = 1 then t := [ op(t), n ] else f := [ op(f), n ]; fi; od: t; # _Wesley Ivan Hurt_, Oct 11 2013
%p A030229 # alternative
%p A030229 A030229 := proc(n)
%p A030229     option remember;
%p A030229     local a;
%p A030229     if n = 1 then
%p A030229         1;
%p A030229     else
%p A030229         for a from procname(n-1)+1 do
%p A030229             if numtheory[mobius](a) = 1 then
%p A030229                 return a;
%p A030229             end if;
%p A030229         end do:
%p A030229     end if;
%p A030229 end proc:
%p A030229 seq(A030229(n),n=1..40) ; # _R. J. Mathar_, Sep 22 2020
%t A030229 Select[Range[214], MoebiusMu[#] == 1 &] (* _Jean-François Alcover_, Oct 04 2011 *)
%o A030229 (PARI) isA030229(n)= #(n=factor(n)[,2]) % 2 == 0 && (!n || vecmax(n)==1 )
%o A030229 (PARI) is(n)=moebius(n)==1 \\ _Charles R Greathouse IV_, Jan 31 2017
%o A030229 for(n=1,500, isA030229(n)&print1(n",")) \\ _M. F. Hasler_
%o A030229 (Haskell)
%o A030229 import Data.List (elemIndices)
%o A030229 a030229 n = a030229_list !! (n-1)
%o A030229 a030229_list = map (+ 1) $ elemIndices 1 a008683_list
%o A030229 -- _Reinhard Zumkeller_, Dec 27 2012
%o A030229 (Python)
%o A030229 from math import isqrt, prod
%o A030229 from sympy import primerange, integer_nthroot, primepi
%o A030229 def A030229(n):
%o A030229     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 A030229     def f(x): return int(n-1+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(2,x.bit_length(),2)))
%o A030229     kmin, kmax = 0,1
%o A030229     while f(kmax) > kmax:
%o A030229         kmax <<= 1
%o A030229     while kmax-kmin > 1:
%o A030229         kmid = kmax+kmin>>1
%o A030229         if f(kmid) <= kmid:
%o A030229             kmax = kmid
%o A030229         else:
%o A030229             kmin = kmid
%o A030229     return kmax # _Chai Wah Wu_, Aug 29 2024
%Y A030229 A006881, A046386, A067885, A123322, A281222 are subsequences.
%Y A030229 Cf. A000379, A005117, A008683, A028260, A030059, A104141, A151797, A245630.
%K A030229 nonn,easy,nice
%O A030229 1,2
%A A030229 _David W. Wilson_