A395653 a(n) is the number of positive integers k <= n whose divisors, listed in increasing order, have the same sequence of prime signatures as the divisors of n.

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

Offset

1,3

Comments

Ordinal transform of A300250.

Equivalently, a(n) counts the positive integers k <= n such that, listing the divisors of k and of n in size order, the i-th divisor of k has the same prime signature as the i-th divisor of n for all i.

Refines A335286: A335286 is the ordinal transform of A101296 (which classifies n by its prime signature alone), while this sequence is the ordinal transform of A300250 (which classifies n by the entire sequence of prime signatures of its divisors in size order). The two sequences first differ at n = 20: 12 and 20 share prime signature [2,1], but the divisors of 12 begin 1, 2, 3, 4, ... while those of 20 begin 1, 2, 4, 5, ... -- so the third divisor of 12 is a prime while the third divisor of 20 is a prime square, placing them in different A300250-classes.

Links

Table of n, a(n) for n=1..79.

Example

a(20) = 1 because the divisors of 20 in increasing order are 1, 2, 4, 5, 10, 20 with prime signatures (), [1], [2], [1], [1,1], [2,1], and no smaller positive integer has divisors with this sequence of prime signatures.

Prog

(Python)
from sympy import factorint, divisors
from collections import Counter
seen = Counter()
def p_sig(n): return tuple(sorted(factorint(n).values(), reverse=True))
def p_prof(n): return tuple(p_sig(d) for d in sorted(divisors(n)))
def a(n):
    p = p_prof(n)
    seen[p] += 1
    return seen[p]
print([a(n) for n in range(1, 80)])  # Peter Luschny, May 11 2026

Crossrefs

Cf. A046523, A101296, A290110, A297174, A300250, A335286.

Sequence in context: A363943 A241919 A286469 * A335286 A064839 A347103

Adjacent sequences: A395649 A395650 A395652 * A395654 A395655 A395656

Keyword

nonn,easy

Author

Marc LeBrun, May 02 2026

Status

approved