Cycles in a number-theoretic graph...

AUMathTutor

Consider the following graph:

1.) There are n vertices labeled 1...n.
2.) There exists an edge between vertices u and v iff label(u) | label(v) (the label of u divides the label of v).

How many unique simple cycles does such a graph with n vertices contain?

Note(s):
The exact function in terms of n may be too hard to get (lol), but growth orders are also acceptable, with appropriate proof.
The graphs are non-directed graphs... no double-edges are allowed, but self loops are present.
Cycles may be counted one way or both ways (that is, if 1-2-4-1 is counted as a cycle, then 1-4-2-1 may or may not be counted, as long as you make your counting method explicit).

davee123

I couldn't get a general case, but a brute force method revealed for n=1 to n=24:

1: 0
2: 0
3: 0
4: 1
5: 1
6: 6
7: 6
8: 18
9: 25
10: 42
11: 42
12: 241
13: 241
14: 324
15: 667
16: 1602
17: 1602
18: 5511
19: 5511
20: 21596
21: 32549
22: 35434
23: 35434
24: 237727

So, it would seem that the increase from n to n+1 is dependent on the number of factors of n+1, since something like 21 (factors 1, 3, 7) is a smaller percentage increase than 20 (factors 1, 2, 4, 5, 10). And obviously when n+1 is prime, no additional loops are added.

However, because primes necessarily don't add loops, doesn't that mean that you can't have a mathematical formula for the value at n vertices, since primes aren't mapped to any known function? I guess I'm not sure how you'd go about figuring out a growth order in that case, since it's a little erratic. Anyway, I'm interested to hear your solution (assuming you've got one?)

[edit]
So, let's say L(x) is the number of loops, and F(x) is the number of factors of x. It looks like L(x)/L(x-1) <= F(x), except for a few early numbers (6 and 12).
[/edit]

DaveE