Apakah urutan rasional ini selalu mencapai bilangan bulat?

Dec 02 2020

Posting ini berasal dari saran Joel Moreira dalam komentar di Sebuah alternatif untuk pecahan lanjutan dan aplikasi (itu sendiri terinspirasi oleh video Numberphile 2.920050977316 dan Fridman, Garbulsky, Glecer, Grime, dan Tron Florentin - Konstanta representasi utama ).

Membiarkan $u_0 \ge 2$ menjadi rasional, dan $u_{n+1}=⌊u_n⌋(u_n - ⌊u_n⌋ + 1)$.
Pertanyaan : Apakah urutannya$(u_n)$ mencapai integer?

$\to$ lihat di bawah aplikasi untuk teori bilangan irasional.

Komentar : Itu benar untuk$u_0=\frac{p}{q}$ dengan $p \le 40000$ (Lihat Lampiran).

Proposisi : Itu selalu benar untuk$u_0 = \frac{p}{2}$.
Bukti dengan kontradiksi : Asumsikan bahwa urutan tidak pernah mencapai bilangan bulat, lalu$u_n = k_n + \frac{1}{2}$ untuk semua $n$. Selanjutnya perhatikan itu$u_{n+1} = k_n + \frac{k_n}{2}$, jadi $k_n$ pasti aneh untuk semua $n$. Biarkan menulis$k_n = 2 h_n +1$, kemudian $u_n = 2h_n+1+\frac{1}{2}$ (dengan $h_n \ge 1$) dan $u_{n+1} = 3h_n+1+\frac{1}{2}$. Ini mengikuti itu$2h_{n+1} = 3h_n$, dan sebagainya $h_n = (\frac{3}{2})^nh_0$, yang menyiratkan itu $2^n$ membagi $h_0$ untuk semua $n$, kontradiksi. $\square$

Untuk $u_0=\frac{11}{5}$, kemudian $$(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).$$ Berikut adalah gambaran dinamika tersebut:

Dengan memperhatikan (misalnya) kapan $u_0=\frac{15}{7}$ di bawah ini, kami menduga bahwa pembuktian umum seharusnya sulit. $(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)$

Untuk $u_0=\frac{10307}{4513}=\frac{k_0}{q}$, urutannya $(\frac{k_n}{q})=(u_n)$ mencapai bilangan bulat di $n=58254$. Urutannya$(u_n)$ mencapai bilangan bulat sekali $k_n \text{ mod } q=0$. Di bawah ini adalah gambar untuk$(n,k_n \text{ mod } q)$; itu terlihat sangat acak. Probabilitas untuk$s$ bilangan bulat acak antara $0$ dan $q-1$ tidak pernah menjadi nol adalah tentang $e^{-s/q}$ kapan $q$ cukup besar.

Aplikasi untuk teori bilangan irasional

Menurut makalah yang disebutkan di atas, ada batasan antara kumpulan angka$u_0 \ge 2$, dan kumpulan urutan $(a_n)$ seperti itu untuk semua $n$:

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

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

Bijection diberikan oleh: $$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}.$$Jawaban positif atas pertanyaan tersebut akan memberikan semacam alternatif untuk pecahan lanjutan , dalam arti cara alami untuk merepresentasikan angka, dengan karakterisasi lengkap dari angka irasional, yang di sini adalah itu.$\lim_{n \to \infty} (a_n)=\infty$.

Lampiran

Dalam daftar berikut datum $[r,(p,q)]$ berarti urutannya $(u_n)$, dengan $u_0=\frac{p}{q}$, mencapai bilangan bulat di $n=r$. Daftar tersebut menyediakan yang terpanjang$r$ menurut urutan leksikografik $(p,q)$.

Komputasi

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)]

Kode

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)])

Jawaban

10 BenBurns Dec 03 2020 at 11:19

Saya ingin meninggalkan beberapa komentar dasar, mungkin itu akan membantu.

Pertanyaannya menanyakan tentang relasi pengulangan

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

Misalkan Anda menulis rasional $u$ dalam hal bilangan asli $\frac{pq+r}{p}$. Kemudian$\lfloor u \rfloor = q$. Hubungan perulangannya sekarang

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

Oleh karena itu, kita dapat menyelidiki deret yang sama dalam bilangan asli $u_{n+1}=q_n(r_n + p)$ menanyakan kapan rangkaian tersebut menyatu dengan kelipatan $p$. Sekarang kita harus berurusan dengan$r_{n+1} = q_n * r_n \mod p$ dan $q_{n+1} = \lfloor u_{n+1} / p\rfloor$tapi biar saya tunjukkan manfaatnya. Pertama bandingkan dengan aslinya$u_0 = 11/5$.

Sekarang $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\\ $$

Urutan berlanjut tanpa batas sekali $r_n=0$.

Komentar kecil: $q_{n+1} \ge q_n$. Menurut definisi,$q_{n+1} = \lfloor u_{n+1} / p\rfloor \rightarrow \lfloor q_n(r_n + p) / p\rfloor$.

