Timeline for Solving a recurrence relation for the prime counting function?
Current License: CC BY-SA 4.0
22 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 15, 2023 at 12:49 | vote | accept | mathoverflowUser | ||
| Nov 15, 2023 at 18:37 | |||||
| Nov 15, 2023 at 8:38 | answer | added | Peter Taylor | timeline score: 2 | |
| Nov 14, 2023 at 20:33 | answer | added | Steven Clark | timeline score: 0 | |
| Nov 14, 2023 at 17:17 | comment | added | Steven Clark | @PeterTaylor It's a simpler formula and admittedly kind of silly, but it you consider the more complicated generating function for the formula in the question the only difference is that it compensates for the $\frac{1}{n-2}$ factor and reversal of the order of the coefficients, so it seems kind of silly to me as well as it really doesn't provide any insight into the primes. I can post an answer illustrating my two generating functions if anyone is interested. | |
| Nov 14, 2023 at 11:26 | comment | added | Peter Taylor | @StevenClark's coefficients are $$a_i = \begin{cases}\textrm{arbitrary} & \textrm{if } i = 1 \\ 2 & \textrm{if } i = 2 \\ 0 & \textrm{if } i+1 \textrm{ composite} \\ \frac{1}{\pi(i)} & \textrm{otherwise} \end{cases}$$ It's a direct encoding of the primes. | |
| Nov 14, 2023 at 6:57 | comment | added | mathoverflowUser | @StevenClark: How do you define the $a_i$? I can see the numbers but I do not see the definition. The $c_i$ are defined as $1+b_i$ for $i>0$ and $c_{-1}=2$ or equivalently as the coefficients of $H'(t)/H(t)$ where $H(t) = \sum_{n} \pi(n) t^n$. | |
| Nov 14, 2023 at 4:05 | comment | added | Steven Clark | How is this related to the recurrence $$\pi(n)=\sum_{k=1}^{n-1} \pi(k)\, a_k\,,\quad n>2$$ where $$a=\left\{a_1,2,0,\frac{1}{2},0,\frac{1}{3},0,0,0,\frac{1}{4},0,\frac{1}{5},0,0,0,\frac{1}{6},0,\frac{1}{7},0,0,0,\frac{1}{8},0,0,0,0,0,\frac{1}{9},0,\frac{1}{10},0,...\right\}?$$ | |
| Nov 13, 2023 at 18:05 | comment | added | Sidharth Ghoshal | I was hoping this might shed some light on the matter: math.stackexchange.com/questions/4806220/… | |
| Nov 13, 2023 at 17:50 | comment | added | Sidharth Ghoshal | @mathoverflowUser the idea of trying a transform is the observation that $F((n-2)\pi(n)) = F(\sum_{k=0}^{n-1} \pi(k)b(n-k))$ so therefore $F(n-2)\star F(\pi(n)) = F(\pi(k)) F(b(n-k))$ so the right hand side becomes just a very nice multiplication but because of that $(n-2)$ the LHS now has a convolution so this doesn't help solve the problem in an obvious fashion. | |
| Nov 13, 2023 at 17:33 | comment | added | Peter Taylor | $$\pi(n+2) = \sum_{\vec{x}} \frac{c_{x_1-1}}{x_1} \cdot \frac{c_{x_2-1}}{x_1 + x_2} \cdot \frac{c_{x_3-1}}{x_1+x_2+x_3} \cdots \frac{c_{x_k-1}}{n}$$ where the sum is over compositions of $n$. Note quite the same as Bell polynomials, but possibly something in this form has been studied before. | |
| Nov 13, 2023 at 17:31 | comment | added | mathoverflowUser | @SidharthGhoshal: Thanks for your interest in this question. After thinking about it, I do not clearly see , how the introduction of Fourier transform can help in this case. If you can give an answer with details, I will try to follow. | |
| Nov 13, 2023 at 17:06 | comment | added | Sidharth Ghoshal | Yes even in the finite case this factors. See the circular convolutional theorem section here: en.m.wikipedia.org/wiki/Discrete_Fourier_transform . Unfortunately that $n-2$ factor complicates things a bit but if you take a discrete Fourier transform that sum (called a circular convolution) explicitly transforms into a product which is easier to work with. | |
| Nov 13, 2023 at 17:02 | comment | added | Sidharth Ghoshal | In the case of infinite discrete sums these also factor nicely the way they do in the continuous case (see the section labeled convolution theorem): eng.libretexts.org/Bookshelves/Electrical_Engineering/… | |
| Nov 13, 2023 at 16:59 | comment | added | mathoverflowUser | @SidharthGhoshal: Yes it looks like discrete convolution. I realised this also and am trying the discrete convolution also. Thanks for the hint! | |
| Nov 13, 2023 at 16:57 | comment | added | Sidharth Ghoshal | I haven’t verified the correctness of what you wrote but it’s worth noticing The RHS looks like a discrete convolution. I know in the continuous setting these things can be undone via Fourier transforms. Since you’re in the discrete setting I’m not sure how it goes but you might want to look at “discrete convolution”, “deconvolution”, and “discrete deconvolution”. In particular you want to call $b(r) = c_{r-1}$ then your formula becomes $(n-2)\pi(n) = \sum_{k=0}^{n-1} \pi(k)b(n-k)$ and that looks a discrete convolution to me | |
| Nov 13, 2023 at 16:56 | comment | added | mathoverflowUser | @MaxAlekseyev: Thanks for the hint. | |
| Nov 13, 2023 at 16:48 | comment | added | Max Alekseyev | As for Q2, see for example mathworld.wolfram.com/MeisselsFormula.html and mathworld.wolfram.com/LehmersFormula.html | |
| Nov 13, 2023 at 16:25 | history | edited | mathoverflowUser | CC BY-SA 4.0 |
updated because of ambiguous formulation
|
| Nov 13, 2023 at 16:23 | comment | added | mathoverflowUser | @StanleyYaoXiao: It means: I can prove the recurrence formula as stated. But I can not solve $\pi(n)$ for $c_n$: I would like to have a formula, where on the left there is $\pi(n)$ and on the right there is only $c_n$. | |
| Nov 13, 2023 at 16:15 | comment | added | Stanley Yao Xiao | "Which I can prove, but not yet solve" does not make any sense. | |
| Nov 13, 2023 at 12:44 | history | edited | mathoverflowUser | CC BY-SA 4.0 |
added link and comment
|
| Nov 13, 2023 at 12:27 | history | asked | mathoverflowUser | CC BY-SA 4.0 |