44
$\begingroup$

Take the sequence 001 and repeatedly append its second half to itself, using the larger half if the length is odd. This gives you 00101 then 00101101 then 001011011101 then 001011011101011101 and so on. Counting the groups of adjacent ones gives 1 2 3 1 3 2 1 3 4 2 1 3 2 3 4.... You get similar results if you start off with other short sequences like 0010.

These sequences do not appear to repeat or follow an obvious pattern, yet they are generated from an extremely simple rule, similar to the Thue-Morse sequence or the look-and-say sequence. However, my sequence does not seem to be on OEIS.

I find it hard to believe that I'm the first person to think that appending half of a sequence to itself might be interesting. So my question is do these sequences already have a place in mathematics, however esoteric? If not, then why not? Am I wrong in thinking that this easily defined yet seemingly disorderly sequence is somewhat curious?

Related Questions:

Do runs of every length occur in this string?

Do runs of every length occur in this string? (At Math Overflow)

Where are the runs in this infinite string? (At Programming Puzzles & Code Golf)

$\endgroup$
9
  • 4
    $\begingroup$ The number of characters added each iteration follows oeis.org/A073941 or oeis.org/A005428. It seems that the parity of these numbers may be playing a part in how counting the groups of adjacent ones does not generate an obvious pattern. The parity of A073941(n) is at oeis.org/A082416. $\endgroup$
    – brogrenkp
    Jul 10, 2014 at 4:38
  • 2
    $\begingroup$ The restriction to binary digits seems artificial. I'd think it'd be better to consider the generic case (i.e. a string "$a_1,/,a_2/,...,a_n$") and then only afterwards suppose that some of the $a_n$ are identical. $\endgroup$
    – Semiclassical
    Jul 19, 2014 at 18:08
  • 1
    $\begingroup$ Okay, I have been trying to find more connections between this sequence and other things in mathematics. In this comment I will include a bit of how I have been approaching it lately and maybe it will help discover more connections. Make a list of the characters that are added during each iteration: {01, 101, 1101, 011101, 101011101, ...}. Note that the ends of these sequences are the same, because each iteration you add all of what was added before plus some. So reverse each element and note the index at which zeros appear: {1,5,7,10,15,19,22,26,28,32,36,38,41,46...}. $\endgroup$
    – brogrenkp
    Jul 20, 2014 at 1:31
  • 3
    $\begingroup$ I've posted a "spin-off" question: Do runs of every length occur in this string?. $\endgroup$
    – r.e.s.
    Jul 25, 2014 at 13:04
  • 1
    $\begingroup$ Just an idea, not an answer: I think to have a better relation to usual mathematical expressions and make the problem more "algebraic", one could mirror the initial sequence and then prepend instead of append. You initial word "001" is then "100" and the binary interpretation is $a_0=4$. Then pre pending the leading subsequence "10" means adding $(2^1) \cdot (2 \cdot 4)$ to $a_0$ to get $a_1=20$. Then iterate. This might be easier to handle, and possibly results in some Collatz-like iteration $\endgroup$
    – Gottfried Helms
    Dec 17, 2014 at 21:07

1 Answer 1

Reset to default
3
$\begingroup$

If I use abc to generate the sequence it comes out like this:

abc                       3
bc                        5
c bc                      8
c c bc                    12
bc c c bc                 18
c bc bc c c bc            27
c c c bc c bc bc c c bc   41

The list of numbers on the right, the sequence length up to that point, is A061419. A Mills-type formula for this sequence has the constant $\frac{2}{3}K(3)$, where $K(3)$ is A083286, and this last constant is related to the Josephus problem.

So your sequence is related to prime number sieves and the prime number theorem, which are closely linked with the Josephus problem. That you could not find the sequence in the OEIS is most likely because mathematics in this area lags behind other fields of number theory.

$\endgroup$

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.