MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a number $x \geq 3$, let $b(x) \in \{0,1\}$ be the second most significant digit (bit) of its binary representation, and $t(x)\in \{1,2\}$ the most significant digit of its ternary representation.

In other words: $x = 2^n + b(x) 2^{n-1} + ... = t(x) 3^m + ...$ for some $n,m \geq 1$

Let $A$ be the set of $K \geq 0$ such that there exist integers $x \geq 3, y \geq 1$ and

$$b(x + i y) + t(x + i y) = 1 \text{ for all } 0 \leq i \leq K$$

Informally the longest (integer) arithmetic progression that can be formed with numbers having $0$ as the second most significant digit of its binary representation and $1$ as the most significant digit of its ternary representation.

Is $A$ finite?
Do exist $x,y$ such that $b(x + i y) + t(x + i y) = 1 \text{ for all } i$?
share|cite|improve this question
No , A is infinite, as there are infinitely many intervals of increasing length of numbers with such representation. Eventually the mth interval has more than 2^m many consecutive integers. – The Masked Avenger Mar 5 '14 at 1:14
up vote 2 down vote accepted

The problem is a little harder than it seems at first glance. Pick m large, say m > 8. There are 3k=3^m numbers with first ternary digit 1 and m other ternary digits. Suppose 0<= a < 3^m is smallest such that 3k +a= 3*2^l. Then 2^(l+2)=4k +4a/3, so there will be either at least k/2 numbers before 3k+a or after 4k+ 4a/3 which are part of the 3k numbers in ternary which begin 10 in binary. The claim in the comment above that A is infinite follows, while the claim about the mth interval does not, although there will be an interval of length > 2^m for every m.

share|cite|improve this answer
Indeed k/2 can be replaced by something like 6k/7. In any case there will be at least 2^m consecutive numbers of the desired form for all m not too small. – The Masked Avenger Mar 5 '14 at 4:07
Thanks, it confirms my idea (use $4 \cdot 3^{2m}+2i$); but I'm not an expert; do you have a suggestion about how to formally prove the second claim (there are not progressions of infinite length)? – Marzio De Biasi Mar 5 '14 at 13:18
Certainly. Given an arithmetic progression with first term a and common difference d, choose m so that 3^m > a+d. There will be k such that 2*3^m < a+kd < 3*3^m. Figure how to find k. – The Masked Avenger Mar 5 '14 at 15:12

Your Answer


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.