Next prime after 11 is 1111111111111111111
· 🕒
I thought about this in a sauna at a hot spring:
Is 111 prime?
No, it is divisible by 3.
What about 1111?
This looks like a prime. It is not divisible by 3, 5, or 7. But no. It has a factorization: 1111 = 11 \cdot 101.
What about 11111? Then I got overheated.
Later, I became interested in palindromes in language, which led me to study numbers as strings in math.
| Examples | Name | Prime only if | OEIS | Regex |
|---|---|---|---|---|
| 11, 111, 1111 | repunit R_n | n is prime | A002275 | 1+ |
| 111, 222, 3333 | repdigit | repunit1 | A010785 | (.)\1* |
| 123, 234, 5678 | A138141 | |||
| 121, 1221, 12321 | palindromic number | length is odd2 | A002113 | |
| 101, 1001, 10001 | of the form 10^{2^n} + 1 | A000533 | 10*1 |
Repunits
A number of the form 11...1 is called a repunit, denoted R_n, where n is the number of 1s.
If n is composite, then R_n is divisible by R_k, where k is a factor of n. For example, R_9 = 111,111,111 is divisible by R_3 = 111.
Therefore, R_n is prime only if n is prime.
R_2 = 11 is prime, but neither R_3 nor R_5 is. The next primes are R_{19} and R_{23}, followed by R_{317}.
Repdigits
A number like 111, 222, or 3333 is called a repdigit. Every repunit is a repdigit.
Repdigits are not prime (except for repunit primes and single-digit primes) because they are divisible by a repunit, e.g., 777 = 7 \cdot 111.