# Fast method for Nth Squarefree number (using mathematica)

I am trying to compute Nth Squarefree numbers using Mathematica. What I am trying to utilize is the SquareFreeQ[i] function.

Here is my solution :

NSqFree[N_] := For[n = 1; i = 1, n <= N + 1, If[SquareFreeQ[i], If[n == N, Print[i] ] n++] i++]

But I am supposed to compute NSqFree[1000000000] but seems like my approach is taking for ever. Any faster method ?

Thanks,

ADDED:

Here an exactly identical topcoder question and the corresponding editorial for the same.

-

## 4 Answers

You have to us the Inclusion-Exclusion principle: suppose you want to find the number of square free numbers up to $N$, then from $N$ you have to substract the number of integers divisible by the square of a prime, but then you have to add any multiple of the square of the product of two discinct primes and so on, in formulas the number looked for is $$N - \sum_{p^2 \le N} \left\lfloor\frac{N}{p^2}\right\rfloor + \sum_{p^2q^2 \le N} \left\lfloor\frac{N}{p^2q^2}\right\rfloor - \sum_{p^2q^2r^2 \le N} \left\lfloor\frac{N}{p^2q^2r^2}\right\rfloor + \cdots -\cdots$$ using the moebius $\mu$ function you can write this last formula as $$\sum_{n \le \sqrt{N}} \mu(n) \left\lfloor\frac{N}{n^2}\right\rfloor$$ I don't know how to write this in mathematica but it should take a negligible fraction of the time it takes your current method.

-
But my problem is to find the exact Nth Square free number not the number of square free numbers up to N,I have used your idea in here and here but I am not getting how to use the same formula to get the exactly Nth square free number. – VelvetThunder Feb 5 '11 at 18:42
Okay I guess I got my answer and here is the explanation. – VelvetThunder Feb 5 '11 at 18:50
I'm sorry, I had misunderstood the question. But you can use the same formula combined with a binary search. It will take only a few applications of the formula. – Esteban Crespi Feb 5 '11 at 18:52

You won't do a billion (if I counted the zeros right) loops any time soon, so you need a better approach. Wikipedia has an approximation under the section Distribution of square-free numbers. So you could start with $10^9 \pi^2/6$ and calculate how many below that are square-free, then correct from there. You will need to use inclusion/exclusion, but there are only about 40,000 to consider.

-

I'm not an expert of number-theoretic algorithms, but it seems to me that you can employing the Chinese Remainder Theorem to obtain a decent first stab at a "sieving" algorithm.

• Use several registers r[p], each storing a residue modulo p2 for some prime p. Define such a register for various small primes p ∈ {2, 3, 5, ... , P} for some suitably large prime P. You will use these to represent an integer R, such that R ≡ r[p] (mod p2). You shouldn't need too many such registers to faithfully represent even reasonably large non-negative numbers (the registers can uniquely determine any integer from 1 to 22 × 32 × 52 × ... × P2).

• Whenever you wish to increment R, increment each of the registers r[p] as well. If R is square-free, none of these registers will be zero modulo the square of the appropriate prime. For sufficiently small integers N, you can even characterize N as being square-free if none of these residues are zero. Put another way, the more registers r[p] you maintain, the larger the range of square-free numbers you can automatically detect using these registers.

Suppose that you want to test for square-freeness up to some upper limit N. What do you need to test square-freeness using nothing but registers such as I've described? What you need is for any composite number less than N to have a prime factor from the list of registers that you maintain; that is, you need registers for each of the primes up to √N.

If you're going to iterate through all integers anyway, you can discover the list of primes that you need to characterize square-freeness at the same time by the Sieve of Erasthotenes, and construct the list of residues modulo squares-of-primes as you go. Any time you find a new prime P, so long as P2 < N, add P to the list of primes for which you maintain registers and initialize a register for residues modulo P2.

As Ross suggests in his answer, you can use results on the distribution of square-free numbers to obtain an upper bound for the Nth square-free number (it should grow more slowly than N ln(N) or so, in any case). This gives you an upper bound on the number of registers that you have to maintain as you search for square-free integers.

From this, you should actually be able to show a polynomial-time asymptotic upper bound on the runtime of your procedure.

-

I think that your method can be improved by sieving: if $n$ is not squarefree you don't need to check any of its multiples. Start with a reasonable estimate (like the one Ross Millikan gave) and sieve like you would do in a prime sieve.

Is this viable? I don't know! I can't program in Mathematica, but later today I'll try to implement this in Python.

-