A335097 Number of integers less than n with the same number of prime factors (counted with multiplicity) as n.

0, 0, 1, 0, 2, 1, 3, 0, 2, 3, 4, 1, 5, 4, 5, 0, 6, 2, 7, 3, 6, 7, 8, 1, 8, 9, 4, 5, 9, 6, 10, 0, 10, 11, 12, 2, 11, 13, 14, 3, 12, 7, 13, 8, 9, 15, 14, 1, 16, 10, 17, 11, 15, 4, 18, 5, 19, 20, 16, 6, 17, 21, 12, 0, 22, 13, 18, 14, 23, 15, 19, 2, 20, 24, 16, 17, 25, 18, 21, 3

Offset: 1

Author

Ilya Gutkovskiy, Oct 31 2020

Keywords

• nonn

Examples

			a(10) = 3 because bigomega(10) = 2 and also bigomega(4) = bigomega(6) = bigomega(9) = 2.
		

Links

• Robert Israel, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000079 (positions of 0's), A001222, A047983, A058933, A067004, A322838, A334655.

Programs

Maple

A:= NULL:
for n from 1 to 100 do
  t:= numtheory:-bigomega(n);
  if not assigned(R[t]) then
    A:= A,0;
    R[t]:= 1;
   else
    A:= A, R[t];
    R[t]:= R[t]+1;
   fi
od:
A; # Robert Israel, Oct 24 2021

Mathematica

Table[Length[Select[Range[n - 1], PrimeOmega[#] == PrimeOmega[n] &]], {n, 80}]

PARI

a(n)={my(t=bigomega(n)); sum(k=1, n-1, bigomega(k)==t)} \\ Andrew Howroyd, Oct 31 2020

Python

from math import prod, isqrt
from sympy import isprime, primepi, primerange, integer_nthroot, primeomega
def A335097(n):
    if n==1: return 0
    if isprime(n): return primepi(n)-1
    def g(x,a,b,c,m): yield from (((d,) for d in enumerate(primerange(b,isqrt(x//c)+1),a)) if m==2 else (((a2,b2),)+d for a2,b2 in enumerate(primerange(b,integer_nthroot(x//c,m)[0]+1),a) for d in g(x,a2,b2,c*b2,m-1)))
    return int(sum(primepi(n//prod(c[1] for c in a))-a[-1][0] for a in g(n,0,1,1,primeomega(n)))-1) # Chai Wah Wu, Aug 28 2024

Formula

a(n) = |{j < n : bigomega(j) = bigomega(n)}|.

a(n) = A058933(n) - 1.