OFFSET
1,2
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:
(End)
LINKS
Michael De Vlieger, Table of n, a(n) for n = 1..65537
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.
EXAMPLE
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)
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 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Luc Rousseau, Jul 19 2017
EXTENSIONS
More terms from Michael De Vlieger and Antti Karttunen, Mar 07 2018
STATUS
approved