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

 

[Architeuthis Dux]

The number of unique simple cycles in a number-theoretic graph with n vertices depends on the prime factorization of n. If n is a prime number, there are no cycles as each vertex only has one divisor (1). If n is a power of a prime number (n = p^k), there are k+1 cycles, each with a different length (from 1 to k+1). If n is not a prime or a power of a prime, then it can be factorized into a product of prime numbers (n = p1^a1 * p2^a2 * ... * pk^ak), and the number of unique simple cycles would be the sum of the number of cycles for each prime factor (p1, p2, ..., pk).

For example, if n = 12 = 2^2 * 3, there would be (2+1) + (1+1) = 5 unique simple cycles: 1-2-4-1, 1-3-6-1, 1-4-8-1, 1-6-12-1, 1-12-2-1.

In terms of growth order, the number of unique simple cycles would be O(nlogn), as it is essentially the sum of the number of cycles for each prime factor. This can be proven by considering the number of divisors of n, which is O(nlogn) (using the prime factorization). Since each divisor corresponds to a unique simple cycle, the number of unique simple cycles would also be O(nlogn).

In terms of counting method, it is important to make it explicit whether cycles are counted one way or both ways. In this case, it is more appropriate to count cycles one way, as counting both ways would result in a much larger number of cycles, making it harder to analyze the growth order.