Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

While analysing the average runtime of an algorithm, I came across the following identity, and would like to know if anybody knows of any references for it?

For $i \in \mathbb{N}$, let $\bar{s}(i)$ denote the square-free part of $i$, eg., $\bar{s}(12) = 3$ (and $\bar{s}(1)=1$). Then $$ \lim_{n \rightarrow \infty} \frac{\sum_{i=1}^{n} \bar{s}(i)}{n^2} = \frac{\pi^2}{30}. $$

Many thanks.

share|improve this question
2  
You have $\prod_p (1+p/p^s+1/p^{2s}+p/p^{3s}+\cdots)$, alternately $1$ and $p$ in coefficients, and likely can write this as a $\zeta$ expression. –  Junkie Jun 8 '11 at 21:36
1  
I guess it is $\zeta(2s)\zeta(s-1)/\zeta(2s-2)$. –  Junkie Jun 8 '11 at 21:46
add comment

2 Answers 2

up vote 1 down vote accepted

The question asked for a reference, not a proof. A reference is Karl Greger, Square divisors and square-free numbers, Mathematics Magazine 51, No. 4 (Sept. 1978), 211-219. I make no claim that the result was unknown before Greger's paper.

share|improve this answer
    
Thanks Gerry, this is just what I was looking for. –  Granger Mar 20 '12 at 15:31
add comment

If my understanding is correct, for "squarefree part" can be "squarefree kernel" in other cases, the generating Dirichlet series is $${\zeta(2s)\zeta(s-1)\over\zeta(2s-2)}=\prod_p\biggl(1+{p\over p^s}+{1\over p^{2s}}+{p\over p^{3s}}+\cdots\biggr)=\sum_n{\bar s(n)\over n^s}$$ alternating $1$ and $p$ as the coefficients, which is a $\zeta$ quotient as indicated. The residue at $s=2$ is $\zeta(4)/\zeta(2)={\pi^4/90\over\pi^2/6}={\pi^2\over 15}$, so that by Perron's formula $$\sum_{n\le X} \bar s(n)={1\over 2\pi i}\int_{(\sigma)}{\zeta(2s)\zeta(s-1)\over\zeta(2s-2)}{X^s ds\over s} \sim {\zeta(4)\over 2\zeta(2)}X^2={\pi^4/90\over2\pi^2/6}X^2={\pi^2\over 30}X^2,$$ with usual conditions about convergence in vertical strips, which are OK here. Dividing by $X^2$ gives the desired limit.

share|improve this answer
3  
Junkie, by Perron's formula we have $$\sum_{n\le X} \bar s(n)=\int_{(3)}\frac{\zeta(2s)\zeta(s-1)}{\zeta(2s-2)}\frac{X^s}{s}\,ds\sim \frac{\pi^2}{30}X^2,$$ which is the limit conjectured by the OP. So there is no need to do any partial summation: the extra factor $2$ comes from the $s$ in the denominator of the integrand. –  GH from MO Jun 8 '11 at 22:41
    
Ah yes, you are right, and really there should be more fretting about convergence. –  Junkie Jun 8 '11 at 22:56
1  
Thanks guys, but I was only asking if to anyones knowledge this had been considered before (hence reference request). It's sufficiently natural that I thought it must be classical? –  Granger Jun 9 '11 at 9:35
1  
This is a standard exercise in analytic number theory, regardless if it had been considered before. You got a solution, use it and enjoy it. It is possible that there is a more elementary proof, using convolutions and the hyperbola method. –  GH from MO Jun 11 '11 at 4:20
3  
@GH - I think it is standard etiquette (and saves space) to determine whether or not a result is already in print, before contributing a proof. Therefore whether a result has been considered before is important. I think you and Junkie misunderstood what I was asking. As it is, writing `this is a standard exercise' would have been a sufficient answer, so thank you. –  Granger Jun 13 '11 at 16:50
show 2 more comments

Your Answer

 
discard

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.