Take the 2-minute tour ×
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.

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|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 at 0:02
    
(or a list of comprime squarefree numbers in general) –  user2345215 Apr 20 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 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 at 8:59
1  
@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 at 9:09

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.