Let's line up $ 1 $.
1, 11, 111, 1111, 11111, 111111, 11111111, 111111111, 1111111111, …
The natural number $ R_n $, which can be made by arranging $ n $ of $ 1 $ in this way, is called the __Repunit number __Repunit number __.
[^ 1]: The name Repunit comes from "Repeated" + "Unit (1)"
That is,
__ The content can be understood at the high school math level, so please relax your shoulders and enjoy! __
Given a sequence, it is the sadness of all humankind that makes us want to find the general term. So, let's first find the general term for the number of Repunits. Let's write the $ n $ number of Repunits as $ R_n = \ underbrace {1111 \ dots 11} _ {\ text {$ n $ digits}} $. At this time, $ R_n $ can be regarded as the sum of geometric progressions as follows.
\begin{align}
R_n &= \underbrace{1111 \dots 11}_{\text{$n$digit}} \\
&= 1 + 10 + 100 + \dotsb + \underbrace{1000…00}_{\text{$n$digit}} = \sum_{k = 0}^{n - 1}10^k
\end{align}
Therefore, from the formula of the sum of geometric progressions,
\begin{align}
R_n = \frac{10^n - 1}{9}
\end{align}
And I was able to find the general term.
This is what I wanted to write the most in this article. The following theorem holds for the number of Repunits [^ 2].
[^ 2]: AtCoder ABC174 C.Repsept has a problem with this theorem in the background.
The problem name is Repsept. , This seems to come from "Repeated" + "sept (7)"
Let __ $ n $ be a natural number with $ 2,5 $ as a prime factor .__ __ At this time, there is always a Repunit number divisible by $ n $ .__
For example ... If you take $ 3 $ as $ n $, you get $ R_3 = 111 $ as the number of Repunits divisible by $ 3 $. If you take $ 21 $ as $ n $, you get $ R_6 = 111111 $ as the number of Repunits divisible by $ 21 $. If you take $ 877 $ as $ n $, you get $ R_ {438} = \ underbrace {1111… 11} _ {\ text {438 digits}} $ as the number of Repunits divisible by $ 877 $.
It's beautiful. It's a theorem that's hard to imagine from that simple definition.
Let's prove this theorem in this chapter. Beautiful story of high school mathematics has a proof using Fermat's little theorem, but here I will adopt another approach.
Here, Hatosha theory This section explains. The claim is very simple.
Now suppose you have $ M $ feather pigeons and $ N (<M) $ aviaries.
Then, we will put the pigeons in each aviary. At this time, the statement is that there is a aviary with at least $ 2 $ or more of pigeons.
It seems obvious, but it is actually very powerful, and it is effective in various fields of mathematics.
This article also uses this pigeon house theory to prove the above theorem.
Let $ n $ be a natural number with $ 2,5 $ as a prime factor. Now consider $ n + 1 $ Repunit numbers $ R_1, R_2,…, R_ {n}, R_ {n + 1} $. There exists $ 1 \ leq i <j \ leq n + 1 $ which is $ R_j \ equiv R_i \ \ \ (\ mathrm {mod}. N) $ from the pigeon house theory. That is,
R_j - R_i \equiv 0 \ \ \ (\mathrm{mod}. n)
Is. At this time,
\begin{align}
R_j - R_i &= \frac{10^j - 1}{9} - \frac{10^i - 1}{9} \\
&= \frac{10^j - 10^i}{9} \\
&= 10^i \cdot \frac{10^{j - i} - 1}{9} \\
&= 10^i R_{j - i}
\end{align}
Because it can be calculated as
10^i R_{j - i} \equiv 0 \ \ \ (\mathrm{mod}. n)
Will be. Now, $ n $ is relatively prime to $ 10 $ because it doesn't have $ 2.5 $ as a prime factor,
R_{j - i} \equiv 0 \ \ \ (\mathrm{mod}. n)
Can be. Therefore, we were able to obtain the number of Repunits that can be divided by $ n $.
Here is the code to find the minimum number of Repunits that can be divisible by a number when you pass it as a command line argument. [^ 3]
[^ 3]: Even if I modify this code for $ 777… 77 $, it does not become TLE in AtCoder ABC174 C. Repsept
> Another device is required
get_repunit_length.py
import sys
def get_repunit_length(number):
if (number <= 0):
return -1
elif ((number % 2 == 0) or (number % 5 == 0)):
return 0
else:
repunit = 1
length = 0
while(True):
length += 1
if (repunit % number == 0):
return length
else:
repunit = repunit + 10 ** length
if __name__ == "__main__":
args = sys.argv
input = int(args[1])
result = get_repunit_length(input)
if (result == -1):
print("Please enter a natural number.")
elif (result == 0):
print(f'{input}There is no Repunit number divisible by.')
else:
print(f'{input}The minimum number of Repunits divisible by is R_{result}is.')
It's a bonus from here.
A Repunit number that is both a prime number and a prime number is called a __Repunit prime number _. For example, $ R_2 = 11 $ is a Repunit prime number. $ R {19} = 1111111111111111111 $ is also a Repunit prime number. What are the other Repunit prime numbers? The following table is posted on Wikipedia. Here, $ n $ means the $ n $ th Repunit number.
Year of discovery | discoverer | |
---|---|---|
- | - | |
- | - | |
- | - | |
1978 | Williams | |
1986 | Williams, Dubner | |
1999 | Dubner | |
2000 | Baxter | |
2007 | Dubner | |
2007 | Voznyy |
Only this $ 9 $ prime number is currently known. Repunit Whether there are an infinite number of prime numbers is an open question .
We don't know when the Repunit number will be prime, but we can do some research. For example, if $ n $ is a composite number, then $ R_n $ is also a composite number. [^ 4] [^ 4]: Please note that we do not claim that $ R_n $ is prime when __ $ n $ is prime __ This is immediately apparent from the following properties regarding the number of Repunits:
__ For natural numbers $ n, m $, if $ m $ is divisible by $ n $, then $ R_m $ is divisible by $ R_n $ .__
Please consider proof of the above properties. I will write it here as well, so please use it as an answer.
\begin{align}
R_{n} &= \frac{10^n - 1}{9} \\
&= \frac{10^{km} - 1}{9} \\
&= \frac{(10^m)^k - 1}{9} \\
&= \frac{(10^m - 1)(10^{m(k - 1)} + 10^{m(k - 2)} + \cdots + 1)}{9} \\
&= (10^{m(k - 1)} + 10^{m(k - 2)} + \cdots + 1)R_{m}
\end{align}
Then, $ (10 ^ {m (k − 1)} + 10 ^ {m (k − 2)} + \ cdots + 1) $ is a natural number, so $ R_m $ is divisible by $ R_n $.
Mathematics is really interesting. Of course, most of the fields are challenging by making full use of gorigori analysis, algebra, and topology, and the problem setting itself is quite advanced. But that's not all. For example, just by arranging the numbers appropriately or exchanging the numbers like this time, there are gorgeous gems of mathematics sleeping there. [^ 5] [^ 5]: The secret of the combination hidden in trigonometric functions But you just arranged the numbers in a zigzag pattern (promotion) I think this is amazing. It might be a good idea to play a few games once in a while and play with your own math. __ If you have any interesting themes or discoveries, please let us know! __
Recommended Posts