|
| |
|
|
A058890
|
|
Smallest number of nodes in a graph whose automorphism group is cyclic of order n.
|
|
1
|
|
|
|
0, 2, 9, 10, 15, 11, 14, 14, 15, 17, 22, 18, 26, 16, 21, 22, 34, 17, 38, 25, 23, 24, 46, 22, 35, 28, 33, 24, 58, 23, 62, 38, 31, 36, 29, 24, 74, 40, 35, 29, 82, 25, 86, 32, 27, 48, 94, 30
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
REFERENCES
|
William C. Arlinghaus, The classification of minimal graphs with given Abelian automorphism group, Memoirs of the American Mathematical Society, Number 330, September 1985.
F. Harary, Graph Theory, Page 176, Problem 14.7.
|
|
|
LINKS
|
Table of n, a(n) for n=1..48.
|
|
|
FORMULA
|
a(2) = 2; for r > 1, a(2^r) = 2^r + 6; for p = 3 or 5 and r > 0, a(p^r) = p^r + 2p; for p prime >= 7 and r > 0, a(p^r) = p^r + p. (Harary)
a(n) = a(p1^r1 p2^r2 ... pk^rk) = a(p1^r1) + ... + a(pn^rn) - F where F is a "correction factor" which depends on the exponents of the primes 2, 3 and 5 in the prime factorization of the number n. Call these values n2, n3 and n5 respectively.
The correction factor F is 0 if n3 = 0 (so unless 3 divides n, the upper bound is exact); 4 if n2 = 2, n3 >= 1 and n5 = 1; 3 if n2 != 2, n3 >=1 and n5 = 1; 1 if n2 = 2, n3 >= 1 and n5 != 1; 1 if n2 >= 2, n3 = 1 and n5 != 1; 0 otherwise.
|
|
|
MATHEMATICA
|
a[1] = 0; a[2] = 2; a[n_ /; IntegerQ[ Log[2, n]]] := 2^Log[2, n] + 6; a[n_ /; IntegerQ[ Log[3, n]]] := 3^Log[3, n] + 6; a[n_ /; IntegerQ[ Log[5, n]]] := 5^Log[5, n] + 10; a[n_ /; MatchQ[ FactorInteger[n], {{(p_)^(r_)} /; PrimeQ[p]}]] := p^r + 2*p; a[(n_)?PrimeQ] := 2*n; a[n_] := a[n] = (fi = FactorInteger[n]; n2 = (s = Select[fi, First[#] == 2 &, 1]; If[s == {}, 0, s[[1, 2]]]); n3 = (s = Select[fi, First[#] == 3 &, 1]; If[s == {}, 0, s[[1, 2]]]); n5 = (s = Select[fi, First[#] == 5 &, 1]; If[s == {}, 0, s[[1, 2]]]); pp = fi[[All, 1]]; rr = fi[[All, 2]]; Total[a /@ (pp^rr)] - cf[n2, n3, n5]); cf[n2_, 0, n5_] = 0; cf[2, n3_ /; n3 >= 1, 1] = 4; cf[n2_ /; n2 != 2, n3_ /; n3 >= 1, 1] = 3; cf[2, n3_ /; n3 >= 1, n5_ /; n5 != 1] = 1; cf[n2_ /; n2 >= 2, 1, n5_ /; n5 != 1] = 1; cf[_, _, _] = 0; Table[a[n], {n, 1, 48}] (* Jean-François Alcover, Oct 19 2011 *)
|
|
|
CROSSREFS
|
Cf. A080803.
Sequence in context: A344145 A051017 A078180 * A306998 A047468 A032929
Adjacent sequences: A058887 A058888 A058889 * A058891 A058892 A058893
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
|
AUTHOR
|
N. J. A. Sloane, Jan 08 2001
|
|
|
EXTENSIONS
|
Additional comments and more terms from David Wasserman and Gordon F. Royle, Jun 09 2002
|
|
|
STATUS
|
approved
|
| |
|
|
