# [seqfan] A problem of ordering

hv at crypt.org hv at crypt.org
Sun Nov 30 17:12:24 CET 2008

```1. The problem

Back in August, David Wilson introduced the problem:
> Let p1 < p2 < ... < p_n be primes (call p1 = p, p2 = q, p3 = r, ...)
>
> Consider the set M of divisors of p1*p2*...*p_n. How many ways can M be
> ordered?
>
> For n = 0, we have m = { 1 }, with 1 ordering.
>
> For n = 1, we have M = { 1, p }. There is 1 possible ordering, 1 < p.
>
> For n = 2, we have M = { 1, p, q, pq }. Remembering p < q, there is again 1
> possible ordering, 1 < p < q < pq.
>
> For n = 3, we have M = { 1, p, q, r, pq, pr, qr, pqr }. There are 2 possible
> orderings here
>
> 1 < p < q < r < pq < pr < qr < pqr
> 1 < p < q < pq < r < pr < qr < pqr
>
> How many possible orderings are there for larger n?

I extended this to allow prime factors to appear more than once: letting
M = { m_1, m_2, ... m_k } be a multiset of positive integers, I define
f(M) as the number of ways the factors of x = p_1^m_1 . p_2^m_2 ... p_k^m_k
can be ordered, where the p_i are distinct primes.

Note that this assumes the p_i can be distinguished, but in fact when
m_i = m_j no such distinction is possible; a more natural function then
is g(M) which requires p_i < p_j whenever i < j and m_i = m_j. Though
it is useful to record both f() and g(), it turns out that f() is more
amenable.

2. Mathematical results

When |M| = 0 or |M| = 1, f(M) = 1.
When |M| = 2, f(M) = 1 + A135646(m_1, m_2), where A135646 is the "2-D phi"
discussed in my recent message.
When M = { 1, 1, k }, f(M) = A002939(k+1) = (2k + 1)(2k + 2).

David's original problem asks for g(M) with the n-element multiset
{ 1, 1, ... 1 }, and results up to n=6 indicate that this is identical
to A009997(n), "Number of comparative probability orderings on all
subsets of n elements that can arise by assigning a probability
distribution to the individual elements".

I can prove the identities for |M| <= 2, the rest are merely observations.

3. Computational results

I grouped the calculations by t = tau(x), and for each t calculated the
g(M) for each multiset that yielded that t; the program for this is
currently working on tau(x) = 80, and probably won't get beyond tau(x) = 84:
for 1 <= t < 72 it took less than a day (almost all of it at t=64), but
t=72 took over 10 days. These results appear at the bottom of this email.

I confirmed my results by calculating the least representative x for each
ordering; I've run that up to tau(x) = 48, and could realistically go up
to around tau(x) = 60.

4. Sequences

A couple of obvious sequences, beyond the one originally suggested by David,
are a) a(n) = sum f(M) (or g(M)) over each M that yields tau(x) = n; b)
the set of integers that are "least representatives" for any ordering (which
must necessarily be a superset of A025487).

I'd also like to represent f(M) and g(M) themselves as sequences, but I don't
know if there is a canonical way to order the multisets of positive integers,
and an arbitrary order would leave them impossible to find back.

I'm also dubious about how each of these sequences can be satisfactorily
described in the traditionally terse structure of an OEIS sequence.

I'm sure other sequences of interest could be extracted from the raw
results, I'm open to further suggestions.

5. Computation

The ordering was built up recursively in order from least to greatest
factor; as each new factor f_{i+1} was allowed for, I recorded the
constraint f_{i+1} > f_i, and cascaded the effects down to smaller
numbers of free variables by locating linear combinations with previously
recorded constraints that would simplify away the higher order variables;
constraints in only the first two variables were treated as an assertion
about the minimum or maximum permitted value of the log of the ratio
p_1 / p_2.

Optimisation: 1) taking advantage of the symmetry of any ordering
to consider only the first floor((t+1)/2) factors; 2) asserting the
initial set of constraints p_i < p_j whenever i < j and m_i = m_j
so as to calculate g(M) rather than f(M); 3) returning immediately
when the resolved ratio p_1/p_2 had no possible value; 4) ignoring
newly discovered constraints (direct or derived) that were identical
to or weaker than already established constraints (thus restricting
the explosion in the number of cascaded constraints to merely exponential).

Finetuning might have squeezed a bit more out of the code, but I found
that my profiling was giving very inconsistent results; later a colleague
explained that recent optimisations in the Linux kernel meant the clock
tick I was relying on for timings would only "fire when needed", making
it completely useless for my purposes; I have not yet discovered how to
get useful timings on a modern kernel.

6. Calculated values

t  g(M)  f(M)  M
-----------------
1  1     1     <>
2  1     1     <1>
3  1     1     <2>
4  1     1     <3>
1     2     <1,1>
5  1     1     <4>
6  1     1     <5>
3     3     <1,2>
7  1     1     <6>
8  1     1     <7>
4     4     <1,3>
2     12    <1,1,1>
9  1     1     <8>
2     4     <2,2>
10 1     1     <9>
5     5     <1,4>
11 1     1     <10>
12 1     1     <11>
6     6     <1,5>
15    30    <1,1,2>
6     6     <2,3>
13 1     1     <12>
14 1     1     <13>
7     7     <1,6>
15 1     1     <14>
7     7     <2,4>
16 1     1     <15>
8     8     <1,7>
28    56    <1,1,3>
14    336   <1,1,1,1>
4     8     <3,3>
17 1     1     <16>
18 1     1     <17>
9     9     <1,8>
36    72    <1,2,2>
9     9     <2,5>
19 1     1     <18>
20 1     1     <19>
10    10    <1,9>
45    90    <1,1,4>
10    10    <3,4>
21 1     1     <20>
10    10    <2,6>
22 1     1     <21>
11    11    <1,10>
23 1     1     <22>
24 1     1     <23>
12    12    <1,11>
66    132   <1,1,5>
246   1476  <1,1,1,2>
145   145   <1,2,3>
12    12    <2,7>
13    13    <3,5>
25 1     1     <24>
6     12    <4,4>
26 1     1     <25>
13    13    <1,12>
27 1     1     <26>
13    13    <2,8>
26    156   <2,2,2>
28 1     1     <27>
14    14    <1,13>
91    182   <1,1,6>
14    14    <3,6>
29 1     1     <28>
30 1     1     <29>
15    15    <1,14>
227   227   <1,2,4>
15    15    <2,9>
16    16    <4,5>
31 1     1     <30>
32 1     1     <31>
16    16    <1,15>
120   240   <1,1,7>
656   3936  <1,1,1,3>
516   61920 <1,1,1,1,1>
137   274   <1,3,3>
17    17    <3,7>
33 1     1     <32>
16    16    <2,10>
34 1     1     <33>
17    17    <1,16>
35 1     1     <34>
17    17    <4,6>
36 1     1     <35>
18    18    <1,17>
153   306   <1,1,8>
1616  6464  <1,1,2,2>
346   346   <1,2,5>
18    18    <2,11>
173   346   <2,2,3>
19    19    <3,8>
10    20    <5,5>
37 1     1     <36>
38 1     1     <37>
19    19    <1,18>
39 1     1     <38>
19    19    <2,12>
40 1     1     <39>
20    20    <1,19>
190   380   <1,1,9>
1371  8226  <1,1,1,4>
448   448   <1,3,4>
21    21    <3,9>
21    21    <4,7>
41 1     1     <40>
42 1     1     <41>
21    21    <1,20>
467   467   <1,2,6>
21    21    <2,13>
22    22    <5,6>
43 1     1     <42>
44 1     1     <43>
22    22    <1,21>
231   462   <1,1,10>
23    23    <3,10>
45 1     1     <44>
22    22    <2,14>
256   512   <2,2,4>
23    23    <4,8>
46 1     1     <45>
23    23    <1,22>
47 1     1     <46>
48 1     1     <47>
24    24    <1,23>
276   552   <1,1,11>
2475  14850 <1,1,1,5>
19944 478656 <1,1,1,1,2>
8953  17906 <1,1,2,3>
633   633   <1,2,7>
686   686   <1,3,5>
24    24    <2,15>
359   718   <2,3,3>
26    26    <3,11>
27    27    <5,7>
49 1     1     <48>
12    24    <6,6>
50 1     1     <49>
25    25    <1,24>
359   718   <1,4,4>
26    26    <4,9>
51 1     1     <50>
25    25    <2,16>
52 1     1     <51>
26    26    <1,25>
325   650   <1,1,12>
27    27    <3,12>
53 1     1     <52>
54 1     1     <53>
27    27    <1,26>
793   793   <1,2,8>
4522  27132 <1,2,2,2>
27    27    <2,17>
412   824   <2,2,5>
30    30    <5,8>
55 1     1     <54>
28    28    <4,10>
56 1     1     <55>
28    28    <1,27>
378   756   <1,1,13>
4052  24312 <1,1,1,6>
913   913   <1,3,6>
30    30    <3,13>
30    30    <6,7>
57 1     1     <56>
28    28    <2,18>
58 1     1     <57>
29    29    <1,28>
59 1     1     <58>
60 1     1     <59>
30    30    <1,29>
435   870   <1,1,14>
18613 37226 <1,1,2,4>
1005  1005  <1,2,9>
1112  1112  <1,4,5>
30    30    <2,19>
1114  1114  <2,3,4>
32    32    <3,14>
32    32    <4,11>
34    34    <5,9>
61 1     1     <60>
62 1     1     <61>
31    31    <1,30>
63 1     1     <62>
31    31    <2,20>
536   1072  <2,2,6>
33    33    <6,8>
64 1     1     <63>
32    32    <1,31>
496   992   <1,1,15>
6187  37122 <1,1,1,7>
76008 1824192 <1,1,1,1,3>
124187 89414640 <1,1,1,1,1,1>
12089 48356 <1,1,3,3>
1246  1246  <1,3,7>
34    34    <3,15>
228   1368  <3,3,3>
18    36    <7,7>
65 1     1     <64>
33    33    <4,12>
66 1     1     <65>
33    33    <1,32>
1205  1205  <1,2,10>
33    33    <2,21>
36    36    <5,10>
67 1     1     <66>
68 1     1     <67>
34    34    <1,33>
561   1122  <1,1,16>
36    36    <3,16>
69 1     1     <68>
34    34    <2,22>
70 1     1     <69>
35    35    <1,34>
1476  1476  <1,4,6>
37    37    <4,13>
37    37    <6,9>
71 1     1     <70>
72 1     1     <71>
36    36    <1,35>
630   1260  <1,1,17>
8964  53784 <1,1,1,8>
309858 3718296 <1,1,1,2,2>
34173 68346 <1,1,2,5>
1463  1463  <1,2,11>
39417 78834 <1,2,2,3>
1587  1587  <1,3,8>
833   1666  <1,5,5>
36    36    <2,23>
753   1506  <2,2,7>
1767  1767  <2,3,5>
39    39    <3,17>
41    41    <5,11>
40    40    <7,8>
73 1     1     <72>
74 1     1     <73>
37    37    <1,36>
75 1     1     <74>
37    37    <2,24>
841   1682  <2,4,4>
39    39    <4,14>
76 1     1     <75>
38    38    <1,37>
703   1406  <1,1,18>
40    40    <3,18>
77 1     1     <76>
39    39    <6,10>
78 1     1     <77>
39    39    <1,38>
1702  1702  <1,2,12>
39    39    <2,25>
43    43    <5,12>
79 1     1     <78>
80 1     1     <79>
40    40    <1,39>
780   1560  <1,1,19>
12467 74802 <1,1,1,9>
currently working on <1,1,1,1,4>

t  sum(g)  sum(f)
-----------------
1  1       1
2  1       1
3  1       1
4  2       3
5  1       1
6  4       4
7  1       1
8  7       17
9  3       5
10 6       6
11 1       1
12 28      43
13 1       1
14 8       8
15 8       8
16 55      409
17 1       1
18 55      91
19 1       1
20 66      111
21 11      11
22 12      12
23 1       1
24 495     1791
25 7       13
26 14      14
27 40      170
28 120     211
29 1       1
30 274     274
31 1       1
32 1463    66404
33 17      17
34 18      18
35 18      18
36 2354    7538
37 1       1
38 20      20
39 20      20
40 2072    9117
41 1       1
42 532     532
43 1       1
44 277     508
45 302     558
46 24      24
47 1       1
48 33428   514103
49 13      25
50 411     770
51 26      26
52 379     704
53 1       1
54 5812    28834
55 29      29
56 5432    26070
57 29      29
58 30      30
59 1       1
60 22438   41486
61 1       1
62 32      32
63 601     1137
64 220526  91328019
65 34      34
66 1308    1308
67 1       1
68 632     1193
69 35      35
70 1586    1586
71 1       1
72 399638  3928702
73 1       1
74 38      38
75 918     1759
76 782     1485
77 40      40
78 1824    1824
79 1       1

Hugo

```