Timeline for Consider a sequence $a_i=p \mod a_{i-1}$, where $p$ is a prime number, how to estimate the smallest $i$ where $a_i=1$? [duplicate]
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 15, 2018 at 10:56 | history | closed |
Kevin P. Costello Max Alekseyev CommunityBot |
Duplicate of improving known bounds for Pierce expansions; cash prize | |
| Feb 8, 2018 at 9:33 | review | Close votes | |||
| Feb 8, 2018 at 21:27 | |||||
| Feb 7, 2018 at 21:05 | comment | added | Ravi Boppana | Jeffrey Shallit has asked essentially the same question (with partial results and a cash prize) here: mathoverflow.net/questions/164129/… | |
| Feb 7, 2018 at 11:57 | answer | added | Chris Wuthrich | timeline score: 1 | |
| Feb 7, 2018 at 9:22 | comment | added | zbh2047 | Is there a tight bound of $p$? $\sqrt p$ is about 3000 when $p=10^7$, but results shows that it is never larger than 50. | |
| Feb 6, 2018 at 16:02 | comment | added | Gerhard Paseman | It is likely that the answer is $O(\sqrt{p})$. Note that for a_j greater than $\sqrt{p}$ that the difference between successive a_j grows by a multiplicative factor, so it takes roughly $(\log p)^2$ at most to get a_j down to $\sqrt{p}$. I imagine the rest of the journey to 1 is almost as quick. Gerhard "Look At The Step Size" Paseman, 2018.02.06. | |
| Feb 6, 2018 at 12:48 | comment | added | zbh2047 | I want a bound which only depends on $p$. That is, for any $0<a_0<p$, the bound is always correct. Your understanding and modification is really helpful. Thanks! | |
| Feb 6, 2018 at 12:43 | comment | added | zbh2047 | I mean the only $i$ such that $a_i=1$. In fact, I just wonder why such $i$ are always small, for any $p$ and $a_0$. I guess such $i$ is equal to $O(\log p)$, for example. | |
| Feb 6, 2018 at 11:39 | comment | added | Chris Wuthrich | I had the same question. Probably my edit was not useful. There is a unique $i$ such that $a_i=1$. Do you want a bound on $i$ depending on $p$ and $a_0$ or only on $p$? The latter would rather be the "largest" $i$ for a fixed $p$ and varying $a_0$. | |
| Feb 6, 2018 at 11:26 | comment | added | Gerry Myerson | If $a_i=1$, then $a_{i+1}=0$, and $a_{i+2}$ is undefined, so the smallest $i$ such that $a_i=1$ is the only $i$ such that $a_i=1$. Or do you mean the smallest $i$ as you vary $a_0$, keeping $p$ fixed? | |
| Feb 6, 2018 at 11:14 | history | edited | Chris Wuthrich | CC BY-SA 3.0 |
deleted 44 characters in body
|
| Feb 6, 2018 at 10:28 | history | asked | zbh2047 | CC BY-SA 3.0 |