Divisor graph sequence
David W. Wilson
wilson.d at anseri.com
Tue May 20 15:56:12 CEST 2008
Let G(n) the divisor graph of n whose nodes are the divisors of n and edges
a->b indicate that a is a (proper/any) divisor of n.
Clearly the number of vertices of G(n) is d(n) = A000005(n).
What is the number of edges e(n) of G(n)?
If two numbers a and b have the same prime signature, G(a) and G(b) are
isomorphic, so e(n) is a function of the prime signature of n.
Using the proper divisor definition of G(n), we have e(p^k) = k(k-1)/2 for p
prime. It looks as if prime values of e(n) are scarce, I conjecture that
e(n) prime => n = 4 or n squarefree.
Can anyone come up with a useful recurrence for e(n)?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20080520/556a6c50/attachment.htm>
More information about the SeqFan
mailing list