Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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))$ ?

share|improve this question
6  
It has an irrational Cesàro sum: $\log_23$. –  Emil Jeřábek Feb 28 at 15:10
    
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) –  Gottfried Helms Mar 1 at 0:42
    
(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. –  Gottfried Helms Mar 1 at 1:01

1 Answer 1

up vote 6 down vote accepted

$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.

share|improve this answer
    
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). –  Marzio De Biasi Feb 28 at 15:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.