$\text{rad}(n)$ is defined as the largest squarefree divisor of $n$.
Now, I have two questions. Is there a sublinear algorithm for the following two Summatory functions??
$R(n)=\displaystyle\sum_{k=1}^n \text{rad}(k)$
$P(n)=\displaystyle\sum_{k=1}^n \frac{k}{\text{rad}(k)}$
Any help is greatly appreciated. Thank you.
Do we have any Algos for these??

 Posts: 351
 Joined: Sun Mar 22, 2015 2:30 pm
 Location: India
 Contact:
Do we have any Algos for these??
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.
Re: Do we have any Algos for these??
Short answer is yes, it is at least possible to get the time down to $O(n^{\frac{1}{2}+\epsilon})$ for both functions.
Long answer looks like a major spoiler.
Long answer looks like a major spoiler.

 Posts: 351
 Joined: Sun Mar 22, 2015 2:30 pm
 Location: India
 Contact:
Re: Do we have any Algos for these??
Spoiler?? Apologies, I wouldn't have posted this question here had I known that...
I was working on converting DGFs to Summatory functions and these two functions have kind of weird DGFs and I was thinking whether it is possible..
I'll post in a different forum. Thanks mclo.
I was working on converting DGFs to Summatory functions and these two functions have kind of weird DGFs and I was thinking whether it is possible..
I'll post in a different forum. Thanks mclo.
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.