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?)


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).


DaveE