[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
More information about the SeqFan
mailing list