0
$\begingroup$

Let's call the infinite Thue-Morse sequence $T$. Define $\delta (n)$ to be $1$ if the binary representation of $n$ appears in $T$ and $0$ otherwise. Let $$F(n)=\sum_{i=1}^n\delta(i)$$

$\delta(7)=0$ , $\delta(300)=1$

$F(100)=32$ , $F(1000)=72$

According to wikipedia and MathWorld, an integer that appears in $T$ must have its binary representation overlapfree. However, not all overlapfree representations will appear, for example $54=110110_2$ does not appear. I found a paper describing an algorithm to count overlapfree words of a given length, but it doesn't readily apply here because not all words represent a valid integer, and because I want to find $F(n)$ for arbitrary integer $n$, and not just for $n=2^k-1$ for some integer $k$.

Can the above algorithm be adjusted somehow? Is there any way to evaluate $F(n)$ exactly? Is there any asymptotic approximation for $F(n)$?

$\endgroup$
2
  • $\begingroup$ "... an integer will appear in $T$ if it's binary representation is overlapfree." Consider $54=(110110)_2.$ Isn't $110110$ overlap-free without appearing in $T?$ $\endgroup$
    – r.e.s.
    Commented Apr 6, 2023 at 3:40
  • $\begingroup$ @r.e.s. Yes, it seems correct. Then I believe every integer that appears is overlapfree, but not overlapfree integers appear. Thank you. Then is there a better characterization of the integers that do appear? $\endgroup$
    – MC From Scratch
    Commented Apr 6, 2023 at 5:13

0

Reset to default

You must log in to answer this question.