Divisor graph sequence

[Richard Mathar]

All,

My computations agree with Richard's below:

> Counting these gives the sequence e(n), n=1..20 of
> 0, 1, 1, 3, 1, 5, 1, 6, 3, 5, 1, 12, 1, 5, 5, 10, 1, 12, 1, 12,...

Also, I believe David's conjecture should be altered slightly from the
statement

e(n) prime => n = 4 or n squarefree

to the statement

e(n) prime => n = p^2 (where p is prime) or n squarefree.

This is a fabulous question!  All the best.

James





> dww> From seqfan-owner at ext.jussieu.fr  Tue May 20 16:04:36 2008
> dww> From: "David W. Wilson" <wilson.d at anseri.com>
> dww> To: <seqfan at ext.jussieu.fr>
> dww> Subject: Divisor graph sequence
> dww> Date: Tue, 20 May 2008 09:56:12 -0400
> dww>
> dww> Let G(n) the divisor graph of n whose nodes are the divisors of n and
> edges
> dww> a->b indicate that a is a (proper/any) divisor of n.
> dww>
> dww> Clearly the number of vertices of G(n) is d(n) = A000005(n).
> dww>
> dww> What is the number of edges e(n) of G(n)?
> dww>
> dww> If two numbers a and b have the same prime signature, G(a) and G(b)
> are
> dww> isomorphic, so e(n) is a function of the prime signature of n.
> dww>
> dww> Using the proper divisor definition of G(n), we have e(p^k) =
> k(k-1)/2 for p
> dww> prime. It looks as if prime values of e(n) are scarce, I conjecture
> that
> dww> e(n) prime => n = 4 or n squarefree.
> dww>
> dww> Can anyone come up with a useful recurrence for e(n)?
>
> The sequence for the particular case of loop-less graphs
> (a->b points only to the nodes b<a, never to itself, proper divisors in
> the common sense as in A032741) seems not to be in
> the OEIS yet; consider the cases n=3...20 with oriented edges
>
> 3->1,
>
> 4->2,4->1,2->1,
>
> 5->1,
>
> 6->3,6->2,6->1,3->1,2->1,
>
> 7->1,
>
> 8->4,8->2,8->1,4->2,4->1,2->1,
>
> 9->3,9->1,3->1,
>
> 10->5,10->2,10->1,5->1,2->1,
>
> 11->1,
>
> 12->6,12->4,12->3,12->2,12->1,6->3,6->2,6->1,4->2,4->1,3->1,2->1,
>
> 13->1,
>
> 14->7,14->2,14->1,7->1,2->1,
>
> 15->5,15->3,15->1,5->1,3->1,
>
> 16->8,16->4,16->2,16->1,8->4,8->2,8->1,4->2,4->1,2->1,
>
> 17->1,
>
> 18->9,18->6,18->3,18->2,18->1,9->3,9->1,6->3,6->2,6->1,3->1,2->1,
>
> 19->1,
>
> 20->10,20->5,20->4,20->2,20->1,10->5,10->2,10->1,5->1,4->2,4->1,2->1,
>
> Counting these gives the sequence e(n), n=1..20 of
> 0, 1, 1, 3, 1, 5, 1, 6, 3, 5, 1, 12, 1, 5, 5, 10, 1, 12, 1, 12,...
>
> If I include the a->a loops (set of divisors is of order A00005), I seem
> to get A007425.
>
> Using the "very" proper divisor notation in which neither 1 nor a are
> counted as divisors of a, we have
>
> 4->2,
>
> 6->3,6->2,
>
> 8->4,8->2,4->2,
>
> 9->3,
>
> 10->5,10->2,
>
> 12->6,12->4,12->3,12->2,6->3,6->2,4->2,
>
> 14->7,14->2,
>
> 15->5,15->3,
>
> 16->8,16->4,16->2,8->4,8->2,4->2,
>
> 18->9,18->6,18->3,18->2,9->3,6->3,6->2,
>
> 20->10,20->5,20->4,20->2,10->5,10->2,4->2,
>
> with edge count e(n), n=1..20 of
> 0, 0, 0, 1, 0, 2, 0, 3, 1, 2, 0, 7, 0, 2, 2, 6, 0, 7, 0, 7...
>
> This is all modulo the errors in my program.
> Richard Mathar
>