A395653 - OEIS

%I #15 May 14 2026 23:26:34

%S 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,

%T 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,

%U 18,18,3,1,19,2,19,5,20,2,20,1,21,21,3,6,22,3,22

%N 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.

%C Ordinal transform of A300250.

%C 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.

%C 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.

%e 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.

%o (Python)

%o from sympy import factorint, divisors

%o from collections import Counter

%o seen = Counter()

%o def p_sig(n): return tuple(sorted(factorint(n).values(), reverse=True))

%o def p_prof(n): return tuple(p_sig(d) for d in sorted(divisors(n)))

%o def a(n):

%o     p = p_prof(n)

%o     seen[p] += 1

%o     return seen[p]

%o print([a(n) for n in range(1, 80)])  # _Peter Luschny_, May 11 2026

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

%K nonn,easy

%O 1,3

%A _Marc LeBrun_, May 02 2026