Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I want to find $c_k$ for

$n = 1 + c_1 \Pi(n) + c_2 \Pi(\frac{n}{2})+ c_3 \Pi(\frac{n}{3})+ c_4 \Pi(\frac{n}{4})+ c_5 \Pi(\frac{n}{5})+...$,

assuming there are such coefficients, where

$\Pi(n) = \pi(n) + \frac{1}{2}\pi(n^\frac{1}{2})+ \frac{1}{3}\pi(n^\frac{1}{3})+ \frac{1}{4}\pi(n^\frac{1}{4})+...$ and $\pi(n)$ is the prime counting function.

Are there known techniques for solving a problem like this?

EDIT - I was really asking this to figure out how tough of a question this is. At least for anon, not very tough, it would seem.

In case any of you are curious, one way to calculate these coefficients is like so:

If $C_k$ are the Gregory Coefficients, the first few terms being $-1, \frac{1}{2}, \frac{1}{12}, \frac{1}{24}, \frac{19}{720}, \frac{3}{160},...$, and we have the strict divisor function such that

$d_0'(j) = 1$ if $n = 1$, $0$ otherwise

$d_1'(j) = 1$ if $n \neq 1$, $0$ otherwise

$d_k'(n) = \sum\limits_{j | n} d_1'(j) d_{k-1}'(n/j )$

then $c_k = \sum\limits_{a=0} -1^a C_a d_a'(k)$

There's a straightforward reason why the Gregory coefficients show up, involving Linnik's identity $\sum\limits_{k=1} \frac{-1^{k+1}}{k} d_k'(n) = \frac{\Lambda(n)}{\log n}$and multiplicative inverses of series coefficients, but I won't go into that.

Anyway, good job, anon.

share|cite|improve this question
Looks like Möbius inversion won't work here. You might be able to compute the coefficients recursively, though. Since $\Pi(1)=0$ and $\Pi(2)=1$, we make the deduction $2=1+c_1\Pi(2)$ $\implies c_1=1$. Likewise $\Pi(3)=2$ and $\Pi(4)=5/2$, hence $c_2=1/2$. Then $c_3=1/2$ and $c_4=5/12$ (if I did my arithmetic correctly). – anon Sep 14 '11 at 19:09
Wow - color me impressed. I had actually tracked down a much more complicated way of solving this problem, but you jump to the end pretty much immediately. It's too bad you didn't submit this as an answer - I would have voted it up. – Nathan McKenzie Sep 14 '11 at 19:49
The recursion idea wasn't really a number-theoretic insight, and Eric was the one who thought of involving $\Lambda(n)/\log n$ and noticed the factorization pattern, so I don't see why I get so much credit. But now I'm curious if a more analytic derivation can be made in a Riemann-esque way with $z/\log(1-z)$, contour integration, and some kind of divisibility inversion. – anon Sep 14 '11 at 20:33
up vote 3 down vote accepted

This is really a comment, but it is a bit too long.

Notice that you are summing under a hyperbola. Since $$\Pi(x)=\sum_{n\leq x}\frac{\Lambda(n)}{\log n}$$ we see that $$\sum_{k\leq x}c_{k}\Pi\left(\frac{x}{k}\right)=\sum_{k\leq x}c_{k}\sum_{n\leq\frac{x}{k}}\frac{\Lambda(n)}{\log n}=\sum_{nk\leq x}c_{k}\frac{\Lambda(n)}{\log n}.$$ Equivalently we are trying to find $f$, some function on the integers, satifying $$\sum_{n\leq M}\left(f*\frac{\Lambda}{\log}\right)(n)=M.$$

share|cite|improve this answer

Here is the implementation of anon's idea:

enter image description here

In case you would like to try the code out:

\[CapitalPi][n : (_Integer | _Rational)] := 
 Module[{k = Ceiling[Log2[n]] + 2, rec}, rec = 1/Range[k]; 

FindCoefficientsC[len_] := 
 Module[{mat = 
    PadRight[Table[\[CapitalPi][n/m], {n, 2, 2 len + 1}, {m, 1, n}]]},
    PadRight[mat], Range[1, 2 len]][[;; MatrixRank[mat]]]
share|cite|improve this answer
It is worth noting that each entry in the list depends on the prime factor decomposition of the number. If $k$ is prime, $c_k=\frac{1}{2}$. If $k=p^2$, then $c_k=\frac{5}{12}$, $$k=p^3\Rightarrow c_k=\frac{3}{8}$$ and $$k=p^4\Rightarrow c_k=\frac{251}{720}.$$ Also, if $k=pq$, (distinct primes) then $c_k=\frac{1}{3}$ and if $k=pqr$ then $c_k=\frac{1}{4}$. Lastly $k=p^2q$ then $c_k=\frac{7}{24}$. I can't see a pattern at the moment, but I think a good guess would not be hard to prove. – Eric Naslund Sep 14 '11 at 19:52
@Eric: If you're curious, I've added an explicit description of the coefficients to my question edit. I was fishing a bit with this question, to see if any other techniques existed for solving this problem - which they did, apparently. – Nathan McKenzie Sep 14 '11 at 20:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.