[seqfan] Re: A combinatorial problem

Alois Heinz heinz at hs-heilbronn.de
Tue Aug 3 16:36:38 CEST 2010


Alois Heinz schrieb:
> So I computed a(p*q*r*s) = 5712 for distinct primes p,q,r,s.
>
> Now we have:
> a(p), a(p*q), a(p*q*r), a(p*q*r*s) = 1, 2, 18, 5712
> which looks like the beginning of sequence
> http://www.research.att.com/~njas/sequences/A003043
> Can you prove that there is any connection?
>   
Ok, the proof is easy.

For distinct primes p_1, ..., p_n
m = p_1 * p_2 * ... p_n has 2^n divisors.
a(m) counts all permutations of the divisors
(d_1=m, d_2..., d_{2^n}) where neighbors
d_j, d_{j+1} differ in exactly one prime factor.
Thus a(m) equals the number of Hamiltonian paths
on an n-cube with a marked starting node.

So we have a(p*q*r*s*t) = 5859364320
for distinct primes p,q,r,s,t, according to
http://www.research.att.com/~njas/sequences/A003043

Alois





More information about the SeqFan mailing list