[PYTHON] The mystery of the number that can be seen just by arranging 1s-The number of repunits and mysterious properties-

Introduction

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, R_1 = 1, R_2 = 11, R_3 = 111, R_4 = 1111, R_5 = 11111, ……… And so on. It's a very simple definition of the Repunit number, but it actually has some mysterious properties. In this article, let's take a look at the properties.

__ The content can be understood at the high school math level, so please relax your shoulders and enjoy! __

General term for Repunit number

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.

A beautiful theorem about the number of Repunits

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.

Pigeon house theory

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.

Proof

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 $.

(Bonus) Code

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.')

Repunit prime

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.

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}