23
$\begingroup$

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$:
 SeqMeans10k
As per Eckhard's request, with Will's function $\sqrt{4n/3} -1/2$:
 SeqMeansWill

$\endgroup$
8
  • 10
    $\begingroup$ Doesn't the mean have to decrease at each step (or stay the same)? Wouldn't that show it stabilizes? I would also guess that typically the final answer would be about $\sqrt{n}$; I'd be surprised if it were monotone in $n$. $\endgroup$
    – Lucia
    Nov 2, 2013 at 14:33
  • 9
    $\begingroup$ If $a_k$ is the mean of the first $k$ elements, then $a_{k+1}=\lceil (ka_k+1)/(k+1)\rceil$. This formula is monotone in $a_k$, hence $a_k$ is a monotone function of $a_1=n$. Hence so is $r(n)$, which equals $a_k$ for all sufficiently large $k$. $\endgroup$ Nov 2, 2013 at 16:30
  • 1
    $\begingroup$ @SergeiIvanov: very nice indeed! $\endgroup$
    – Lucia
    Nov 2, 2013 at 16:33
  • $\begingroup$ What does Will's constant of $\sqrt{4/3}$ look like in your graph? $\endgroup$
    – Eckhard
    Nov 2, 2013 at 19:55
  • 2
    $\begingroup$ This question is now entirely settled, an amazing collaboration among half-a-dozen contributors. I would accept them all were that an option! $\endgroup$ Nov 4, 2013 at 19:02

5 Answers 5

16
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Congrats on computing the constant! Amazing to see $2/\sqrt{\pi}$ emerge out of this problem! $\endgroup$ Nov 4, 2013 at 0:14
  • $\begingroup$ @JosephO'Rourke: Thanks! Yes the $2/\sqrt{\pi}$ was a surprise. $\endgroup$
    – Lucia
    Nov 4, 2013 at 5:00
  • $\begingroup$ very nice result indeed. $\endgroup$ Nov 4, 2013 at 11:11
5
$\begingroup$

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))
}   
$\endgroup$
1
  • 1
    $\begingroup$ I would just like to confirm that I've calculated this sequence and got the same result. $\endgroup$ Nov 2, 2013 at 17:03
5
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ Paul Hanna's formula has the obvious bounds $r^2 - r(r-1)/2 \leq n(r) \leq n^2$, so $\sqrt{n}-1 \leq r(n) \leq \sqrt{2n}$, which is similar to Julian's and Konstantin's bounds but might improve the constants. $\endgroup$
    – Will Sawin
    Nov 2, 2013 at 17:32
  • $\begingroup$ The data confirms your bounds, with constant about $1.14$. $\endgroup$ Nov 2, 2013 at 18:13
  • $\begingroup$ How did you compute $1.14$ from the original $1.377$? i.e. which constant is it? $\endgroup$
    – Will Sawin
    Nov 2, 2013 at 18:49
  • $\begingroup$ I made a typo, dropping a digit from 1.1377 to 1.377, then corrected myself. The best-fit is 1.1377. Sorry for sowing confusion! $\endgroup$ Nov 2, 2013 at 18:54
  • 1
    $\begingroup$ Excellent! This fits fairly well to the random heuristic, which says that $n(r)$ falls about half the maximum possible distance from $r^2$, so it is about $3r^2/4$, so $r(n) = \sqrt{4/3} \sqrt{n}$. This predicts a constant of $1.1547$ $\endgroup$
    – Will Sawin
    Nov 2, 2013 at 19:00
4
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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