A085089 Number of distinct prime signatures arising up to n.

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

Offset

1,2

Links

Alois P. Heinz, Table of n, a(n) for n = 1..65536

Prog

(PARI) A085089(n)=#Set(apply(t->vecsort(factor(t)[, 2]), [1..n])) \\ Not very efficient for large n > 10^5, but very quick up to the point where stack overflow occurs. - M. F. Hasler, Jul 16 2019
(Python)
from itertools import count
from functools import lru_cache
from sympy import prime, integer_log
def A085089(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)
    c, p = 1, 1
    for k in count(1):
        p *= prime(k)
        if p>n:
            break
        c += g(n, k, 1)
    return c # Chai Wah Wu, Mar 30 2026

Crossrefs

Cf. A025487.

Cf. A025488(n) = a(2^n); A124832 (table of the distinct prime signatures in the order they occur).

Sequence in context: A282711 A035100 A303594 * A228720 A219652 A069924

Adjacent sequences: A085086 A085087 A085088 * A085090 A085091 A085092

Keyword

easy,nonn

Author

Amarnath Murthy and Meenakshi Srikanth (menakan_s(AT)yahoo.com), Jul 02 2003

Extensions

More terms from Ray Chandler, Aug 17 2003

Status

approved