Do we have any Algos for these??

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

Do we have any Algos for these??

Post by MuthuVeerappanR » Wed Jun 28, 2017 3:54 am

$\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.
Image
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.

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

Re: Do we have any Algos for these??

Post by mclo » Wed Jun 28, 2017 12:56 pm

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: 348
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

Re: Do we have any Algos for these??

Post by MuthuVeerappanR » Wed Jun 28, 2017 5:06 pm

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.
Image
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.

Post Reply