Two ordering problems

franktaw at franktaw at
Fri Aug 29 21:11:03 CEST 2008

Apparently you missed the discussion between Max and myself.  The
answer to your first problem (as defined below) is A005806.

The ones that can be achieved by assigning primes are A009997.  Since
this is different from A005806, the answer to the second problem is no.

Franklin T. Adams-Watters

-----Original Message-----
From: David Wilson <dwilson at>

If we momentarily ignore the problem of finding numerical examples for 
moment, let P(n) be a set of n distinct symbolic primes (e.g, P(3) =
{p,q,r}) and let D(n) be the set of divisors of PROD(P(n)) (e.g, D(3) =
{1,p,q,r,pq,qr,pr,pqr}. We then use the following rules 

   [1] 1 < p < q < r < ... < x 
   [2] a < b  =>  ac < bc 
   [3] (a < b and b < c) => a < c 

to induce a partial order G(n) on D(n) (G(n) because it can be
represented as a graph with nodes D(n)). 

The first problem is to count the total orderings of D(n) that conform
to G(n). I doubt we are the first to consider this problem, I wonder if
there is an efficient algorithm. 

The second problem is whether all of the total orderings can be 
by assignment of numerical primes to the variables. Interesting 


The new pages had several bugs, especially in the way they handled

Apologies!  I hope they have been fixed now. Let me know
if anyone finds other bugs.


PS When these programs mail you what you wrote,
would people prefer the lines to be wrapped with < p r e > and < / p r e >
or not?

More information about the SeqFan mailing list