28
$\begingroup$

The following story is true, not just to make it sound mysterious or coincidental. I found a very curious sequence of integers, and searching it gave no result. I am trying to learn more about it, just for fun.

We were taking a break with two friends, and came up with the following game in the staircase:

  • Assume there are $n$ stairs (so $n+1$ places to stand);
  • Starting from the bottom, go up 1 stair at a time, until you reach the top;
  • Then turn around and go down 2 stairs at a time, until you can't go further;
  • Then turn around and go up 3 stairs at a time, until you can't go further;
  • .. Then 4, 5, 6, etc. stairs at a time, until you can't even make one step.

Whatever the step size is when you stop (the one you cannot achieve), is characteristic of the number of stairs in the staircase, and we call it the Mona number (after my friend Mona).

For Example: For $n=5$ we go up to the top, then down in sets of $2$ until we reach $1$, then up $3$ to $4$, then down $4$ to $0$, then up $5$ to $5$, and then we are stuck because there aren't $6$ stairs to go down from our current position. Therefore $M(5)=6$.

From there, we wondered if we could find a formula for that number. Obviously it has to be at least 2 (going up the stairs one stair at a time should always be possible), but it is not monotonic with the number of stairs. The "mirroring" operation of "turning around" makes it quite difficult; in particular the system clearly has a memory, but the state of that memory does not only depend on the previous step size. So instead, we wrote a program for it (Matlab code):

function k = mona(n)

    assert( n >= 1 );    
    h = n;
    k = 2;

    while h >= k
        h = mod(h,k);
        h = n-h;
        k = k+1;
    end

end

where n is the number of stairs, k is the step size, and h is the "horizon" -- aka the number of stairs remaining until the end of the staircase for a given step size. Plotting it for the first 1000 integers looks like this:

Mona sequence for the first 1000 integers

I have thought about it for a while, but it is much more complicated to analyse than it seems, and the analytic formulation of the sequence is ugly so I'm not sure it can help.

I would be curious to know whether this relates to any known integer process? And if not, whether you have a clever idea of how to analyse the Mona sequence?


About the envelope

As can be seen on the plot, there seems to be a bounding cone to the progression of this sequence. This "envelope" corresponds to the following cases (found programmatically):

\begin{align} N_\mathrm{upper} &= \left\{ n\ |\ M(n)=n+1 \right\} = \{ 1,2,5,8,14,50,119,200,269,299, ... \} \\ N_\mathrm{lower} &= \left\{ n\ |\ M(n)=\left\lceil \frac{n}{2}\right\rceil + 1 \right\} = \{ 1,3,7,39,47,111,959, ... \} \end{align}

However once again, neither of these sequences give a hit in the OEIS.

$\endgroup$
  • 1
    $\begingroup$ Oh I see, so, for $n=5$ we go up to the top, then down in sets of $2$ until we reach $1$, then up $3$ to $4$, then down $4$ to $0$, then up $5$ to $5$, and then we are stuck because there aren't $6$ stairs to go down from our current position or $7$ stairs to go up? So $M(5)=5$ $\endgroup$ – Stella Biderman Feb 15 '17 at 18:25
  • 1
    $\begingroup$ Let's say we define $M(a,b)$ to be where you are after you make the $b^{th}$ step on a staircase of size $a$ and use the convention that there is a $0^{th}$ step. Then $M(a)\leq a+1$ and $$M(a)=a+1\iff M(a,a-1)=0\iff M(a, a-2)=a-1\iff\cdots$$ The larger $a$ is the longer you can expand this equality condition, because it holds for $b>a/2$ (since that guarantees that you're only taking one step each time) $\endgroup$ – Stella Biderman Feb 15 '17 at 18:37
  • 1
    $\begingroup$ @John, no results if you use more terms: $(2,3,6,9,15,51,120,201)$ or $(1,2,5,8,14,50,119,200)$. $\endgroup$ – Peter Kagey Feb 15 '17 at 18:55
  • 1
    $\begingroup$ @John and Peter, I edited the OP to include something about the apparent envelope. Perhaps it makes more sense to subtract 1 to this sequence, seeing as the formulas always seem to carry a +1 so far. $\endgroup$ – Sheljohn Feb 15 '17 at 19:18
  • 1
    $\begingroup$ @Sheljohn: (+1) especially for this nice and insightful presentation! $\endgroup$ – Markus Scheuer Feb 16 '17 at 8:00
5
$\begingroup$

I would be curious to know whether this relates to any known integer process?

This reminds me of the Fibonacho's sequence (A280521) which was asked on Reddit by user Teblefer—and more specifically, it reminds me of the natural number generalization: A057945.

The Fibonacho's sequence works similarly (quote from the Reddit post):

two people are sharing a plate of nachos. They take turns dividing the nachos, each taking the nth Fibonacci number of nachos on the nth turn. When the number of nachos left is less than the next Fibonacci number, they start the sequence over. What number of nachos (less than 500) requires the most number of restarts? How would you generate numbers of nachos with a high number of restarts?

In a recent lecture, Neil Sloane (the founder of the OEIS) discusses the Fibonacho's sequence and its generalizations. (You can see the details in Slides 18-23 and the video starting at 12:50.)

In general, Neil suggests that there has not been much exploration of (or insight into) these Fibonacho-like problems, which leads me to believe that the "Mona" sequence is probably largely unexplored too.


I've gone ahead an added these and related sequences to the OEIS and linked them back to this question.

  • A282442: smallest step size that does not occur.
    • 2, 3, 3, 4, 6, 5, 5, 9, 9, 8, 10, 11, ...
  • A282443: largest step size that does occur.
    • 1, 2, 2, 3, 5, 4, 4, 8, 8, 7, 9, 10, ...
  • A282444: Numbers $n$ such that $A282442(n) = n + 1$.
    • 1, 2, 5, 8, 14, 50, 119, 200, 269, 299, 1154, 5369, ...
  • A282427: Numbers $n$ such that $A282442(n) = \lceil\frac{n}{2}\rceil + 1$.
    • 1, 3, 7, 39, 47, 111, 959, 3319, 7407, 11967, 13007, 16239, ...
  • A282434: Positions of records in A282442.
    • 1, 2, 4, 5, 8, 11, 12, 14, 18, 19, 21, 24, ...
  • A282573: Number of steps taken.
    • 1, 3, 4, 7, 10, 12, 13, 19, 20, 23, 26, 32, ...
  • A282574: Final position.
    • 1, 0, 1, 3, 5, 2, 3, 0, 1, 7, 9, 2, 3, 0, ...
$\endgroup$
  • $\begingroup$ I will have a look at the Fibonacho sequence :) If you are right, then perhaps there is little chance that my question will be answered in the near future. $\endgroup$ – Sheljohn Feb 15 '17 at 19:20

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.