The Dirichlet inverse of the Euler totient function is:
$$\varphi^{-1}(n) = \sum\_{d \mid n} \mu(d)d \tag{1}$$
and the von Mangoldt function can be expanded/computed as:
$$\Lambda(n) = \sum\limits\_{k=1}^{\infty}\frac{\varphi^{-1}(\gcd(n,k))}{k} \tag{2}$$
Consider the sequences:
$$a(n)=\sum \_{k=1}^{j} \frac{\varphi^{-1}(\gcd (n,k))}{k}$$
$$b(n)=\sum \_{k=1}^{j+1} \frac{\varphi^{-1}(\gcd (n,k))}{k}$$


**Question:**



> 
> For what values of $j$ does $b(n)$ eventually correlate better than $a(n)$ with the von Mangoldt function $\Lambda(n)$ as $n \rightarrow \infty$?
> 
> 
> 


The exceptions of $j$ when $b(n)$ correlates worse than $a(n)$ appear to be:  

$$j=7, 15, 24, 26, 31$$ which when added with $1$ gives initially a sequence of powers of some sort:  

$$j+1=8, 16, 25, 27, 32$$


A very slow Mathematica program that computes the sequences $a(n)$ and $b(n)$ and compares their Pearson correlation with the von Mangoldt function, is:



```
Clear[a, n, k, start, end]
nnn = 200;
a[n_] := Total[Divisors[n]*MoebiusMu[Divisors[n]]];
Do[column = j;
 earlier = 
  Table[Correlation[
    Table[Sum[a[GCD[n, k]]/k, {k, 1, column}], {n, 1, nn}], 
    Table[N[MangoldtLambda[n]], {n, 1, nn}]], {nn, 2, nnn}];
 later = Table[
   Correlation[
    Table[Sum[a[GCD[n, k]]/k, {k, 1, column + 1}], {n, 1, nn}], 
    Table[N[MangoldtLambda[n]], {n, 1, nn}]], {nn, 2, nnn}];
 sign = Sign[later - earlier];
 Print[If[Last[sign] == -1, j, 0]], {j, 2, 32}]

```

`nnn = 200;` is considered a large number that serves as the substitute for $n \rightarrow \infty$ in the program.




---


Edit 10.7.2021:


Correlations of partial sums:



```
Clear[a, n, k, start, end]
nnn = 400;
a[n_] := Total[Divisors[n]*MoebiusMu[Divisors[n]]];
Do[column = j;
 earlier = 
  Table[Correlation[
    Accumulate[
     Table[Sum[a[GCD[n, k]]/k, {k, 1, column}], {n, 1, nn}]], 
    Accumulate[Table[N[MangoldtLambda[n]], {n, 1, nn}]]], {nn, 2, 
    nnn}];
 later = Table[
   Correlation[
    Accumulate[
     Table[Sum[a[GCD[n, k]]/k, {k, 1, column + 1}], {n, 1, nn}]], 
    Accumulate[Table[N[MangoldtLambda[n]], {n, 1, nn}]]], {nn, 2, 
    nnn}];
 sign = Sign[later - earlier];
 Print[{earlier, Count[sign, 1], sign, j}], {j, 2, 32}]

```


Correlating the von Mangoldt function with periodic sequences
TL;DR: This is not a full answer. I compute asymptotically the correlation of $b(n)$ and $\Lambda (n)$ (it turns out to be $0$) and the correlation of $b(n)$ and $a(n)$ in a relatively closed form sum (I don't think there's really a simpler expression). Although I do not show when the correlation of $b(n)$ and $a(n)$ is larger or smaller than $0$, I show that it is never equal exactly to $0$ except for $j = 1$.




---


For the rest of the answer let us denote by $\mathbb{E}\_N$ the average of a function on the numbers $1, \dots, N$. We will always look at correlations up to $N$, and then let $N \to \infty$. We also assume that $j > 1$.


First notice that the correlation of $b(n)$ and $\Lambda(n)$ tends to $0$ as $N \to \infty$. This is simply because $b(n)$ is a bounded sequence and $\Lambda (n)$ fluctuates wildly. More precisely, the correlation is equal to
$$\frac{\mathbb{E}\_N \left[ \Lambda (n) b(n) \right] - \mathbb{E}\_N \left[ \Lambda (n) \right] \mathbb{E}\_N \left[ b(n) \right]}{\left( \mathbb{E}\_N \left[ \Lambda (n)^2 \right] - \mathbb{E}\_N \left[ \Lambda(n) \right]^2 \right)^{\frac{1}{2}} \left( \mathrm{Var}\_N \left( b(n) \right) \right)^{\frac{1}{2}}}$$


As $b(n)$ is bounded, the numerator is at most a constant times $\mathbb{E}\_N \left[ \Lambda (n) \right]$, which by the Prime Number Theorem is asymptotically equal to $1$. Also by the Prime Number Theorem we have $\mathbb{E}\_N \left[ \Lambda (n)^2 \right] \sim \log N$, and as $b(n)$ is a non constant periodic sequence (with period $\mathrm{lcm} \left( 1, \dots, j + 1 \right)$) its variance is bounded by below. Therefore the correlation of $b(n)$ and $\Lambda (n)$ is bounded in absolute value by a constant times $\frac{1}{\log N}$, which tends to $0$.




