41
$\begingroup$

Define a "mod sequence" of nonnegative integers based on one start parameter $s$, its first term, as follows. $A(s)=(a_1,a_2,\ldots,a_n,\ldots)$ with $a_1 = s$ and $$ a_n = \left(\sum_{k=1}^{n-1} a_k \right) \bmod n\;.$$

For example, $A(13)=(13, 1, 2, 0, 1, 5, 1, 7, 3, 3, 3, \ldots)$. Here is how this is obtained. Let $S(s)$ be the sums, $s_n=\sum_1^{n} a_k$. Then $S(13)=(13, 14, 16, 16, 17, 22, 23, 30, 33, 36, 39, \ldots)$. In detail, $$a_2 = 13 \bmod 2 = 1$$ $$a_3 = 14 \bmod 3 = 2$$ $$a_4 = 16 \bmod 4 = 0$$ $$a_5 = 16 \bmod 5 = 1$$ $$a_6 = 17 \bmod 6 = 5$$ $$a_7 = 22 \bmod 7 = 1$$ $$a_8 = 23 \bmod 8 = 7$$ $$a_9 = 30 \bmod 9 = 3$$ $$a_{10} = 33 \bmod 10 = 3$$ $$a_{11} = 36 \bmod 11 = 3$$ $$a_{12} = 39 \bmod 12 = 3$$ And all remaining terms are $3$.

Q1. For all $s \ge 1$, does $A(s)$ become a constant after some finite $n$, $a_n=c$?

Here is a bit more data, showing for each $s$ (first row), the constant reached (second row): $$\left( \begin{array}{ccccccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ 97 & 97 & 1 & 1 & 2 & 2 & 2 & 2 & 316 & 316 & 2 & 2 & 3 \\ \end{array} \right)$$ The constant $316$ seems especially ubiquitous, always (apparently) reached at $a_{1241}=316$. For $s \le 50$, $316$ is reached for $$s=\{9,10,33,34,37,38,39,40,43,44,45,46,47,48,49,50\}\;.$$ For $s=9$, $s_{1241}=392472$ and $(392472 \bmod 1241) = 316$; then $s_{1242}=392788$ and $(392788 \bmod 1242) = 316$; etc.

Q2. What is special (if anything) about $316$?


Addendum. Here is an image that shows which $s$ map to which $a_n=c$, for all $s \le 100$. The upper-right cluster is $316$. The leftmost cluster is $13$, nearly as ubiquitous as $316$; so perhaps I misled to single out $316$....
        ModSeqs100


$\endgroup$
  • 6
    $\begingroup$ If $a_n = a_{n+1}$ for some $n$, we are done, beacause then $s_{n-1} \equiv 0 \mod (n+1)$, so $s_{n-1} = x(n+1)$ and $a_n = x$. So we have $s_n = x(n+2)$, $a_{n+1} = x$, $s_{n+1} = x(n+3)$, $a_{n+2} = x$ and so on... $\endgroup$ – István Kovács Dec 26 '14 at 17:40
  • 3
    $\begingroup$ More generally, if $s_{n-1} = x_n (n+1) + b_n$ with $0 \leq b_n \leq n$, then $a_n = x_n + b_n - n \epsilon_n$ where $\epsilon_n := 1_{x_n+b_n \geq n}$ and then $b_{n+1} = 2b_n + 2 \epsilon_n \hbox{ mod } n+2$ and $x_{n+1} = x_n + \lfloor \frac{2b_n - n \epsilon_n}{n+2} \rfloor$. As Istvan observed, as soon as $b_n$ hits zero one gets a constant sequence, so the puzzle is why $b_{1241}=0, x_{1241}=316$ occurs so often. The latter is at least not so puzzling: we expect $a_n$ to be $n/2$ on avg, so concentration of measure predicts $s_n \sim n^2/4$ and $x_n \sim n/4$. $\endgroup$ – Terry Tao Dec 26 '14 at 19:26
  • 4
    $\begingroup$ @Istvan, that doesn't work when a_1 is a reasonably sized factorial. There are other exceptions when a_n is larger than n^2. $\endgroup$ – The Masked Avenger Dec 26 '14 at 19:28
  • 3
    $\begingroup$ @The Masked Avenger, yes, we need the condition, such that $x_n < n$, but by growing rate of $s_n$ its eventually true. $\endgroup$ – István Kovács Dec 26 '14 at 21:23
  • 3
    $\begingroup$ The sequence cannot become constant in the $\pmod{p_n}$ case, for any starting value $s>0$. To see this, suppose by way of contradiction that it did become the constant sequence $c\pmod{p_n}$ for every $n>N$. This would mean that $s_N+(m-1)c\equiv 0\pmod{p_{N+m}}$ (for each $m\geq 1$), and hence $p_{N+m}|(s_N+(m-1)c)$. But $p_{N+m}\sim (N+m)\log(N+m)$ while $s_N+(m-1)c\sim cm$, so the primes grow too fast to continue dividing. $\endgroup$ – Pace Nielsen Dec 27 '14 at 17:36
10
$\begingroup$

Before this becomes another forgotten open problem on MO, let me record here a comment. An equivalent way to state the sequence is as follows: Let $x(1)=2s-1$ and look at the recurrence equation: $$x(n+1)=x(n)+x(n)_{\operatorname{mod}n}$$ where I'm using $x_{\operatorname{mod}n}$ to mean the smallest nonnegative integer equal to $x$ mod n. You get essentially the same sequence if you start with $x(1)=2k$. Now the question in the OP is equivalent to:

Question: Is this sequence eventually an arithmetic progression?

The common difference of this progression is the convergent value of your sequence. This conjecture was mentioned in A117846.

Moreover, the OEIS also includes a slightly more general conjecture in A074482: Suppose $x(1,k)=s$ and $$x(n+1,k)=x(n,k)+x(n,k)_{\operatorname{mod} n+k}$$ is this always eventually an arithmetic progression? What can we say about the common differences as a function of $s,k$? The mysterious 316 doesn't appear prominently anymore for different $k$, but the values do tend to concentrate around other seemingly random numbers. The oeis links have a lot of computed values in case anyone wants to hunt for patterns.

$\endgroup$
  • 2
    $\begingroup$ Nice to see $316$, $97$, et al. show up in A117846! $\endgroup$ – Joseph O'Rourke Dec 29 '14 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.