Skip to main content
MathOverflow

Return to Question

Post Closed as "Not suitable for this site" by Peter Taylor, abx, Gro-Tsen, Emil Jeřábek, Gerry Myerson
`mod10` -> `\bmod{10}`
Source Link
LSpice
LSpice
  • 12.9k
  • 4
  • 45
  • 69

I have been playing around with integer sequences as of late, and the following question occurred to me:

Suppose for $m$ fixed we have some some initial values $a_1,\cdots,a_m$ and for all $n\in\mathbb{N}:n>m$ we have a linear recurrence relation $a_n=\sum_{i=1}^{m}\alpha_i a_{n-i}$ with $\alpha_i\in\mathbb{Z}$ (we could generalise to non-linear recurrence relations, but we focus on linear ones for the time being). Suppose we define $b_n\equiv a_n mod10$$b_n\equiv a_n \bmod{10}$ with $0\leq b_n\leq9$ and define the decimal expansion of $x$ by the concatenation $0.b_1b_2b_3\cdots$. Which recurrence relations give $x\in\mathbb{Q}$? Which give $x\notin\mathbb{Q}$? Which $x$ are normal?

I then realised (an embarrassingly long time after initially formulating this problem) that $x$ is rational if and only if its decimal expansion is repeating after some finite number of digits or terminating (i.e. repeated zeroes after some finite number of digits), so this question essentially reduces to whether a given recurrence relation is periodic (after some finite number of 'leading terms') when reduced mod10. Computationally it is easier to reduce each term mod10 as it is calculated.

I have been playing around with the Fibonacci sequence (OEIS A000045) and the example $a_n=a_{n-1}-a_{n-4}, a_1=a_2=a_3=a_4=1$ (which is sadly not documented on OEIS) but without much clue of how to check if values reoccur or not.

Does anyone have any insights into this problem? Is it too broad to be solved in general? Are there any interesting cases you can think of and wish to highlight?

I have been playing around with integer sequences as of late, and the following question occurred to me:

Suppose for $m$ fixed we have some some initial values $a_1,\cdots,a_m$ and for all $n\in\mathbb{N}:n>m$ we have a linear recurrence relation $a_n=\sum_{i=1}^{m}\alpha_i a_{n-i}$ with $\alpha_i\in\mathbb{Z}$ (we could generalise to non-linear recurrence relations, but we focus on linear ones for the time being). Suppose we define $b_n\equiv a_n mod10$ with $0\leq b_n\leq9$ and define the decimal expansion of $x$ by the concatenation $0.b_1b_2b_3\cdots$. Which recurrence relations give $x\in\mathbb{Q}$? Which give $x\notin\mathbb{Q}$? Which $x$ are normal?

I then realised (an embarrassingly long time after initially formulating this problem) that $x$ is rational if and only if its decimal expansion is repeating after some finite number of digits or terminating (i.e. repeated zeroes after some finite number of digits), so this question essentially reduces to whether a given recurrence relation is periodic (after some finite number of 'leading terms') when reduced mod10. Computationally it is easier to reduce each term mod10 as it is calculated.

I have been playing around with the Fibonacci sequence (OEIS A000045) and the example $a_n=a_{n-1}-a_{n-4}, a_1=a_2=a_3=a_4=1$ (which is sadly not documented on OEIS) but without much clue of how to check if values reoccur or not.

Does anyone have any insights into this problem? Is it too broad to be solved in general? Are there any interesting cases you can think of and wish to highlight?

I have been playing around with integer sequences as of late, and the following question occurred to me:

Suppose for $m$ fixed we have some some initial values $a_1,\cdots,a_m$ and for all $n\in\mathbb{N}:n>m$ we have a linear recurrence relation $a_n=\sum_{i=1}^{m}\alpha_i a_{n-i}$ with $\alpha_i\in\mathbb{Z}$ (we could generalise to non-linear recurrence relations, but we focus on linear ones for the time being). Suppose we define $b_n\equiv a_n \bmod{10}$ with $0\leq b_n\leq9$ and define the decimal expansion of $x$ by the concatenation $0.b_1b_2b_3\cdots$. Which recurrence relations give $x\in\mathbb{Q}$? Which give $x\notin\mathbb{Q}$? Which $x$ are normal?

I then realised (an embarrassingly long time after initially formulating this problem) that $x$ is rational if and only if its decimal expansion is repeating after some finite number of digits or terminating (i.e. repeated zeroes after some finite number of digits), so this question essentially reduces to whether a given recurrence relation is periodic (after some finite number of 'leading terms') when reduced mod10. Computationally it is easier to reduce each term mod10 as it is calculated.

I have been playing around with the Fibonacci sequence (OEIS A000045) and the example $a_n=a_{n-1}-a_{n-4}, a_1=a_2=a_3=a_4=1$ (which is sadly not documented on OEIS) but without much clue of how to check if values reoccur or not.

Does anyone have any insights into this problem? Is it too broad to be solved in general? Are there any interesting cases you can think of and wish to highlight?

Source Link
lordralphnewman
lordralphnewman
  • 1

Reducing recurrence relations mod10

I have been playing around with integer sequences as of late, and the following question occurred to me:

Suppose for $m$ fixed we have some some initial values $a_1,\cdots,a_m$ and for all $n\in\mathbb{N}:n>m$ we have a linear recurrence relation $a_n=\sum_{i=1}^{m}\alpha_i a_{n-i}$ with $\alpha_i\in\mathbb{Z}$ (we could generalise to non-linear recurrence relations, but we focus on linear ones for the time being). Suppose we define $b_n\equiv a_n mod10$ with $0\leq b_n\leq9$ and define the decimal expansion of $x$ by the concatenation $0.b_1b_2b_3\cdots$. Which recurrence relations give $x\in\mathbb{Q}$? Which give $x\notin\mathbb{Q}$? Which $x$ are normal?

I then realised (an embarrassingly long time after initially formulating this problem) that $x$ is rational if and only if its decimal expansion is repeating after some finite number of digits or terminating (i.e. repeated zeroes after some finite number of digits), so this question essentially reduces to whether a given recurrence relation is periodic (after some finite number of 'leading terms') when reduced mod10. Computationally it is easier to reduce each term mod10 as it is calculated.

I have been playing around with the Fibonacci sequence (OEIS A000045) and the example $a_n=a_{n-1}-a_{n-4}, a_1=a_2=a_3=a_4=1$ (which is sadly not documented on OEIS) but without much clue of how to check if values reoccur or not.

Does anyone have any insights into this problem? Is it too broad to be solved in general? Are there any interesting cases you can think of and wish to highlight?