7
$\begingroup$

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.

$\endgroup$
3
  • 4
    $\begingroup$ 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). $\endgroup$
    – anon
    Sep 14, 2011 at 19:09
  • $\begingroup$ 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. $\endgroup$
    – Nathan McKenzie
    Sep 14, 2011 at 19:49
  • 1
    $\begingroup$ 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. $\endgroup$
    – anon
    Sep 14, 2011 at 20:33

2 Answers 2

Reset to default
3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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]; 
  rec.PrimePi[n^rec]]

FindCoefficientsC[len_] := 
 Module[{mat = 
    PadRight[Table[\[CapitalPi][n/m], {n, 2, 2 len + 1}, {m, 1, n}]]},
  LinearSolve[
    PadRight[mat], Range[1, 2 len]][[;; MatrixRank[mat]]]
  ]
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Eric Naslund
    Sep 14, 2011 at 19:52
  • $\begingroup$ @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. $\endgroup$
    – Nathan McKenzie
    Sep 14, 2011 at 20:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .