Square-free numbers and the Moebius function: computational aspects

• Grant number: 13/11279-6
• Support Opportunities: Regular Research Grants
• Start date: October 01, 2013
• End date: September 30, 2015
• Field of knowledge: Physical Sciences and Mathematics - Mathematics - Analysis
• Principal Investigator: Fernando Auil
• Grantee: Fernando Auil
• Host Institution: Escola de Artes, Ciências e Humanidades (EACH). Universidade de São Paulo (USP). São Paulo , SP, Brazil

Abstract

In a recent paper, published in the Journal of Number Theory (stratum A1), the author of the present project introduces an algorithm that iteratively generates a sequence of natural numbers k_i and functions b_i, such that the number k_(i+1) is defined as the first discontinuity point of b_i which is greater than k_i. In the work cited, is proved in a mathematically rigorous way that the numbers k_i match the complete sequence of square-free numbers in increasing order, and that the value of the Moebius function mu(k_i) can be computed as mu(k_i) = b_i(k_(i+1)) - b_i(k_i). The goal of this project consists in the effective implementation of the algorithm to produce numerical results, with the purpose of analyzing their computational efficiency. The algorithm has an interest by itself: (1) from a theoretical standpoint, because the value of the Moebius function mu(k_i) is obtained with no prior knowledge of the factorization in primes of its argument, (2) from a computational standpoint, as numerical evidence, limited to 5x10^6, seems to suggest that the runtime is apparently polynomial. More specifically, quadratic or linear, depending on the implementation. (AU)