Conjectures 111-113 from "100 Conjectures from the OEIS"

[Max A.]

On 1/5/07, Max A. <maxale at gmail.com> wrote:

>> %C A083905 Conjecture: a(3*A006288) = 0.

> Conjecture 113 seems to be given in a wrong direction in your paper.
> You ask to prove that if a(3k)=0 then k belongs to A006288. But it is
> opposite to proving that a(3*A006288) = 0.

This is a proof to the corrected Conjecture 113 given by RIP from
russian forum http://lib.mexmat.ru/forum/

Let n = \sum_{k=0}^m e_k 2^k be a binary representation of n such that e_m = 1.
Then A083905(n) = a(n) = \sum_{k=0}^m (1-e_k)*(-1)^k (can be shown by
induction on m). In other words, a_n equals the difference between the
number of zeros at even positions and the number of zeros at odd
positions in the binary representation of n.

Let k = \sum_{l=0}^M g_l 4^l where g_l from {-1,0,1}.
Then k can represented as the sum of one or several numbers of the
form 4^t and possibly the number S = (4^m - \sum_{j\in J} 4^j) * 4^s,
where J is a subset of {0,1, ..., m-1} and J contains 0.

It is clear that 3*4^t=(110..0)_2 (the binary representation) where
the number of trailing zeros is 2t. At the same time,
3S = (2*4^m + 3*(4^m-4)/3 - 3\sum_{j\in J'} 4^j + 1)*4^s
= (2*4^m + 3\sum_{j\in J''} 4^j + 1)*4^s = (10...010...0)_2
where J'=J\{0} and J''={1,2,...,m-1}\J. In the binary representation
of 2S the former "..." constitutes a number of pairs 00 or 11, and the
number of trailing zeros is 2s.

Now it is easy to obtain a binary representation of 3k and check that
a(3k)=0. For example, if
k = 4^7 - 4^6 - 4^4 + 4^3 + 4^2 - 4 + 1 = (4^3-4^2-1)*4^4 + 4^3 + (4-1)*4 + 1,
then
3k = (2*4^3+3*4+1)*4^4 + 3*4^3 + (2*4+1)*4 + 3 = (1000110111100111)_2.
It is crucial to notice that the unit digits in different summands are
located at different places.

In general, it can be shown that a(3k)=0 if and only if in the base-4
representation of n=3k there is the same amount of digits 1 and 2, and
the leading digit is different from 1.

Max



Hello seqfans,

I've noticed (and proved) that the number of 01-avoiding words of length n on alphabet {0,1,2,3, ..., d} which do not end in 0 can be easily described. The sequence starts with 1, d and follows the recursion a(n) = (d+1)*a(n-1) - a(n-2).

I am submitting this comment to the relevant sequences.

My question is - if this comment is not present in the sequences should I assume that this is something new? If it is something new what is the standard way to publish small results like this?

Best, Tanya