Sequences with integral means

Question

Let $S(n)$ be the sequence whose first element is $n$, and from then onward, the next element is the smallest natural number ${\ge}1$ that ensures that the mean of all the numbers in the sequence is an integer.

For example, the second element of $S(4)$ cannot be $1$ (mean $\frac{5}{2}$), but $2$ works: $S(4)=4,2,\ldots$. Then the third element cannot be $1$ (mean $\frac{7}{3}$) or $2$ (mean $\frac{8}{3}$), but $3$ works: $S(4)=4,2,3,\ldots$. And from then on, the elements are all $3$'s, which I'll write as $S(4)=4,2,\overline{3}$.

Here are a few more examples: $$S(1)=1,\overline{1}$$ $$S(2)=2,2,\overline{2}$$ $$S(3)=3,1,\overline{2}$$ $$S(4)=4,2,\overline{3}$$ $$S(5)=5,1,\overline{3}$$ $$S(11)=11,1,3,1,\overline{4}$$ $$S(32)=32,2,2,4,5,3,1,\overline{7}$$ $$S(111)=111,1,2,2,4,6,7,3,8,6,4,2,\overline{13}$$ $$S(112)=112,2,3,3,5,1,7,3,8,6,4,2,\overline{13}$$ $$S(200)=200,2,2,4,2,6,1,7,1,5,1,9,7,5,3,1,\overline{16}$$

Has anyone studied these sequences? Is there a simple proof that each sequence ends with a repeated number $\overline{m}$? Is there a way to predict the value of $m$ from the start $n$ without computing the entire sequence up to $\overline{m}$? Might it be that the repeat value $m=r(n)$ satisfies $r(n+1) \ge r(n)$?

This question occurred to me when thinking about streaming computation of means, a not-infrequent calculation (e.g., computing mean temperatures).

---

Added, supporting the discoveries of several commenters: $r(n)$ red, and now fit with $1.135 \sqrt{n}$ blue for $n\le 10000$:
 

---

As per Eckhard's request, with Will's function $\sqrt{4n/3} -1/2$:
 

Answer 1

Will Sawin's guess that the mean stabilizes around $2\sqrt{n/3}$ is very close to the correct answer, but not quite! Asymptotically the right answer is $\sim 2\sqrt{n/\pi}$. Note that $2/\sqrt{\pi}$ is about $1.12837\ldots$.

To see why this is, suppose that $n$ is large, and let $\ell$ also be large, but small compared with $n$. Consider the number of steps $k$ needed until the mean first dips below $k\ell$. It is easy to see that $k\sim \sqrt{n/\ell}$. Now if we continue from step $k$, the mean must first drop by $\ell-1$ at each step, until we get to a point $k_1$ such that the mean at this point $k_1$ dips below $k_1(\ell-1)$. It is easy to see that $k_1$ is about $k(2\ell-1)/(2\ell-2)$. From here on at each step the mean drops by $\ell -2$ at each step, until we arrive at a point $k_2$ where the mean has dipped below $k_2(\ell-2)$. Now $k_2$ is about $$ k\Big(\frac{2\ell-1}{2\ell-2}\Big) \Big(\frac{2\ell-3}{2\ell-4}\Big). $$ And so on. (In following the above calculations, the comment of Sergei Ivanov is useful.)

In this manner we find that the number of steps taken to terminate (which is also the size of the final mean) is about $$ \sqrt{n/\ell} \Big(\frac{2\ell-1}{2\ell-2}\Big) \cdots \Big(\frac{5}{4}\Big)\Big(\frac{3}{2}\Big). $$ Computing this using Stirling's formula finishes the proof.

