## Do we have any Algos for these??

Primes, divisors, arithmetic, number properties, ...
MuthuVeerappanR
Posts: 340
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

### Do we have any Algos for these??

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

It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.

mclo
Posts: 159
Joined: Fri Oct 21, 2016 5:53 pm

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

MuthuVeerappanR
Posts: 340
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.

It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.