[PYTHON] Das Geheimnis der Zahl, die nur durch Anordnen von 1s gesehen werden kann - Die Anzahl der Wiederholungen und die mysteriöse Natur -

Einführung

Lassen Sie uns $ 1 $ ausrichten. 1, 11, 111, 1111, 11111, 111111, 11111111, 111111111, 1111111111, … Die natürliche Zahl $ R_n $, die durch Anordnen von $ 1 $ auf diese Weise angeordnet werden kann, heißt __Repunit-Nummer (Repunit-Nummer) __. [^ 1] [^ 1]: Der Name Repunit stammt von "Repeated" + "Unit (1)". Das ist, R_1 = 1, R_2 = 11, R_3 = 111, R_4 = 1111, R_5 = 11111, ……… Und so weiter. Es ist eine sehr einfache Definition der Repunit-Zahl, aber sie hat tatsächlich einige mysteriöse Eigenschaften. In diesem Artikel werfen wir einen Blick auf die Eigenschaften.

__ Der Inhalt kann auf der Mathematikstufe der High School verstanden werden. Bitte entspannen Sie Ihre Schultern und genießen Sie! __ __

Allgemeiner Begriff für die Repunit-Nummer

Bei einer Folge von Zahlen ist es die Traurigkeit der gesamten Menschheit, dass man den allgemeinen Begriff finden möchte. Lassen Sie uns also zuerst den allgemeinen Begriff für die Anzahl der Repunits finden. Schreiben wir die $ n $ -te Repunit-Nummer als $ R_n = \ underbrace {1111 \ dots 11} _ {\ text {$ n $ digit}} $. Zu diesem Zeitpunkt kann $ R_n $ wie folgt als die Summe von Sequenzen mit gleichem Verhältnis betrachtet werden.

\begin{align}
R_n &= \underbrace{1111 \dots 11}_{\text{$n$Ziffer}} \\
&= 1 + 10 + 100 + \dotsb + \underbrace{1000…00}_{\text{$n$Ziffer}} = \sum_{k = 0}^{n - 1}10^k
\end{align}

Aus der Formel der Summe der Sequenzen mit gleichem Verhältnis ergibt sich daher

\begin{align}
R_n = \frac{10^n - 1}{9}
\end{align}

Und ich konnte den allgemeinen Begriff finden.

Schöner Satz über die Anzahl der Repunits

Das wollte ich am liebsten in diesem Artikel schreiben. Der folgende Satz gilt für die Anzahl der Repunits [^ 2].

[^ 2]: AtCoder ABC174 C.Repsept hat ein Problem mit diesem Theorem im Hintergrund.
Der Problemname lautet Repsept. , Dies scheint von "Wiederholt" + "Sept (7)" zu kommen.

Sei __ $ n $ eine natürliche Zahl mit $ 2,5 $ als Primfaktor .__ __ Zu diesem Zeitpunkt gibt es immer eine Repunit-Nummer, die durch $ n $ teilbar ist .__

Zum Beispiel ... Wenn Sie $ 3 $ als $ n $ nehmen, erhalten Sie $ R_3 = 111 $ als die Anzahl der durch $ 3 $ teilbaren Repunits. Wenn Sie $ 21 $ als $ n $ nehmen, erhalten Sie $ R_6 = 111111 $ als die Anzahl der durch $ 21 $ teilbaren Repunits. Wenn Sie $ 877 $ als $ n $ nehmen, erhalten Sie $ R_ {438} = \ underbrace {1111… 11} _ {\ text {438 Stellen}} $ als Anzahl der durch $ 877 $ teilbaren Repunits.

Es ist wunderschön. Es ist ein bezaubernder Satz, den man sich aus dieser einfachen Definition nicht vorstellen kann.

Lassen Sie uns diesen Satz in diesem Kapitel beweisen. Schöne Geschichte der Mathematik an der High School hat einen Beweis unter Verwendung des kleinen Satzes von Fermat, aber hier werde ich einen anderen Ansatz verfolgen.

Taubenhaus-Theorie

