OFFSET
1,2
COMMENTS
Consider vertices numbered 0 to n. For 1 <= k <= n, add an arc from v_k to (v_k+k) mod q, where q = n+1. (Thus (n+1)^n possibilities.) Two such digraphs are considered equivalent under the following operations: (i) rename each v to (v+1) mod q; (ii) rename each v to (av) mod q, where a is relatively prime to q; (iii) form the converse digraph by reversing the direction of every arc. The number of equivalence classes is a(n).
REFERENCES
G. S. Bloom and D. F. Hsu, On graceful digraphs and a problem in network addressing, Congr. Numer., 35 (1982) 91-103.
D. E. Knuth, The Art of Computer Programming, forthcoming exercise in Section 7.2.2.3
LINKS
Peter Luschny, Table of n, a(n) for n = 1..100
EXAMPLE
Each equivalence class has exactly one digraph with v_1=0.
For n=3 the six classes of digraphs 0v_2v_3 are: {000,032}, {001,011,021,031}, {002,010,022,030}, {003,033}, {012,020}, {013,023}.
MAPLE
# This is a port from the Mathematica program below.
sols := proc(alf, bet, q)
igcd(alf, q); `if`(modp(bet, %) <> 0, 0, %) end:
F := proc(l, a, b, q) local s, r, ll;
s := 1; r := 1; ll := modp(l*a, q);
while ll > l do
s := s + 1;
ll := modp(ll*a, q);
r := modp(r*a+1, q); od;
`if`(ll <> l, 1, sols(a^s - 1, -r*b, q)) end:
G := proc(l, a, b, q) local s, r, ll;
s := 1; r := 1; ll := modp(-l*a, q);
while ll > l do
s := s + 1;
ll := modp(-ll*a, q);
r := modp(r*a+1, q); od;
`if`(ll <> l, 1, sols(a^s - 1, -r*b - l*irem(s, 2), q)) end:
f := (a, b, q) -> mul(F(l, a, b, q), l = 1..q-1):
g := (a, b, q) -> mul(G(l, a, b, q), l = 1..q-1):
a := proc(n) local q; q := n + 1;
add(`if`(igcd(a, q) > 1, 0, add(f(a, b, q) + g(a, b, q),
b = 0..q-1)), a = 1..q-1);
% / (2*q*numtheory:-phi(q)) end:
seq(a(n), n=1..21); # Peter Luschny, Mar 10 2021
MATHEMATICA
sols[alf_, bet_, q_]:=Block[{d=GCD[alf, q]}, If[Mod[bet, d]!=0, 0, d]]
(* that many solutions to alf x == bet (modulo q) for 0<=x<q *)
f[l_, a_, b_, q_]:=Block[{r, s, ll, atos},
s=1; ll=Mod[l*a, q]; r=1;
While[ll>l, s++; ll=Mod[ll*a, q]; r=Mod[r*a+1, q]];
If[ll==l, sols[a^s-1, -r b, q], 1]]
g[l_, a_, b_, q_]:=Block[{r, s, ll, atos},
s=1; ll=Mod[-l*a, q]; r=1;
While[ll>l, s++; ll=Mod[-ll*a, q]; r=Mod[r*a+1, q]];
If[ll==l, sols[a^s-1, -r b-l Mod[s, 2], q], 1]]
f[a_, b_, q_]:=Product[f[l, a, b, q], {l, q-1}]
g[a_, b_, q_]:=Product[g[l, a, b, q], {l, q-1}]
x[q_]:=Sum[If[GCD[a, q]>1, 0, Sum[f[a, b, q]+g[a, b, q], {b, 0, q-1}]], {a, q-1}]/
(2q EulerPhi[q])
a[n_]:=x[n+1]
CROSSREFS
KEYWORD
nonn
AUTHOR
Don Knuth, Feb 22 2021
EXTENSIONS
a(10) from Don Knuth, Mar 10 2021
More terms from Peter Luschny, Mar 10 2021
STATUS
approved