4
$\begingroup$

Let $a(n)$ for $n \geq 1$ be the number of powers of two $2^m$ that lie between $3^{n-1}$ and $3^{n}$:

$$a(n) = 1, 2, 1, 2, 1, 2, 2, 1, ...$$

It represents the increments between successive terms of allowable dropping times in the Collatz ($3x+1$) problem (see oeis A022921).

Is there an easy way to prove that the sequence never becomes periodic? i.e. do not exist $n_0, k \geq 1$ such that for all $n \geq n_0$, $a(n) = a(n_0 + (n - n_0)\bmod k))$ ?

$\endgroup$
  • 7
    $\begingroup$ It has an irrational Cesàro sum: $\log_23$. $\endgroup$ – Emil Jeřábek supports Monica Feb 28 '14 at 15:10
  • 1
    $\begingroup$ even more interesting: there are two types of partial sums, say $a=1,2$ and $b=1,2,2$. Then you can rewrite it $a_1(n)=a,a,a,b,a,a,a,b,a,a,b,a,a,a,b,...$ ,say. THis has again two types of "words",$c=a,a,a,b$ and $d=a,a,b$, say. Then one can rewrite this as $a_2(n) = c,d,d,d,c,d,d,c,d,d,d,....$. Then this has two types of "words"... and so on. It is a nice game to find the ever more compressed expression, and is also related to the continued fraction of log(3)/log(2) (or log(3/2), dan't have it at hand at the moment) $\endgroup$ – Gottfried Helms Mar 1 '14 at 0:42
  • $\begingroup$ (cont) I forgot to mention: the a-periodicity guarantees, that this does not run into a repeated sequence of only one letter but can be continued forever to sharper compressions. If we write the sequence instead as infinite product, beginning with (3/2)*(3/2)*(3/4)*... where we take care that we never fall below 1, then the compression as words provide the "best approximations" of powers of 3 to powers of 2. $\endgroup$ – Gottfried Helms Mar 1 '14 at 1:01
7
$\begingroup$

$a(n)=\lfloor \alpha n\rfloor-\lfloor \alpha(n-1)\rfloor$, where $\alpha=\log_23$. Sequences of this type are called Sturmian and are well known (and easily shown) not to be periodic. Basically: for any $x,x'$ whose difference is not an integer, there is a multiple of $\alpha$ such that $\lfloor x+n\alpha\rfloor-\lfloor x\rfloor\ne \lfloor x'+n\alpha\rfloor-\lfloor x'\rfloor$ by density of multiples of $\alpha$ in the circle.

$\endgroup$
  • $\begingroup$ Thanks! I noticed that Chapter 2 of Lothaire's "Algebraic combinatorics on words" is entirely devoted to "Sturmian words"; I'll try to read it (my mathematical skills are poor). $\endgroup$ – Marzio De Biasi Feb 28 '14 at 15:43

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.