1

Given a number consisting of digits all equal to 1 in base 10 and not equal to 1 or 11, is it necessarily composite? I know that 11 is the smallest non-trivial counter-example, but I would like to know if it is the only counter-example. If not, what is the second to smallest counter-example? If this is difficult to find, can you prove its existence?

vosov
  • 113
  • 4
    There are more. – Daniel Fischer Aug 24 '15 at 12:44
  • 1
    see http://oeis.org/A004023 – mathlove Aug 24 '15 at 12:45
  • Interestingly, the relevant oeis.org page states that only the first five repunits (2, 19, 23, 317, and 1031 digits) have been proved prime as of August 2014. – vosov Aug 24 '15 at 13:04
  • @vosov the next candidate as more than $49,000$ digits. I genuinely wonder if there's a "quick" way to check if it's prime. – Ben Grossmann Aug 24 '15 at 13:19
  • @Omnomnomnom: Dubner says that the only viable way to prove primality for a number of this size is the BLS test, but we'd need to know more of the factorization of 10^49080-1 before we could do this -- we need ~33% but we have only ~16% now. – Charles Aug 24 '15 at 14:47
  • @Omnomnomnom This is silly, but it never quite occured to me that, even though we have found prime numbers far larger than this, it is not feasible to check a given number of this magnitude for primality. I always figured that numbers of the form $2^n-1$ were only searched because they are somewhat likely candidates for primality, not because they are easier to check. – vosov Aug 25 '15 at 13:44
  • @vosov factoring big numbers is hard. This fact is essential for certain kinds of encryption (which include, for example, email encryption systems). – Ben Grossmann Aug 25 '15 at 13:46

1 Answers1

1

The next-smallest counterexample, as indicated in the links from the comments, is given by $$ R_{19} = \sum_{i=0}^{18}10^i = \overbrace{1 \cdots 1}^{19} $$ it is conjectured (but has not been proven) that there are infinitely many such primes.

It is notable that $R_n = \sum_{i=0}^{n-1}10^i$ can be written in the form $$ R_n = \frac{10^{n} - 1}{9} $$ From this presentation, one may more easily deduce that $R_n$ can only be prime if $n$ is prime (though the converse doesn't hold).

Ben Grossmann
  • 225,327