이 합리적인 시퀀스는 항상 정수에 도달합니까?

Dec 02 2020

이 게시물의 제안에서 비롯 조엘 모레이라 A의 의견 에 계속 분수 및 응용 프로그램에 대안 (자체는 Numberphile 비디오에서 영감을 2.920050977316 및 Fridman, Garbulsky, Glecer, 피부를 깨끗하게, 그리고 트론 플 로렌 - 대표적인-나타내는 상수 ).

허락하다 $u_0 \ge 2$ 합리적이며 $u_{n+1}=⌊u_n⌋(u_n - ⌊u_n⌋ + 1)$.
질문 : 순서가$(u_n)$ 정수에 도달합니까?

$\to$ 무리수 이론에 대한 적용 아래를 참조하십시오.

비고 : 사실입니다$u_0=\frac{p}{q}$ 와 $p \le 40000$ (부록 참조).

명제 : 항상 사실입니다.$u_0 = \frac{p}{2}$.
모순에 의한 증명 : 시퀀스가 정수에 도달하지 않는다고 가정하고$u_n = k_n + \frac{1}{2}$ 모든 $n$. 다음은$u_{n+1} = k_n + \frac{k_n}{2}$, 그래서 $k_n$ 모두에게 이상해야한다 $n$. 쓰자$k_n = 2 h_n +1$, 다음 $u_n = 2h_n+1+\frac{1}{2}$ (와 $h_n \ge 1$) 및 $u_{n+1} = 3h_n+1+\frac{1}{2}$. 그것은 다음과 같습니다$2h_{n+1} = 3h_n$, 등 $h_n = (\frac{3}{2})^nh_0$, 즉 $2^n$ 분할 $h_0$ 모든 $n$, 모순. $\square$

에 대한 $u_0=\frac{11}{5}$, 다음 $$(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).$$ 다음은 역학의 그림입니다.

(예 :) 언제 $u_0=\frac{15}{7}$ 아래에서 우리는 일반적인 증명이 어렵다고 생각합니다. $(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)$

에 대한 $u_0=\frac{10307}{4513}=\frac{k_0}{q}$, 시퀀스 $(\frac{k_n}{q})=(u_n)$ 정수에 도달 $n=58254$. 순서$(u_n)$ 한 번 정수에 도달 $k_n \text{ mod } q=0$. 아래는 사진입니다$(n,k_n \text{ mod } q)$; 완전히 무작위로 보입니다. 확률$s$ 사이의 임의의 정수 $0$ 과 $q-1$ 제로가되지 않는다는 것은 $e^{-s/q}$ 언제 $q$ 충분히 큽니다.

무리수 이론에 적용

위에서 언급 한 논문 에 따르면 , 숫자 집합 사이에는 이차가 있습니다.$u_0 \ge 2$및 시퀀스 세트 $(a_n)$ 모두를 위해 $n$:

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

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

bijection은 다음과 같이 제공됩니다. $$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}.$$질문에 대한 긍정적 인 대답 은 숫자를 자연스럽게 표현하는 의미에서 연속 분수에 대한 일종의 대안을 제공 하고 비합리적인 숫자의 완전한 특성화를 제공합니다.$\lim_{n \to \infty} (a_n)=\infty$.

부록

다음 목록에서 데이텀 $[r,(p,q)]$ 의미 시퀀스 $(u_n)$,와 함께 $u_0=\frac{p}{q}$에서 정수에 도달 $n=r$. 이 목록은 가장 긴$r$ 사전 순서에 따라 $(p,q)$.

계산

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

암호

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

답변

10 BenBurns Dec 03 2020 at 11:19

몇 가지 기본적인 의견을 남기고 싶습니다. 아마도 도움이 될 것입니다.

반복 관계에 대해 묻는 질문

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

당신이 합리적이라고한다면 $u$ 자연수의 관점에서 $\frac{pq+r}{p}$. 그때$\lfloor u \rfloor = q$. 되풀이 관계는 이제

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

따라서 자연수로 동일한 시리즈를 조사 할 수 있습니다. $u_{n+1}=q_n(r_n + p)$ 시리즈가 배수로 수렴하는지 묻습니다. $p$. 이제 우리는 처리해야$r_{n+1} = q_n * r_n \mod p$ 과 $q_{n+1} = \lfloor u_{n+1} / p\rfloor$하지만 이점을 보여 드리겠습니다. 먼저 원본과 비교$u_0 = 11/5$.

지금 $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\\ $$

시퀀스는 한 번 무기한 계속됩니다. $r_n=0$.

사소한 말 : $q_{n+1} \ge q_n$. 정의에 따르면$q_{n+1} = \lfloor u_{n+1} / p\rfloor \rightarrow \lfloor q_n(r_n + p) / p\rfloor$.

