Erreichen diese rationalen Sequenzen immer eine ganze Zahl?

Dec 02 2020

Dieser Beitrag stammt aus dem Vorschlag von Joel Moreira in einem Kommentar zu Eine Alternative zu fortgesetzten Brüchen und Anwendungen (selbst inspiriert durch das Numberphile-Video 2.920050977316 und Fridman, Garbulsky, Glecer, Grime und Tron Florentin - Eine Konstante, die die Hauptrolle spielt ).

Lassen $u_0 \ge 2$ sei rational und $u_{n+1}=⌊u_n⌋(u_n - ⌊u_n⌋ + 1)$.
Frage : Tut die Sequenz$(u_n)$ eine ganze Zahl erreichen?

$\to$ siehe unten die Anwendung auf die irrationale Zahlentheorie.

Bemerkung : Es ist wahr für$u_0=\frac{p}{q}$ mit $p \le 40000$ (siehe Anhang).

Satz : Es ist immer wahr für$u_0 = \frac{p}{2}$.
Beweis durch Widerspruch : Nehmen wir an, dass die Sequenz dann niemals eine ganze Zahl erreicht$u_n = k_n + \frac{1}{2}$ für alle $n$. Nächste beachten Sie das$u_{n+1} = k_n + \frac{k_n}{2}$, so $k_n$ muss für alle ungerade sein $n$. Lass schreiben$k_n = 2 h_n +1$, dann $u_n = 2h_n+1+\frac{1}{2}$ (mit $h_n \ge 1$) und $u_{n+1} = 3h_n+1+\frac{1}{2}$. Es folgt dem$2h_{n+1} = 3h_n$, und so $h_n = (\frac{3}{2})^nh_0$, was das impliziert $2^n$ teilt $h_0$ für alle $n$, Widerspruch. $\square$

Zum $u_0=\frac{11}{5}$, dann $$(u_n)= (\frac{11}{5}, \frac{12}{5}, \frac{14}{5}, \frac{18}{5}, \frac{24}{5}, \frac{36}{5}, \frac{42}{5}, \frac{56}{5}, \frac{66}{5}, \frac{78}{5}, 24, \dots).$$ Hier ist ein Bild der Dynamik:

Indem wir (zum Beispiel) betrachten, wann $u_0=\frac{15}{7}$ Im Folgenden vermuten wir, dass der allgemeine Beweis schwierig sein sollte. $(u_n) = (\frac{15}{7}, \frac{16}{7}, \frac{18}{7}, \frac{22}{7}, \frac{24}{7}, \frac{30}{7}, \frac{36}{7}, \frac{40}{7}, \frac{60}{7}, \frac{88}{7}, \frac{132}{7}, \frac{234}{7}, \frac{330}{7}, \frac{376}{7}, \frac{636}{7}, \frac{1170}{7}, \frac{1336}{7}, \frac{2470}{7}, \frac{4576}{7}, \frac{7836}{7}, \frac{11190}{7}, \frac{17578}{7}, \frac{20088}{7}, \frac{34428}{7}, \frac{44262}{7}, \frac{50584}{7}, \frac{65034}{7}, \frac{102190}{7}, \frac{160578}{7}, 39324, \dots)$

Zum $u_0=\frac{10307}{4513}=\frac{k_0}{q}$, die Sequenz $(\frac{k_n}{q})=(u_n)$ erreicht eine ganze Zahl bei $n=58254$. Die Sequenz$(u_n)$ erreicht einmal eine ganze Zahl $k_n \text{ mod } q=0$. Unten ist das Bild für$(n,k_n \text{ mod } q)$;; es sieht völlig zufällig aus. Die Wahrscheinlichkeit für$s$ zufällige ganze Zahlen zwischen $0$ und $q-1$ niemals Null zu sein ist ungefähr $e^{-s/q}$ wann $q$ ist groß genug.

Anwendung auf die irrationale Zahlentheorie

Gemäß dem oben erwähnten Papier gibt es eine Bijektion zwischen dem Satz von Zahlen$u_0 \ge 2$und die Menge der Sequenzen $(a_n)$ so dass für alle $n$::

$a_n \in \mathbb{N}_{\ge 2}$,

$a_n \le a_{n+1} < 2a_n$.

