Timeline for When is $\lfloor C^n \rfloor \mod b$ efficiently computable?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 8, 2020 at 13:15 | comment | added | joro | @user44191 Could there be a pattern in "c(n)=a(An+B)"? | |
| Mar 8, 2020 at 12:13 | comment | added | user44191 | For the $\alpha$ I wrote above, there is a degree 6 relation that use only 4 terms that's true for sufficiently large $n$: if $b(n) = a(n + 3) - 2 a(n + 2) + a(n + 1) - a(n)$, then $\prod_{i = -2}^3 (b(n) - i) = 0$. This is because $b(n)$ is an integer and because $a(n) - \alpha^n$ is either very close to $0$ or very close to $-1$. | |
| Mar 8, 2020 at 8:04 | comment | added | joro | @user44191 I edited with partial results about the test. | |
| Mar 8, 2020 at 8:03 | history | edited | joro | CC BY-SA 4.0 |
Addressed comment
|
| Mar 7, 2020 at 21:30 | comment | added | user44191 | An example to test: the unique positive root of $x^3 - 2x^2 + x - 1$; I think that computing $\lfloor C^n \rfloor$ is equivalent to determining whether $n \text{arg}(\alpha')$ has positive cosine, where $\alpha'$ is either nonpositive root. | |
| Mar 7, 2020 at 19:18 | comment | added | user44191 | I should note that I assumed $\alpha$ is an algebraic integer. The above may be somewhat overly general; a sufficient restriction is that there is a unique conjugate of second-largest magnitude (which, necessarily, will be real). In that case, there will be a clear linear recurrence. It may still be possible to get a linear recurrence otherwise; I don't have any examples with 2 roots of the 2nd largest magnitude off the top of my head, but it might be worth investigating those. | |
| Mar 7, 2020 at 17:59 | comment | added | user44191 | For algebraic $\alpha$ such that $|\alpha| > 1, |\alpha'| < 1$ for all conjugates $\alpha'$, I suspect it should be easily computable; this is true for the examples given. | |
| Mar 7, 2020 at 17:49 | history | asked | joro | CC BY-SA 4.0 |