Divisor graph sequence - a start to a conjecture...

[sellersj at math.psu.edu]

All,

Using David's notation e(n) for the number of edges in the divisor graph
that he defined below, the following appears to be true:

1)  e(p^k) = k(k+1)/2  for p prime, and

2)  e(p*n) = 2*e(n) + sum(A000005(j), j is a divisor of n)

where the sum at the end is taken over all divisors j of the number n and
where p is a prime NOT dividing n.

So, for example, let n = 20 = 2^2*5.  Then e(20) = 12 from direct
calculation.  Now consider 3n = 60 (and note that gcd(3,n) = 1).  Then we
have e(60) = 42 from direct calculation and we also know that

2*e(20) + (the sum of A000005(j) where j is a divisor of 20) =
2*12 + (1 + 2 + 3 + 2 + 4 + 6) =
24 + 18 =
42,

the desired quantity.  Where did (1 + 2 + 3 + 2 + 4 + 6) come from?  These
are the number of divisors of 1, 2, 4, 5, 10, 20 respectively (and those
are the divisors of 20).

Of course, this does not take care of the case where we want to calculate
e(p*n) based on e(n) where p divides n.  That's the next issue with which
to deal.

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
>