Die Bijektion ist gegeben durch: $$u_0 \mapsto (a_n) \text{ with } a_n = ⌊u_n⌋ \text{ and } u_{n+1}=⌊u_n⌋(u_n - ⌊u_n⌋ + 1),$$ $$(a_n) \mapsto u_0 = \sum_{n=0}^{\infty}\frac{a_n-1}{\prod_{i=0}^{n-1}a_i}.$$Eine positive Antwort auf die Frage würde eine Art Alternative zum fortgesetzten Bruch im Sinne einer natürlichen Darstellung der Zahlen mit einer vollständigen Charakterisierung der irrationalen darstellen, was hier der Fall wäre$\lim_{n \to \infty} (a_n)=\infty$.

Blinddarm

In der folgenden Liste das Datum $[r,(p,q)]$ bedeutet, dass die Reihenfolge $(u_n)$mit $u_0=\frac{p}{q}$erreicht eine ganze Zahl bei $n=r$. Die Liste enthält die längsten$r$ gemäß der lexikografischen Reihenfolge von $(p,q)$.

Berechnung

sage: search(40120)
[1, (2, 1)]
[2, (5, 2)]
[3, (7, 2)]
[4, (7, 3)]
[11, (11, 5)]
[30, (15, 7)]
[31, (29, 14)]
[45, (37, 17)]
[53, (39, 17)]
[124, (41, 19)]
[167, (59, 29)]
[168, (117, 58)]
[358, (123, 53)]
[380, (183, 89)]
[381, (201, 89)]
[530, (209, 97)]
[532, (221, 97)]
[622, (285, 131)]
[624, (295, 131)]
[921, (359, 167)]
[1233, (383, 181)]
[1365, (517, 251)]
[1482, (541, 269)]
[2532, (583, 263)]
[3121, (805, 389)]
[3586, (1197, 587)]
[3608, (1237, 607)]
[3860, (1263, 617)]
[4160, (1425, 643)]
[6056, (1487, 743)]
[9658, (1875, 859)]
[9662, (1933, 859)]
[10467, (2519, 1213)]
[10534, (2805, 1289)]
[11843, (2927, 1423)]
[12563, (3169, 1583)]
[13523, (3535, 1637)]
[14004, (3771, 1871)]
[14461, (4147, 2011)]
[17485, (4227, 1709)]
[18193, (4641, 1987)]
[18978, (4711, 2347)]
[22680, (5193, 2377)]
[23742, (5415, 2707)]
[24582, (5711, 2663)]
[27786, (5789, 2837)]
[27869, (6275, 2969)]
[29168, (6523, 3229)]
[32485, (6753, 2917)]
[33819, (7203, 3361)]
[41710, (7801, 3719)]
[49402, (8357, 3863)]
[58254, (10307, 4513)]
[58700, (10957, 4943)]
[81773, (12159, 5659)]
[85815, (16335, 7963)]
[91298, (16543, 7517)]
[91300, (17179, 7517)]
[98102, (19133, 9437)]
[100315, (19587, 8893)]
[100319, (20037, 8893)]
[102230, (20091, 9749)]
[102707, (21289, 10267)]
[103894, (21511, 10151)]
[105508, (22439, 11149)]
[107715, (22565, 10729)]
[142580, (23049, 11257)]
[154265, (24915, 12007)]
[177616, (27461, 13421)]
[178421, (32063, 15377)]
[190758, (34141, 16547)]
[228068, (34783, 15473)]
[228876, (35515, 17477)]
[277844, (40119, 19391)]

Code

def Seq(p,q):
    x=Rational(p/q)
    A=[floor(x)]
    while not floor(x)==x:
        n=floor(x)
        x=Rational(n*(x-n+1))
        m=floor(x)
        A.append(m)
    return A

def search(r):
    m=0
    for p in range(2,r):
        for q in range(1,floor(p/2)+1):
            A=Seq(p,q)
            l=len(A)
            if l>m:
                m=l
                print([m,(p,q)])

Antworten

10 BenBurns Dec 03 2020 at 11:19

Ich möchte ein paar elementare Kommentare hinterlassen, vielleicht sind sie hilfreich.

Die Frage fragt nach der Wiederholungsbeziehung