Hier Hatosha-Theorie Dieser Abschnitt erklärt. Der Anspruch ist sehr einfach.

Angenommen, Sie haben $ M $ Federtauben und $ N (<M) $ Volieren.

Dann werden wir die Tauben in jede Voliere legen. Derzeit heißt es, dass es eine Voliere mit mindestens 2 USD oder mehr Tauben gibt.

Es scheint offensichtlich, aber es ist tatsächlich sehr mächtig und es ist in verschiedenen Bereichen der Mathematik wirksam.

Dieser Artikel verwendet auch diese Taubenhaus-Theorie, um den obigen Satz zu beweisen.

Beweis

Sei $ n $ eine natürliche Zahl mit $ 2,5 $ als Primfaktor. Betrachten Sie nun $ n + 1 $ Repunit-Zahlen $ R_1, R_2,…, R_ {n}, R_ {n + 1} $. Es gibt $ 1 \ leq i <j \ leq n + 1 $, was $ R_j \ equiv R_i \ \ \ (\ mathrm {mod}. N) $ aus der Taubenhaus-Theorie ist. Das ist,

R_j - R_i \equiv 0 \ \ \ (\mathrm{mod}. n) 

Ist. In diesem Moment,

\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}

Weil es berechnet werden kann als

10^i R_{j - i} \equiv 0 \ \ \ (\mathrm{mod}. n)

Wird sein. Jetzt hat $ n $ nicht $ 2.5 $ als Primfaktor, also ist es Primzahl auf $ 10 $,

R_{j - i} \equiv 0 \ \ \ (\mathrm{mod}. n)

Kann sein. Daher konnten wir die Anzahl der Repunits ermitteln, die durch $ n $ geteilt werden können.

(Bonus-Code

Hier ist der Code, um die Mindestanzahl von Repunits zu ermitteln, die durch eine Zahl geteilt werden können, wenn Sie eine Zahl als Befehlszeilenargument übergeben. [^ 3]

[^ 3]: Auch wenn ich diesen Code für $ 777… 77 $ ändere, wird AtCoder ABC174 C. Repsept nicht als TLE <br übergeben > Eine andere Idee ist erforderlich

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("Bitte geben Sie eine natürliche Nummer ein.")
    elif (result == 0):
        print(f'{input}Es gibt keine durch Teilen teilbare Repunit-Nummer.')
    else:
        print(f'{input}Die Mindestanzahl der durch teilbaren Repunits ist R._{result}ist.')

Repunit prime

Es ist ein Bonus von hier.

Eine Repunit-Nummer, die sowohl eine Primzahl als auch eine Primzahl ist, wird als _Repunit-Primzahl __ bezeichnet. Zum Beispiel ist $ R_2 = 11 $ eine Repunit-Primzahl. Außerdem ist $ R {19} = 11111111111111111 $ eine Repunit-Primzahl. Was sind die anderen Repunit-Primzahlen? Die folgende Tabelle ist auf Wikipedia veröffentlicht. Hier bedeutet $ n $ die $ n $ -te Repunit-Nummer.

Derzeit ist nur diese 9-Dollar-Primzahl bekannt. Repunit Ob es unzählige Primzahlen gibt, ist eine offene Frage .

Wir wissen nicht, wann die Repunit-Zahl die Primzahl sein wird, aber wir können einige Nachforschungen anstellen. Wenn beispielsweise $ n $ eine zusammengesetzte Zahl ist, ist $ R_n $ auch eine zusammengesetzte Zahl. [^ 4] [^ 4]: Bitte beachten Sie, dass wir nicht behaupten, dass $ R_n $ eine Primzahl ist, wenn __ $ n $ eine Primzahl __ ist Dies ergibt sich sofort aus den folgenden Eigenschaften hinsichtlich der Anzahl der Repunits:

__ Für natürliche Zahlen $ n, m $ ist $ R_m $ durch $ R_n $ teilbar, wenn $ m $ durch $ n $ teilbar ist .__

Bitte beachten Sie den Nachweis der oben genannten Eigenschaften. Ich werde es auch hier schreiben, also benutze es bitte als Antwort.

\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}