Counting Square-Free Numbers

2011/07/25 by Jakub Pawlewicz, Pawlewicz, Jakub
Mathematics · Computer Science · #Benford’s Law and Fraud Detection #Computability, Logic, AI Algorithms

paper · pdf · doi:10.48550/arxiv.1107.4890

Abstract

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(√(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¹⁷. Using our implementation we were able to calculate the value for n=10³⁶ on a cluster.

Related

• Twins of s-free numbers
• A SWAR Approach to Counting Ones
• Algorithm to Compute Squares of 1st N Natural Numbers Without Using Multiplication
• A Fast Algorithm for Determining the Existence and Value of Integer Roots of N
• Square-free values of n²+n+1