$$ u_{n+1}= \lfloor u_n \rfloor (u_n − \lfloor u_n \rfloor + 1) $$

Angenommen, Sie schreiben rational $u$ in Bezug auf natürliche Zahlen $\frac{pq+r}{p}$. Dann$\lfloor u \rfloor = q$. Die Wiederholungsrelation ist jetzt

$$ u_{n+1} = q_n (\frac{pq_n+r_n}{p} − q_n + 1) \\ = q_n (\frac{pq_n+r_n− pq_n + p}{p} ) \\ = \frac{q_n(r_n + p)}{p} $$

Daher können wir dieselbe Reihe in natürlichen Zahlen untersuchen $u_{n+1}=q_n(r_n + p)$ Fragen, wann die Serie zu einem Vielfachen von konvergiert $p$. Jetzt müssen wir uns darum kümmern$r_{n+1} = q_n * r_n \mod p$ und $q_{n+1} = \lfloor u_{n+1} / p\rfloor$aber lassen Sie mich den Nutzen zeigen. Vergleichen Sie zuerst mit dem Original$u_0 = 11/5$.

Jetzt $p=5, q_0=2,r_0=1$.

$$ u_0 = 2*5 + 1 \\ u_{n+1} = 2*(5+1) = 12 \\ u_{n+2} = 2*(5+2) = 14\\ u_{n+3} = 2*(5+4) = 18\\ u_{n+4} = 3*(5+3) = 24\\ u_{n+5} = 4*(5+4) = 36\\ u_{n+5} = 7*(5+1) = 42\\ u_{n+6} = 8*(5+2) = 56\\ u_{n+7} = 11*(5+1) = 66\\ u_{n+8} = 13*(5+1) = 78\\ u_{n+9} = 15*(5+3) = 120\\ u_{n+10} = 24*(5+0) = 120\\ $$

Die Sequenz wird einmal auf unbestimmte Zeit fortgesetzt $r_n=0$.

Kleinere Bemerkung: $q_{n+1} \ge q_n$. Per Definition,$q_{n+1} = \lfloor u_{n+1} / p\rfloor \rightarrow \lfloor q_n(r_n + p) / p\rfloor$.

Kleinere Bemerkung: Es gibt keine Zyklen der Länge 1. Ein Zyklus würde erfordern $q_{n+1}=q_n$ und $r_{n+1}=r_n$. Das gleiche$q_{n+1}$ impliziert $q_n * r_n \lt p$. Und deshalb der einzige Weg für$r_{n+1} =r_n$ ist wenn $q_n=1$, aber es ist erforderlich $q_n>2$ (per definitionem auf $u_0$).

Nun eine grobe Skizze, die zeigt, dass "viele" $u_0$konvergieren. Überlegen Sie wann$p=10$. Die gleiche Logik gilt für andere$p$(Prime und Composite), aber die Analogie hier ist am einfachsten. Beachten Sie, dass$10=5*2$. Deshalb, wenn$u_n$ "Schritte" in Werte $50-59$In der Hälfte der Zeit (gerade Zahlen) wird der folgende Schritt beendet:

$$ 50 => 5*(10 + 0) => 50\\ 51 => 5*(10 + 1) => 55\\ 52 => 5*(10 + 2) => 60\\ 53 => 5*(10 + 3) => 65\\ 54 => 5*(10 + 4) => 70\\ 55 => 5*(10 + 5) => 75\\ 56 => 5*(10 + 6) => 80\\ 57 => 5*(10 + 7) => 85\\ 58 => 5*(10 + 8) => 90\\ 59 => 5*(10 + 9) => 95 $$

Dies gilt auch für andere Werte, die berücksichtigt werden $5*m$ (zum $p=10$) sowie $150-159(=3*5), 250-259(=5*5)$ usw. Andere Verbundwerkstoffe $2*p$ verhalten sich ähnlich, z. $p=14$ dann die Hälfte von $70-79$in einem Schritt beenden. Dies kann auf andere Faktoren als angewendet werden$2$. Darüber hinaus gilt diese Idee, "Endzonen" zu finden, auch für eine Reihe von$u_n$ für Prime $p$, die leicht als Beendigung im Bereich von entschieden werden kann $p^2-p$. Zum Beispiel mit$p=5$, dann gibt es einen Wert $q_n=p-1$ und einige $r$ so dass $p^2<u_n<p^2+p$;; in diesem Beispiel$q_n=4,r_n=2\rightarrow 4*(5+2)=28$ und die Sequenz endet nach $5*(5+3)$.