사소한 말 : 길이 1의주기는 없습니다. $q_{n+1}=q_n$ 과 $r_{n+1}=r_n$. 똑같다$q_{n+1}$ 암시 $q_n * r_n \lt p$. 따라서 유일한 방법은$r_{n+1} =r_n$ 만약 $q_n=1$이지만 필수입니다. $q_n>2$ (정의상 $u_0$).

이제 "다"를 보여주는 대략적인 스케치 $u_0$모이다. 언제 고려$p=10$. 동일한 논리가 다른$p$(프라임과 컴포지트) 그러나 여기서 비유가 가장 쉽습니다. 참고$10=5*2$. 따라서$u_n$ 값으로 "단계" $50-59$, 다음 단계의 절반 (짝수)이 종료됩니다.

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

이는 요인을 고려하는 다른 값의 경우에도 마찬가지입니다. $5*m$ (에 대한 $p=10$) 같은 $150-159(=3*5), 250-259(=5*5)$ 등 기타 합성물 $2*p$ 유사하게 행동합니다. $p=14$ 다음 절반 $70-79$한 단계로 종료됩니다. 이것은 다음 이외의 요인에 적용될 수 있습니다.$2$. 또한 "종료 영역"을 찾는이 아이디어는 여러$u_n$ 프라임 $p$의 영역에서 종료로 쉽게 결정할 수 있습니다. $p^2-p$. 예를 들어$p=5$이면 값이 있습니다. $q_n=p-1$ 그리고 일부 $r$ 그런 $p^2<u_n<p^2+p$; 이 예에서는$q_n=4,r_n=2\rightarrow 4*(5+2)=28$ 시퀀스는 $5*(5+3)$.

아직 입증되지 않은 다른 사례가 많이 있지만이 게시물이 도움이되었을 수 있습니다.

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)$, 다음 $\{u_{n}\}_{n=1}^{+\infty}$ 정수에 도달합니다. $\quad (*)$

우리가 증명한다면 증명할 수 있습니다.

$p$ 초기, $t\in \mathbb{N}^{*}$ $p^{t} u_{0} \in \mathbb{N}^{*}$, $\left\{u_{k}\right\}_{n=1}^{+\infty}$정수에 도달합니다. 우리는 이것을 재산이라고 부릅니다.$I(p,t)$.

우리가 증명했는지 확인하기 쉽습니다. $I(p,t)$ $\forall t\in \mathbb{N}^{*}$. $\forall p$ 프라임, $I(p,t)$ 사실이고 우리는 증명했습니다 $ (*)$.

이제 우리는 문제 해결에 집중합니다. $I(p,t)$, $p$ 소수이고 우리는 먼저 사건을 고려합니다 $t=1$.

시퀀스의 크기를 조정하고 $p$, 여전히 사용 $u_k$ 새로운 시퀀스를 표현하고 $p$-확장.

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

그런 다음 시퀀스가 만족되었습니다. $$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$

어디 $a_k$ 이다 $k$-번째 자리 $p$-확장 $u$ 과 $a_k(n)$ 이다 $k$-자리 $p$-확장 $u_n$, 다음 이전 $a_k$ 우리는 $a_k=a_k(0)$.

말. 그리고 일반적으로 일반 용어의 공식을 찾을 수 없습니다. (**)는 처음 몇 자리에만 해당됩니다.$u_k$, 다음에 따라 몇 자릿수가 포함될 수 있습니다. $u_0$, 우리는 산술적 캐리를 피해야하기 때문입니다.

그때 $II(p, k)$ 다음 속성입니다 $$\left\{u_{n}\right\}_{n=1}^{+\infty}, \exists k\in \mathbb{N}^*, a_0(k)=0$$

그리고 확인하기 쉽습니다. $II(p, k)$ 다음과 같다 $I(p, k)$, 모든 $p$ 초기, $k\in \mathbb{N}^*$.

에 대한 $II(2, 1)$ 이 사건은 매우 특별하고 확인할 수 있습니다. $II(2, 1)$ 첫 번째를 직접 확인하여 사실입니다. $k$-확장자가 2 개인 $u_0$, 즉 $a_i(0)$, for $0\leq i\leq k$.

의 처음 2 자리 $u_0$ 10이면 $II(2.1)$사실이다.
의 처음 3 자리$u_0$ 101이면 $II(2.1)$사실이다.
의 처음 4 자리$u_0$ 1001이면 $II(2.1)$ 사실이다.
$......$
첫 번째 경우 $k$ 자릿수 $u_0$ 아르 $1\underbrace{00...0}_{k-2}1$ , 다음 $II(2.1)$사실이다. 그래서 유일한 경우$II(2.1)$ 거짓은 언제 $u_0=1$, 원본의 경우에 해당 $u_0$, $u_0=\frac{1}{2}$.