I'm seeking the asymptotic growth of the function $$f(n) = \frac{1}{n}\sum_{d | n} 2^d \varphi(n/d) = \frac{1}{n} \sum_{k=1}^n 2^{\gcd(n, k)} \tag{1}$$ which counts the number of necklaces made of $n$ black or white beads where turning over is not allowed (sequence A000031 in the OEIS). Here, $\varphi$ is Euler's totient function. Formula (1) for $f$ is easily established by applying Burnside's lemma to the following action of $G = \mathbf{Z}/(n)$ on the set $\{0, 1\}^G$: $$(g\cdot f)(x) = f(xg).$$
The two representations of $f$ given in (1) yield the following bounds: $$\frac{2^n}{n} \le f(n) \le \frac{2^{n+1}-2}{n} \tag{2}$$ the lower bound coming from picking $d = n$ and the upper bound by noting that $\gcd(n, k) \le k$ and summing the geometric series. I'm pretty certain that $$f(n) \sim \frac{2^n}{n} \quad (n \to \infty)\tag{3}$$ but from (2) we can only get $$1 \le \varliminf_{n \to \infty} \frac{n f(n)}{2^n}\text{ and } \varlimsup_{n \to \infty} \frac{n f(n)}{2^n} \le 2.$$
My question(s) are: is (3) true? If so, how is it proved? If not, what is the correct statement?
Looking at the upper bound: $$ \sum_{k=1}^n 2^{\operatorname{gcd}(n,k)} = 2^n + \sum_{k=1}^{n-1} 2^{\operatorname{gcd}(n,k)} $$ Now, each $1\leq k\leq n-1$ which divides $n$ is at most $\frac{n}{2}$; and there will be at most $n-1$ such terms. So we get the upper bound: $$ \sum_{k=1}^n 2^{\operatorname{gcd}(n,k)} \leq 2^n + (n-1)\cdot 2^{n/2} = 2^n + o(2^n) $$ which should now allow you to conclude.