

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}] (* JeanFranç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



