Do we have any Algos for these??

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

Do we have any Algos for these??

Post by MuthuVeerappanR »

$\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: 168
Joined: Fri Oct 21, 2016 5:53 pm

Re: Do we have any Algos for these??

Post by mclo »

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

Re: Do we have any Algos for these??

Post by MuthuVeerappanR »

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