Komentar kecil: Tidak ada siklus panjang 1. Diperlukan sebuah siklus $q_{n+1}=q_n$ dan $r_{n+1}=r_n$. Sama$q_{n+1}$ menyiratkan $q_n * r_n \lt p$. Dan karena itu satu-satunya cara untuk$r_{n+1} =r_n$ adalah jika $q_n=1$, tapi itu wajib $q_n>2$ (menurut definisi di $u_0$).

Sekarang sketsa kasar menunjukkan bahwa "banyak" $u_0$bertemu. Pertimbangkan kapan$p=10$. Logika yang sama akan berlaku untuk yang lain$p$(bilangan prima dan komposit) tetapi analoginya di sini paling mudah. Catat itu$10=5*2$. Karena itu, kapan$u_n$ "melangkah" menjadi nilai-nilai $50-59$, separuh waktu (angka genap), langkah berikut akan dihentikan:

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

Ini juga akan menjadi kasus untuk nilai-nilai lain yang menjadi faktor $5*m$ (untuk $p=10$) seperti $150-159(=3*5), 250-259(=5*5)$ dll. Komposit lainnya $2*p$ berperilaku serupa, misalnya, $p=14$ lalu setengah dari $70-79$diakhiri dalam satu langkah. Ini dapat diterapkan pada faktor selain$2$. Selain itu, gagasan menemukan "zona akhir" juga berlaku untuk sejumlah$u_n$ untuk prime $p$, yang dapat dengan mudah diputuskan sebagai berakhir di area $p^2-p$. Misalnya, dengan$p=5$, lalu ada nilai $q_n=p-1$ dan beberapa $r$ seperti yang $p^2<u_n<p^2+p$; dalam contoh ini,$q_n=4,r_n=2\rightarrow 4*(5+2)=28$ dan urutannya berakhir setelahnya $5*(5+3)$.

Masih banyak kasus lain yang belum dibuktikan, tapi mungkin postingan ini bisa membantu.

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)$, kemudian $\{u_{n}\}_{n=1}^{+\infty}$ mencapai integer. $\quad (*)$

Ini bisa dibuktikan jika kita membuktikan,

$p$ utama, $t\in \mathbb{N}^{*}$ $p^{t} u_{0} \in \mathbb{N}^{*}$, $\left\{u_{k}\right\}_{n=1}^{+\infty}$mencapai integer. kami menyebutnya sebagai properti$I(p,t)$.

Mudah untuk memeriksa apakah kami terbukti $I(p,t)$ $\forall t\in \mathbb{N}^{*}$. $\forall p$ prima, $I(p,t)$ benar maka kami buktikan $ (*)$.

Sekarang kami memfokuskan diri untuk memperbaiki masalah $I(p,t)$, $p$ prime dan kami pertama-tama mempertimbangkan kasusnya $t=1$.

Kami mengubah skala urutan, melebarkannya dengan $p$, dan masih digunakan $u_k$ untuk mengekspresikan urutan baru, dan menuliskannya $p$-expension.

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

maka urutannya terpenuhi, $$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$

Dimana $a_k$ adalah $k$digit ke-dari $p$-pengeluaran $u$ dan $a_k(n)$ adalah $k$-digit $p$-pengeluaran $u_n$, lalu untuk sebelumnya $a_k$ kita punya $a_k=a_k(0)$.

Ucapan. Dan secara umum, kita tidak dapat menemukan rumus suku umum, (**) hanya berlaku untuk beberapa digit pertama$u_k$, berapa banyak digit yang dapat terlibat tergantung pada $u_0$, karena kita perlu menghindari membawa aritmatika.

kemudian $II(p, k)$ adalah properti berikut $$\left\{u_{n}\right\}_{n=1}^{+\infty}, \exists k\in \mathbb{N}^*, a_0(k)=0$$

Dan mudah untuk diperiksa $II(p, k)$ setara dengan $I(p, k)$, untuk semua $p$ utama, $k\in \mathbb{N}^*$.

Untuk $II(2, 1)$ kami beruntung case ini sangat spesial dan bisa di cek $II(2, 1)$ benar dengan cek langsung dulu $k$-digits dalam 2-expension $u_0$, yaitu $a_i(0)$, untuk $0\leq i\leq k$.

Jika 2 digit pertama $u_0$ adalah 10, lalu $II(2.1)$adalah benar.
Jika 3 digit pertama$u_0$ adalah 101, lalu $II(2.1)$adalah benar.
Jika 4 digit pertama$u_0$ adalah 1001, lalu $II(2.1)$ adalah benar.
$......$
Jika dulu $k$ digit dari $u_0$ adalah $1\underbrace{00...0}_{k-2}1$ , kemudian $II(2.1)$adalah benar. Jadi satu-satunya kasus$II(2.1)$ false adalah kapan $u_0=1$, yang sesuai dengan kasus aslinya $u_0$, $u_0=\frac{1}{2}$.