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

Improve this question
$\endgroup$
14
  • 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
    Commented Dec 26, 2014 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
    Commented Dec 26, 2014 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
    Commented Dec 26, 2014 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
    Commented Dec 26, 2014 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
    Commented Dec 27, 2014 at 17:36

1 Answer 1

Reset to default
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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .