A353248 Irregular table, read by rows, where row n is the concatenation of all prime signatures leading to n divisors, in reverse lexicographic order.

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

Offset: 1

Author

M. F. Hasler, Apr 08 2022

Keywords

• nonn
• tabf

Comments

The number-of-divisors function d = A000005 is multiplicative with d(p^e) = e+1. Therefore, a prime signature (e1, e2, ..., eN) which yields a given number of divisors corresponds to a factorization (e1+1)*...*(eN+1) of that number. Following the usual convention, we only consider prime signatures with decreasing exponents (e1 >= e2 >= ... >= eN). Furthermore, we list them in reverse lexicographic order, i.e., largest e1 first, etc.

The sequence starts with row 1 which has length 0 (the only number having only 1 divisor is 1 which has the empty product as prime factorization), so the first term a(1) = 1 is the first element of row 2. Here and thereafter, the first element of row n is easily recognized as the first occurrence of n-1, which is the only element of the row (and therefore followed by n) iff n is prime.

Examples

			Table begins:
row n | prime signatures
   1  | ()
   2  | (1)
   3  | (2)
   4  | (3), (1,1)
   5  | (4)
   6  | (5), (2,1)
   7  | (6)
   8  | (7), (3,1), (1,1,1)
   9  | (8), (2,2)
  10  | (9), (4,1)
  11  | (10)
  12  | (11), (5,1), (3,2), (2,1,1)
		

Crossrefs

Cf. A000005 (d = tau = number-of-divisors function).

Cf. A025487 (products of primorial numbers, representatives of prime signatures), A046523 (representative of prime signature of n), A118914, A212171 and A124010 (prime signature of n), A124832 (prime signatures listed in order of representatives A025487), A080577 (partitions in grad.rev.lex order), A036036 (partitions in rev.lex order).

Programs

PARI

A353248_row(n, M=n)={if(n>1, my(f=factor(n)~, m=f[1,#f], L=List()); fordiv(n, d, n < m*d && break; n > M*d || foreach(self()(d, n/d), S, listput(L,concat(n/d-1,S)))); Vec(L), [[]])}