Es gibt noch viele andere Fälle zu beweisen, aber vielleicht war dieser Beitrag hilfreich.

1 katago Dec 17 2020 at 18:48

$u_{0} \in \mathbb{Q} \quad u_{n+1}=\left[u_{n}\right]\left(u_{n}-\left[u_{n}\right]+1\right)$, dann $\{u_{n}\}_{n=1}^{+\infty}$ erreichen in ganzzahl. $\quad (*)$

Dies kann bewiesen werden, wenn wir beweisen,

$p$ Prime, $t\in \mathbb{N}^{*}$ $p^{t} u_{0} \in \mathbb{N}^{*}$, $\left\{u_{k}\right\}_{n=1}^{+\infty}$eine ganze Zahl erreichen. Wir nennen dies als Eigentum$I(p,t)$.

Es ist leicht zu überprüfen, ob wir es bewiesen haben $I(p,t)$ $\forall t\in \mathbb{N}^{*}$. $\forall p$ Prime, $I(p,t)$ ist wahr, dann haben wir bewiesen $ (*)$.

Jetzt konzentrieren wir uns auf ein Problem, das behoben werden muss $I(p,t)$, $p$ prime und wir betrachten zuerst den Fall $t=1$.

Wir skalieren die Sequenz neu und erweitern sie mit $p$und immer noch verwenden $u_k$ um die neue Sequenz auszudrücken und einzuschreiben $p$-Erweiterung.

$ \quad u_{0} \longrightarrow p u_{0}, u_{0}=\sum_{k=0}^{+\infty} a_{k} p^{k}$

dann ist die Reihenfolge erfüllt, $$u_{n+1}=\left(\sum^{+\infty}_{k=0} a_{k+1}(n) p^{k}\right)\left(a_{0}(n)+p\right) \quad (**)$$

$\Rightarrow \quad a_{k}(n+1)=a_{0}(n) a_{k+1}(n)+a_{k}(n) . \quad \forall k \geqslant 0$

Wo $a_k$ ist der $k$-te Ziffer von $p$-Ausdehnung von $u$ und $a_k(n)$ ist der $k$-digit von $p$-Ausdehnung von $u_n$, dann für vorher $a_k$ wir haben $a_k=a_k(0)$.

Anmerkung. Und im Allgemeinen können wir die Formel des allgemeinen Ausdrucks nicht finden, (**) gilt nur für die ersten Ziffern von$u_k$, wie viele Ziffern es je nach geben kann $u_0$, weil wir arithmetisches Tragen vermeiden müssen.

dann $II(p, k)$ ist die folgende Eigenschaft $$\left\{u_{n}\right\}_{n=1}^{+\infty}, \exists k\in \mathbb{N}^*, a_0(k)=0$$

Und es ist leicht zu überprüfen $II(p, k)$ ist äquivalent zu $I(p, k)$, für alle $p$ Prime, $k\in \mathbb{N}^*$.

Zum $II(2, 1)$ Wir haben Glück, dass dieser Fall etwas ganz Besonderes ist und überprüft werden kann $II(2, 1)$ ist wahr, indem Sie direkt die erste überprüfen $k$-Ziffern in der 2-Expension von $u_0$dh $a_i(0)$, zum $0\leq i\leq k$.

Wenn die ersten 2 Ziffern von $u_0$ sind dann 10 $II(2.1)$ist wahr.
Wenn die ersten 3 Ziffern von$u_0$ sind dann 101 $II(2.1)$ist wahr.
Wenn die ersten 4 Ziffern von$u_0$ sind dann 1001 $II(2.1)$ ist wahr.
$......$
Wenn der erste $k$ Ziffern von $u_0$ sind $1\underbrace{00...0}_{k-2}1$ , dann $II(2.1)$ist wahr. Also der einzige Fall$II(2.1)$ falsch ist wann $u_0=1$, was dem Fall für Original entspricht $u_0$, $u_0=\frac{1}{2}$.