A290110 a(n) = the discovery rank of the factorization pattern of the sequence of divisors of n.

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

Offset: 1

Author

Luc Rousseau, Jul 19 2017

Keywords

• nonn

Comments

The definition for the factorization pattern of the sequence of divisors of a number n is the same as in sequence A191743. Let's use the abbreviation FPSD. One can generate a list of distinct FPSD by trying all integers, 1, 2, 3, ..., and ignoring duplicates. a(n) is the index of the FPSD of n in this list.

From Antti Karttunen, Mar 07 & 08 2018: (Start)

This is NOT restricted growth sequence transform of A297174, but instead A300250 is, from which this differs for the first time at n=858, where a(858) = 115, while A300250(858) = 75.

This gives a finer partitioning of natural numbers than A300250, and indeed we have:

For all i, j:

a(i) = a(j) => A300250(i) = A300250(j) => A101296(i) = A101296(j).

(End)

Examples

			The divisors of 17 are {1, 17}. They follow the pattern {1, p} which is pattern number 2 in discovery order. a(17)=2.
The divisors of 28 are {1, 2, 4, 7, 14, 28}. They follow the pattern {1, p, p^2, q, p*q, p^2*q}, which is pattern number 9 in discovery order. a(28)=9.
From _Michael De Vlieger_ and _Antti Karttunen_, Mar 07 & 08 2018: (Start)
Divisors of 462 = 2*3*7*11 (p=2, q=3, r=7, s=11) are 1, 2, 3, 6, 7, 11, 14, 21, 22, 33, 42, 66, 77, 154, 231, 462, thus the factorization patterns in the order of increasing divisors are: 1, p, q, pq, r, s, pr, qr, ps, qs, pqr, pqs, rs, prs, qrs and pqrs.
Divisors of 546 = 2*3*7*13 (p=2, q=3, r=7, s=13) are 1, 2, 3, 6, 7, 13, 14, 21, 26, 39, 42, 78, 91, 182, 273, 546, thus the factorization patterns are 1, p, q, pq, r, s, pr, qr, ps, qs, pqr, pqs, rs, prs, qrs and pqrs, that is, identical with those of 462, thus a(546) = a(462).
Divisors of 858 = 2*3*11*13 (p=2, q=3, r=11, s=13) are 1, 2, 3, 6, 11, 13, 22, 26, 33, 39, 66, 78, 143, 286, 429, 858, thus the factorization patterns are 1, p, q, pq, r, s, pr, ps, qr, qs, pqr, pqs, rs, prs, qrs and pqrs. At the 8th divisor (26), we see that pattern ps is different from pattern qr of the 8th divisor of 546 (21), thus a(858) is not equal to a(546).
(End)
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..65537

Crossrefs

Cf. A191743, A300250.

Programs

Mathematica

FactorizationPattern[n_] := Module[
  {pn, fd, f1, f2, d},
  pn = First /@ FactorInteger[n];
  fd = FactorInteger[ReplacePart[Divisors[n], 1 -> {}]];
  f1 = (ReplacePart[#,
      1 -> FromCharacterCode[
        111 + First[Position[pn, First[#]]]]]) &;
  f2 = (f1 /@ #) &;
  fd = f2 /@ fd;
  f1 = (Power[First[#], Last[#]]) &;
  For[i = 1, i <= Length[fd], i++,
   d = fd[[i]];
   For[j = 1, j <= Length[d], j++,d[[j]] = f1[d[[j]]];];
   d = Product[x, {x, d}];
   fd[[i]] = d;
  ];
  fd
]
ListFactorizationPatternIndices[n_] := Module[
  {mem, k, i, p, a},
  mem = Association[];
  a = {}; k = 0;
  For[i = 1, i \[LessSlantEqual] n, i++,
   p = FactorizationPattern[i];
   If[KeyExistsQ[mem, p],,
    k++;
    mem = Append[mem, p -> k]
   ];
   a = Append[a, mem[p]]
  ];
  a
]
ListFactorizationPatternIndices[80]
(* or *)
f[n_] := If[n==1, 1, Block[{p = First /@ FactorInteger@n, z,x}, z= Table[p[[i]] -> x[i], {i, Length@p}]; Times @@ (((#[[1]] /. z)^#[[2]]) & /@ FactorInteger@ #) & /@ Divisors[n]]]; A = <||>; Table[k = f[n]; If[ KeyExistsQ[A, k], A[k], t = 1 + Length@A; A[k] = t], {n, 80}] (* Giovanni Resta, Jul 20 2017 *)

Formula

A191743(n) = MIN(k such that a(k)=n).

a(p) = 2, for p prime;

a(p^2) = 3, for p prime;

a(p*q) = 4, for p, q distinct primes.

Extensions

More terms from Michael De Vlieger and Antti Karttunen, Mar 07 2018