40
$\begingroup$

This is a repost from user r.e.s's unsolved Math Stack Exchange question: Do runs of every length occur in this string? That question was derived from my original question on the subject: Does this sequence have any mathematical significance? There is also a related Programming Puzzles & Code Golf question: Where are the runs in this infinite string? (CCCCCC Found!)

I am posting it here in hopes that some of you will be able to shed more light on the problem or even solve it. I apologize if does not fall into the "research question" category, but I imagine many of you may find it quite intriguing.

The Problem

Starting with the sequence $\text{001}$, consider the infinite sequence $s$ generated by repeatedly appending the last half of the current sequence to itself, using the larger half if the length is odd:

$$\begin{align} \quad &\text{001}\\ &\text{00101}\\ &\text{00101101}\\ &\text{001011011101}\\ &\cdots\\ &\text{______________________________}\\ s = \ &\text{0010110111010111011010111011110...} \end{align} $$

Does every sized run of ones occur in $s$? The first few runs are easy to find but then their indices grow astronomically as we've found in the programming contest:

$$\begin{align} &\text{run} \quad & \text{first index}\\ &\text{1} &\text{2}\\ &\text{11} &\text{4}\\ &\text{111} &\text{7}\\ &\text{1111} &\text{26}\\ &\text{11111} &\text{27308}\\ &\text{111111} &\approx 10^{519}\\ &\text{1111111} &? \ (\gt 10^{40501})\\ \end{align} $$

What can be said about the runs of ones in $s$? Why is the index growth so extraordinary? Can one prove or disprove that all runs of ones occur in $s$?

Note that user r.e.s has done much more analysis on this problem in his/her original question. The formatting above is his/hers; I've only changed $\text{abc}$ to my original $\text{001}$ starting sequence. It is r.e.s. and the other users in the programming contest that helped generate the substring indices. I've had little to do with the analysis of this sequence except as discussion starter.

Improve this question
$\endgroup$
8
  • 4
    $\begingroup$ Suggestion for slightly simpler notation: kick off with 001. Then we get 001, 00101, 00101101, etc. $\endgroup$
    – John Bentin
    Commented Aug 7, 2014 at 10:46
  • $\begingroup$ @JohnBentin - This sequence was originally defined (by user "Calvin's Hobbies") as starting with $001$. I introduced the $\text{abc}$ version to illustrate clearly the role played by the symbol in each starting position (e.g., that the first symbol does not propagate); however, the original $001...$ version might be preferred for some purposes. $\endgroup$
    – r.e.s.
    Commented Aug 7, 2014 at 12:54
  • $\begingroup$ I've changed it since I also prefer $001$ but it's obviously just a semantic difference. $\endgroup$
    – Calvin's Hobbies
    Commented Aug 7, 2014 at 12:56
  • 1
    $\begingroup$ One can do many interesting variations on this problem, by doing some simple transformation on the "half-part" before concatenating it (similar to the Morse sequence), where one say, invert or reverse the numbers. With the reversing operator, one quite quickly get runs of length 16, but I have not found any longer (but them, I only checked up to 40 iterations). $\endgroup$
    – Per Alexandersson
    Commented Aug 7, 2014 at 13:51
  • $\begingroup$ One vote and also favorating question. It seems that the behaviour of consequtive 1 in this squence is more chaotic. This is just a view: let $a_n$ and $L_n$ denote the number of ones and total length of sequnces in the $n$-th iteration, respectively. So (if I do not be wrong), $a_n\thickapprox‎ \frac{3}{2}a_{n-1}$ and $L_n \thickapprox 2(3/2)^n‎$. Now, $\frac{a_n}{L_n}$ tends to $\frac{1}{2}$, when $n$ goes to infinity. So, I think the conjecture is true, but its proof must be difficult, because of $\frac{1}{2}$. $\endgroup$
    – Shahrooz
    Commented Aug 9, 2014 at 13:43

1 Answer 1

Reset to default
4
$\begingroup$

Some observations, (some were pointed out at other exchanges):

The only way to get a run of length $n$, is to cut off the partial sequence in the middle, such that the cut-off part starts with a run of length $n-1$.

A point of attack is therefore to just keep the index of the longest observed run, iterate, (which give indices to copies of this run) in the longer sequences. What has to be done is therefore so look for a form of relatively prime-ness of the indices of the copies, and the cut-off index.

Conjectured lemma: Assume there is a run of $n$ ones starting at index $j$. Then, for any $k>0$ and $0\leq r<k$, there are infinitely many $N$ such that a run of length $n$ in $s$ starts at an index $Nk+r$.

Improve this answer
$\endgroup$
6
  • 3
    $\begingroup$ After $1^n$ first occurs, more instances of it arise in two ways: (1) as copies of the original and copies of copies, etc., and (2) as newly created cases when an "appended half" again happens to begin with $1^{n−1}$. So, it is not sufficient to simply track the indices of copies of the first occurrence of the longest observed run, as these will omit all type-2 instances. $\endgroup$
    – r.e.s.
    Commented Aug 7, 2014 at 14:35
  • $\begingroup$ Yes, of course new instances can be created, but I think they should be relatively rare, compared to ancestors of the first one. The conjectured lemma should be interpreted as only tracking the ancestors of the original one; it would be much simpler if this is enough. $\endgroup$
    – Per Alexandersson
    Commented Aug 7, 2014 at 14:39
  • $\begingroup$ Would your conjectured lemma imply anything, assuming it was true? $\endgroup$
    – Christian Remling
    Commented Aug 7, 2014 at 18:45
  • $\begingroup$ Not directly, but if you get some precise data on where these indexes occur, you can compare it with the cutoff indices. The lemma is sort of a warm-up. $\endgroup$
    – Per Alexandersson
    Commented Aug 7, 2014 at 18:50
  • 1
    $\begingroup$ Once $1^n$ appears, it is going to propagate itself roughly as much as the length of the sequence. Specifically, after $t$ steps there will be roughly $(3/2)^t$ instances of $1^n$. So heuristically, the probability of $1^n$ converted to $1^{n+1}$ is give or take the same. This strongly suggest that $1^{n+1}$ would eventually appear. Unfortunately, this eventually is of the magnitude $1/N$ where $N$ is the length of the sequence when $1^n$ appeared. So $1^7$ is likely still far far off. There are other issues, as r.e.s. pointed out, but they appear to be minor. $\endgroup$
    – Lev Borisov
    Commented Aug 17, 2014 at 1:53

You must log in to answer this question.

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