Note: Everyone writes, no one reads! (Myself included, of course.) I just looked at the OEIS reference linked by Elkies, and the $\sim 2\sqrt{n/\pi}$ result essentially appears there. Apparently this is first due to Viggo Brun himself, and refined by M.E. Andersson in a paper in Acta Arithmetica (see http://matwbn.icm.edu.pl/ksiazki/aa/aa85/aa8542.pdf ). But the paper is in German and six pages long, so the above short proof may still be useful.

Answer 2

Lucia already proved in a comment that the sequence stabilizes: at each step the mean decreases or stays the same, and once the sequence is longer than the mean the mean can no longer decrease.

For the remaining questions, here's numerical evidence:

Computing through $n=1000$ I find that $r(n+1) \geq r(n)$ for all $n$, and when $r(n+1) > r(n)$ the difference is 1. The sequence of such $n$ is

1, 3, 7, 13, 19, 27, 39, 49, 63, 79, 91, 109, 133, 147, 181, 207, 223, 253, 289, 307, 349, 387, 399, 459, 481, 529, 567, 613, 649, 709, 763, 807, 843, 927, 949, ...

which matches OEIS sequence A000960 "Flavius Josephus's sieve: Start with the natural numbers; at the $k$-th sieving step, remove every $(k+1)$-st term of the sequence remaining after the $(k-1)$-st sieving step; iterate."

Here's the gp code I use to compute $S(n)$:

{   
S(n, l,i,r) =
  l = [n];
  m = n;
  i = 1;
  while(m>i,
    i++;
    r = m%i;
    if(r==0, r=i);
    l = concat(l,r);
    m -= (m-r)/i;
  );  
  if(m==r,l,concat(l,m))
}   

Answer 3

I think I can confirm Noam Elkies' equivalence of sequences (that $r(n)$ is nondecreasing, and that it firsst attains the value $r$ at $n$ equal to the $r$th term in the OEIS sequence A00960)

First we will check that $r(n+1)\geq r(n)$. Let $A_k(n)$ be the sum of the first $k$ elements of $S(n)$. Then $A_k(n+1) \geq A_{k}(n)$, by induction. Hence $r(n+1) \geq r(n)$. (Edit: I see Sergei earlier made an identical argument.)

To compute $A_k(n)$, we take $n$, then increase to the first multiple of $2$, then increase to the first multiple of $3$, etc., and increase to the first multiple of $k$.

From OEIS, here is an alternate way of calculating A00960:

"As in Paul D. Hanna's formula, start with n^2 and successively move down to the highest multiple of n-1, n-2, etc., smaller than your current number: 121 120 117 112 105 102 100 96 93 92 91, so a(11) = 91, from moving down to multiples of 10, 9, ..., 1. - Joshua Zucker, May 20 2006"

These sound very similar! Let's prove they work the same. Suppose we start at $r^2$ and apply Joshua Zucker's process, ending in a number $n$. Then when we apply Joel's process, $A_k(n)$ will reverse this course. At each step it goes up to the next multiple of $k$. But the previous step of Joshua's process is at most $k-1$, so the next multiple of $k$ is the previous step of Joshua's process. So $A_r(n)=r^2$. Then clearly $A_{r+d}(n)=r(r+d)$ by induction on $d$ for al $d \geq 0$, so $r(n)=r$.

Similarly we can check that $r(n-1)=r-1$, because $A_k(n-1)= A_k(n)-k$ by induction.

So $r(n)$ is nondecreasing, and jumps exactly at the points of A00960.

Answer 4

Here are some bounds on the stable value $r(n)$, as well as the number of terms of the sequence that need to be calculated. The short version is that $$ \frac{\sqrt{2}}{2}\sqrt{n}+O(1)\leq r(n)\leq \frac{3\sqrt{2}}{2}\sqrt{n}+O(1), $$ and about $\sqrt{n}$ terms need to be calculated.

Write $S_k(n)$ for the $k$-th element of $S(n)$, where we start indexing at 1, and let $\mu_k(n)$ be the average of the first $k$ terms of $S(n)$. Let's also write $$ f(n):=\min\{k:S_j(n)=S_k(n)\,\,\forall j\geq k\} $$ for the index at which $S(n)$ stabilizes (by Lucia's comment, we know this is finite). It's not too hard to see that $$ f(n)=1+\min\{k:\mu_k(n)\leq k+1\}. $$

We have $1\leq S_k(n)\leq k$ for $k\geq 2$, so that $$ \frac{n+k-1}{k}\leq \mu_{k}(n)\leq \frac{n+\frac{k(k+1)}{2}-1}{k}. $$ We can use this to obtain the bounds $$ 1+\sqrt{n-1} \leq f(n) \leq \frac{3+\sqrt{8n-7}}{2}. $$

The stable value $r(n)$ is given by $$ r(n)=\mu_{f(n)-1}(n), $$ so our upper and lower bounds on $\mu_k(n)$ (and the upper bound on $f(n)$) gives $$ \frac{(n-1)\sqrt{8n-7}+n-5}{4(n-2)}\leq r(n)\leq \frac{(3n-5)\sqrt{8n-7}+7n-17}{4(n-2)}, $$ at least for $n\geq 3$.

Answer 5

Let $k$ be sufficiently large .Denote the sequence $n,a_1,...a_{k-1}$ with $a_i\leq i+1$ where $i\leq k-1$.
The sum of the first $k$ elements including $n$ (denote it by $S_+(a_k)$) must be always a multiple of $k$ .
So let $d$ be a positive integer with $S_+(a_k)=d\cdot k=n+a_1+...+a_{k-1}\leq n+2+...+k=n-1+k\frac{k+1}{2}$ .
So $d=\frac{S_+(a_k)}{k}=\frac{n-1}{k}+\frac{k +1}{2}<k$ for $k$ large enough.

We will see that the period we want is the number $d$.

We will show that the next element $a_k$ is the number $d$ and inductively we wil reach our goal.
Let $a_k$ be the next element ,so we must have $k+1|S_+(a_{k+1})$ meaning that $k+1|d\cdot k+a_k$
which gives $k+1|a_k-d$.
But $a_k\leq {k+1}$ and $d<k$ so we have only the case $a_k-d=0$ and so, $a_k=d$
(Repeat the argument again)
So we only wait until $\frac{n-1}{k}+\frac{k+1}{2}<k$ to find the period $d$.
This gives the bound closely to $\sqrt n$ which Lucia commented.
I hope this helps.