A058890

[Gordon Royle]

> %I A058890
> %S A058890 1,2,9,10,15
> %N A058890 Smallest number of nodes in a graph whose group is cyclic 
> of order n.
> %D A058890 F. Harary, Graph Theory, Page 176, Problem 14.7.
> %K A058890 nonn,easy,nice,more
> %O A058890 1,2
> %A A058890 njas, Jan 08 2001

The full story for this problem is known... the crucial reference which
appears surprisingly little known is

The classification of minimal graphs with given abelian automorphism group
WIlliam C. Arlinghaus
Memoirs of the American Mathematical Society
Number 330
September 1985

He does all the abelian groups, but it gets complicated.

> I looked up the reference.  The group referred to is the graph's automorphism
> group.  Harary states (and the proof is the exercise)
> 
> (a) a(2) = 2; for r > 1 a(2^r) = 2^r + 6;
>  
> (b) for p = 3 or 5, and r > 0, a(p^r) = p^r + 2p;
> 
> (c) for p prime and >= 7, and r > 0, a(p^r) = p^r + p.
> 
> Harary also says that a(n) can be computed for non-prime-power n, but the
> formula is complicated.
> 
> I don't think this sequence should be labelled 'easy'.  We can easily compute a
> large number of terms from Harary's formulas, but there seems to be no easy way
> to compute the next term.  (I don't think there's a feasible algorithm to
> compute the automorphism group of a graph.)


As an aside, there is a feasible algorithm to compute the automorphism
group of a graph (Brendan McKay's nauty) but of course there are too
many graphs to check exhaustively for the next term of the sequence.
Well, actually that's not true because the next term turns out to
be 11, but in principle there are too many graphs to do anything
more than another term or two in our lifetimes.

But in fact we don't need to do it exhaustively, because the exact result is

	a(n) = a(p1^r1 p2^r2 ... pk^rk) = a(p1^r1) + ... + a(pn^rn) - F

where F is a "correction factor".

The correction factor depends on the exponents of the primes 2, 3 and
5 in the prime factorization of the number n. I will call these values 
n2, n3 and n5 respectively.

The correction factor is

	0 if n3 = 0 	(so unless 3 divides n, the upper bound is dead on)
	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


Putting this altogether into a program, we get 

n a(n)
1 1
2 2
3 9
4 10
5 15
6 11
7 14
8 14
9 15
10 17
11 22
12 18
13 26
14 16
15 21
16 22
17 34
18 17
19 38
20 25
21 23
22 24
23 46
24 22
25 35
26 28
27 33
28 24
29 58
30 23
31 62
32 38
33 31
34 36
35 29
36 24
37 74
38 40
39 35
40 29
41 82
42 25
43 86
44 32
45 27
46 48
47 94
48 30

etc.

-- 
Dr. Gordon F Royle, http://www.cs.uwa.edu.au/~gordon, gordon at cs.uwa.edu.au
--