Counting Square-Free Numbers

Details Counting Square-Free Numbers Counting Square-Free Numbers

2011-07-25

arxiv.org/abs/1107.4890v1

Mathematics

Number Theory

Scientific paper

The main topic of this contribution is the problem of counting square-free numbers not exceeding $n$. Before this work we were able to do it in time (Comparing to the Big-O notation, Soft-O ($\softO$) ignores logarithmic factors) $\softO(\sqrt{n})$. Here, the algorithm with time complexity $\softO(n^{2/5})$ and with memory complexity $\softO(n^{1/5})$ is presented. Additionally, a parallel version is shown, which achieves full scalability. As of now the highest computed value was for $n=10^{17}$. Using our implementation we were able to calculate the value for $n=10^{36}$ on a cluster.

Affiliated with

Also associated with

No associations

Rating

Counting Square-Free Numbers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Counting Square-Free Numbers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting Square-Free Numbers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-572330