Divisor graph sequence

[Maximilian Hasler]

>> 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.(...) Can anyone come up with a useful recurrence for e(n)?
> Also, I believe David's conjecture should be altered
> e(n) prime => n = p^2 (where p is prime) or n squarefree.

[PS: since I took some time to finish the mail, the first part of the
first part of it isn't interesting any more, but in the 2nd part
there's some original information with recurrences and generating
functions.]

Since all the divisors of d are divisors of n, it is simple to count
the number of edges - these are the couples (d1,d2) with
 d1 | n ; d2 | n and d2 | d1
<=> d1 | n ; d2 | d1  (and  d1 >=d2)
so we just have to add up numdiv=tau=sigma_0 for each divisor of n,

e'(n) = sum_{ d | n } tau(d)
if we allow for all divisors.

>> If I include the a->a loops  I seem to get A007425.

This is already written there:
%o A007425 (PARI) for(n=1,100,print1(sumdiv(n,k,numdiv(k)),","))


If we exclude d=n, we get e(n)=A007425(n)-numdiv(n):
indeed, that case was counted once for each d|n (including d=n)
so we get that count on subtracting 1 from each term of the sum:

gp > vector(40,n,sumdiv(n,d,(numdiv(d)-1)))
%1 = [0, 1, 1, 3, 1, 5, 1, 6, 3, 5, 1, 12, 1, 5, 5, 10, 1, 12, 1, 12,
5, 5, 1, 22, 3, 5, 6, 12, 1, 19, 1, 15, 5, 5, 5, 27, 1, 5, 5, 22, 1,
19, 1, 12, 12, 5, 1, 35, 3, 12, 5, 12, 1, 22]

but since there are numdiv(n) terms, this just amounts to leave out
that (largest) term (d=n) in the full sum,

gp > vector(40,n, sumdiv(n,d,if(d<n,numdiv(d)))  )
%2 = [0, 1, 1, 3, 1, 5, 1, 6, 3, 5, 1, 12, 1, 5, 5, 10, 1, 12, 1, 12,
5, 5, 1, 22, 3, 5, 6, 12, 1, 19, 1, 15, 5, 5, 5, 27, 1, 5, 5, 22, 1,
19, 1, 12, 12, 5, 1, 35, 3, 12, 5, 12, 1, 22]

which is of course the same as:
e(n)= sumdiv(n,d, numdiv(d)) - numdiv(n).


On the other hand, it can be shown that :

e( p1*p2*...*pk ) = 3^k - 2^k
if p1,...,pk are k distinct primes ;
this is prime for k in A057468.

e( p1^2 * p2*...*pn ) = 2*3^(n+1)-3*2^n = 3 * A027649(n)

e( p1^3 * p2*...*pn ) = 10*3^(n-1)-2^(n+1) = 2 * A084171(n)
  = 2 ( 5*3^(n-1) - 2^n )

e( p1^4 * p2*...*pn ) = 5 * A083313(n) = 5* (3^n- 2^(n-1)).

e( p1^5 * p2*...*pn ) = 3*(7*3^(n-1)-2^n) = 7*3^n-3*2^n
(not yet in OEIS)
it is seen that except for the 1st case (signature{1,...,1})
this can never be prime:
In fact, all these sequences obey to the recursion

a(n+1) = 5 a(n) - 6 a(n-1) with a(0)=0,a(1)=k(k+1)/2

(where  n=#[k,1,...1], prime signature of the argument)
and have the o.g.f:

e( p1^k * p2*...*pn ) = polcoeff( x( k(k+1)/2 - (k-1)(k+1)*x )/(1 -
5*x + 6*x^2), n)


For prime signature (k,2,1....1) we have the same recursion (starting at n=2):
/* prime signature (2,2,1....1) */
?vector(15,n,e(prod(i=1,n+1,prime(i),2*3)))
%4 = [27, 90, 288, 900, 2772, 8460, 25668, 77580, 233892, 703980,
2116548, 6358860, 19095012, 57321900, 172039428]
?ggf(%)
%5 = (-45*x + 27)/(6*x^2 - 5*x + 1)

/* prime signature (3,2,1....1) */
? vector(15,n,e(prod(i=1,n+1,prime(i),2^2*3)))
%6 = [48, 156, 492, 1524, 4668, 14196, 42972, 129684, 390588, 1174836,
3530652, 10604244, 31837308, 95561076, 286781532]
? ggf(%)
%7 = (-84*x + 48)/(6*x^2 - 5*x + 1)

/* prime signature (4,2,1....1) */
? vector(14,n,e(prod(i=1,n+1,prime(i),2^3*3)))
%8 = [75, 240, 750, 2310, 7050, 21390, 64650, 194910, 586650, 1763790,
5299050, 15912510, 47768250, 143366190]
? ggf(%)
%9 = (-135*x + 75)/(6*x^2 - 5*x + 1)

/* prime signature (5,2,1....1) */
? vector(14,n,e(prod(i=1,n+1,prime(i),2^4*3)))
%10 = [108, 342, 1062, 3258, 9918, 30042, 90702, 273258, 822078,
2470842, 7421742, 22283658, 66887838, 200737242]
? ggf(%)
%11 = (-198*x + 108)/(6*x^2 - 5*x + 1)

Thus, for  (k,2,1....1) (n prime factors), we obviously have again
a(n+1) = 5 a(n) - 6 a(n-1)
starting with a(2)=3(k+1)^2, a(3)=3(k+1)(3k+4),
o.g.f. = x^2 ( 3(k+1)^2 - 3k(2k-1) x )/(1-5x+6x^2).

Analogous relations for other prime signatures can readily be obtained
from the above code.

Maximilian

PS: ggf() adopted from http://www.jjj.de/pari/ggf.inc.gp:
ggf(v)={local(p,q,L=#v\2); if(#q=qflll(matrix(L,L,i,j,v[i-j+L+1]),4)[1],
if(polcoeff(p=Ser(q[,1]),0)<0,p=-p); if(Ser(v)==q=Pol(Ser(v)*p)/Pol(p),q))}