A036041 - OEIS

A036041

Number of prime divisors, counted with multiplicity, of prime signature A025487(n); equals size of associated partition.

0, 1, 2, 2, 3, 3, 4, 4, 3, 5, 4, 5, 4, 6, 5, 6, 5, 7, 6, 5, 7, 4, 6, 6, 8, 7, 6, 8, 5, 7, 7, 9, 8, 7, 9, 6, 8, 6, 8, 10, 7, 9, 6, 8, 8, 10, 7, 9, 7, 9, 11, 8, 10, 5, 7, 9, 9, 11, 8, 10, 8, 10, 12, 9, 11, 6, 8, 10, 8, 10, 12, 7, 9, 9, 11, 9, 8, 11, 10, 13, 10, 12, 7, 9, 11, 9, 11, 13, 8, 10, 10, 12

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

LINKS

Álvar Ibeas, Table of n, a(n) for n = 1..10000

FORMULA

a(n) = A001222(A025487(n)) = A001222(A181822(n)).

EXAMPLE

a(3) = 2 since A025487(3) = 4 = 2*2; a(5) = 3 since A025487(5) = 8 = 2*2*2; ...

PROG

(Python)

from functools import lru_cache

from itertools import count

from sympy import prime, integer_log, primeomega

from oeis_sequences.OEISsequences import bisection

def A036041(n):

@lru_cache(maxsize=None)

def g(x, m, j): return sum(g(x//(prime(m)**i), m-1, i) for i in range(j, integer_log(x, prime(m))[0]+1)) if m-1 else max(0, x.bit_length()-j)

def f(x):

c, p = n-1+x, 1

for k in count(1):

p *= prime(k)

if p>x:

break

c -= g(x, k, 1)

return c

return primeomega(bisection(f, n, n)) # Chai Wah Wu, Apr 11 2026

CROSSREFS

Cf. A025487, A000041, A035796, A036042, A001222.

Sequence in context: A329907 A329958 A309969 * A252759 A085654 A074719

Adjacent sequences: A036038 A036039 A036040 * A036042 A036043 A036044

KEYWORD

easy,look,nonn

AUTHOR

Alford Arnold

EXTENSIONS

More terms from Henry Bottomley, Apr 30 2001

Edited to accommodate change in A025487's offset by Matthew Vandermast, Nov 08 2008

Definition corrected by Álvar Ibeas, Nov 01 2014

STATUS

approved