---


Now, let us compute the correlation of $a(n)$ and $b(n)$. As they are periodic non-constant sequences, their variance is bounded by below. We will see that their covariance is asymptotically equal to a certain number, and whether this number is greater or lesser than $0$ exactly determines whether $b(n)$ is better correlated with $a(n)$ or with $\Lambda (n)$. First, we will compute their averages.


$$\mathbb{E}\_N \left[ a(n) \right] = \frac{1}{N} \sum\_{n = 1}^{N} \sum\_{k = 1}^{j} \frac{1}{k} \sum\_{d | k, n} d \mu (d) = \frac{1}{N} \sum\_{d = 1}^{j} d \mu(d) \left[ \frac{N}{d} \right] \sum\_{k \leq \frac{j}{d}} \frac{1}{d k}$$
As $N \to \infty$ this is is asymptotically equal to
$$\sum\_{d = 1}^{j} \frac{\mu (d)}{d} H\_{\left[ \frac{j}{d} \right]}$$
where $H\_m = \sum\_{k = 1}^{m} \frac{1}{k}$ is the Harmonic number. Replacing $j$ with $j + 1$ we get that $\mathbb{E}\_N \left[ b(n) \right]$ is asymptotically equal to $\sum\_{d = 1}^{j + 1} \frac{\mu (d)}{d} H\_{\left[ \frac{j + 1}{d} \right]}$ as $N \to \infty$. Now, we compute


$$\mathbb{E}\_N \left[ a(n) b(n) \right] = \frac{1}{N} \sum\_{n = 1}^{N} a(n) b(n) = \frac{1}{N} \sum\_{n = 1}^{N} \sum\_{k\_1 = 1}^{j} \sum\_{k\_2 = 1}^{j + 1} \frac{1}{k\_1 k\_2} \sum\_{d\_1 | n, k\_1} \sum\_{d\_2 | n, k\_2} d\_1 d\_2 \mu(d\_1) \mu(d\_2)$$
Notice that $d\_1 | n$ and $d\_2 | n$ if and only if $\mathrm{lcm} \left( d\_1, d\_2 \right) | n$. Interchanging the order of summation, and applying the fact that $\frac{1}{N} \left[ \frac{N}{m} \right] \sim \frac{1}{m}$ for $m \in \mathbb{N}$ we see that this sum is equal to
$$\sum\_{d\_1 = 1}^{j} \sum\_{d\_2 = 1}^{j + 1} \frac{\mu(d\_1) \mu(d\_2)}{\mathrm{lcm} \left( d\_1, d\_2 \right)} H\_{\left[ \frac{j}{d\_1} \right]} H\_{\left[ \frac{j + 1}{d\_2} \right]}$$




---


To sum it up, the covariance of $b(n)$ and $a(n)$ is asymptotically
$$\sum\_{d\_1 = 1}^{j} \sum\_{d\_2 = 1}^{j + 1} \frac{\mu(d\_1) \mu(d\_2)}{\mathrm{lcm} \left( d\_1, d\_2 \right)} H\_{\left[ \frac{j}{d\_1} \right]} H\_{\left[ \frac{j + 1}{d\_2} \right]} - \left( \sum\_{d\_1 = 1}^{j} \frac{\mu(d\_1)}{d\_1} H\_{\left[ \frac{j}{d\_1} \right]} \right) \left( \sum\_{d\_2 = 1}^{j + 1} \frac{\mu (d\_2)}{d\_2} H\_{\left[ \frac{j + 1}{d\_2} \right]} \right)$$
Let us show that this number is non-zero. For all $j > 1$, there exists a prime $\frac{j + 1}{2} < p < j + 1$. It turns out that the covariance has a factor of $p^2$ in the denominator. To prove this, let us see what terms could contribute such a factor. In order for $p$ to appear in the denominator of $H\_m$, we must have $m \geq p$, and since $p > \frac{j + 1}{2}$, in order for $p$ to appear in $H\_{\left[ \frac{j}{d\_1} \right]}$ or $H\_{\left[ \frac{j + 1}{d\_2} \right]}$ we must have $d\_1 = 1$ or $d\_2 = 1$.


In order for $p$ to appear in $d\_1, d\_2$ or $\mathrm{lcm} \left( d\_1, d\_2 \right)$ at least one of $d\_1, d\_2$ must be equal to $p$. Going over the very limited options, we see that
$$\sum\_{d\_1 = 1}^{j} \sum\_{d\_2 = 1}^{j + 1} \frac{\mu(d\_1) \mu(d\_2)}{\mathrm{lcm} \left( d\_1, d\_2 \right)} H\_{\left[ \frac{j}{d\_1} \right]} H\_{\left[ \frac{j + 1}{d\_2} \right]}$$
contains $\frac{1}{p^2} - \frac{2}{p^2} = - \frac{1}{p^2}$ and
$$\left( \sum\_{d\_1 = 1}^{j} \frac{\mu(d\_1)}{d\_1} H\_{\left[ \frac{j}{d\_1} \right]} \right) \left( \sum\_{d\_2 = 1}^{j + 1} \frac{\mu (d\_2)}{d\_2} H\_{\left[ \frac{j + 1}{d\_2} \right]} \right)$$
contains in total $\frac{0}{p^2}$, thus proving the claim.


