Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

People often compete to beat the record for largest known prime (it is currently $2^{57,885,161}-1$). There are also big money prizes for finding explicit prime numbers exceeding specific magnitudes.

But what would happen if you searched for huge squarefree integers instead? Is a simple formula known which gives huge squarefree integers? As an example, if it was proved (unexpectedly) that all Fermat numbers $F_m = 2^{2^m}+1$ were squarefree, it would be trivial to find billion-digit squarefree numbers.

Since the asymptotic (natural) density of the squarefree numbers is $\frac{6}{\pi^2}\approx 61\%$ (while for the primes the density is zero), maybe it is much easier to find a simple formula for squarefree numbers?

(It is trivial to come up with a formula yielding huge non-squarefree numbers of course, and they constitute only $39\%$.)

I know one can use the sieve of Eratosthenes to generate a list of distinct primes and then take the product of the entire list (a "primorial" number), but can a simpler expression in one integer variable be found to yield only squarefree numbers?

share|cite|improve this question
Well huge squarefree search certainly won't be interesting, as it would just turn into the contest who has the biggest list of prime numbers, which is ridiculous. – user2345215 Apr 20 '14 at 0:02
(or a list of comprime squarefree numbers in general) – user2345215 Apr 20 '14 at 0:11
@user2345215 There could exist an efficient way of verifying that some huge number, like $2^{2^{65536}}+1$, was squarefree, without actually knowing its factorization (so without having that long list of prime numbers), could there not? If no, why not? – Jeppe Stig Nielsen Apr 20 '14 at 6:25
Maybe. But then it would be easy to prove e.g. $3$ is not a factor ($2^{2^{65536}}+1=4^{2^{65535}}+1\equiv1+1=2$), so we have a bigger squarefree number $3\cdot(2^{2^{65536}}+1)$. Do you see my point? – user2345215 Apr 20 '14 at 8:59
@user2345215 Yes, so maybe the record thing does not make much sense, but it is still interesting if some "simple" formula will generate squarefree integers only. – Jeppe Stig Nielsen Apr 20 '14 at 9:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.