[seqfan] Re: Observation on the parity of A171791 and A233312

Joergen Backelin joeb at math.su.se
Thu Jan 14 23:15:30 CET 2016


Jeremy, according to the comments for A171791 by
Sean Irvine (and a careful reading of the
definitions), the equivalence

 (0) A23312(n) is even iff A171791(n+1) is odd

 holds for at least the
first 1028 terms. The reason, put very briefly, is
that

 (1) A233312(n) is even if and only if n is the double of a "fibbinary number".

 I'll give a proof of (1) (vide infra), but I fear
that it gets a bit long, because the definitions are
a bit involved. Since Sean has checked that for
n=1..1028 A(171791(n) is odd if and only if n is 1
more than twice a fibbinary number, your observation
indeed should hold for these n.



Proof of (1):
Vladimir Shevelev essentially defines two positive
integers to be "c-equivalent", if their ordinary
binary representations have the same lengths, and
they have the same multiset of lengths of "zero
gaps", by which I mean the numbers of bits 0 between
two bits 1 with no other bit 1 between them, and
also the number of zeros after the rightmost unit.
(This he does by comments and examples for A233249,
in slightly different terms.)

An example: The numbers 1353 (binary 10101001001)
1226 (binary 10011001010) are c-equivalent, since
their ordered sequences of zero gap lengths are
(1,1,2,2,0) and (2,0,2,1,1), respectively, and both
represents orderings of the multiset {0,1,1,2,2},
which in the usual multiset notation is written as
{0,1^2,2^2}.

Vladimir repeatedly seems to consider the function
mapping each positive integer n to the smallest
integer c-equivalent to n. Let us call this function
C(n). Curiously enough, Vladimir seems not to have
contributed C itself to OEIS; but A114994 consists
of its range. (A163382 is the `closest' sequence to
C(1),C(2),...; in fact, A163382(n) = C(n) for
n=1..37, and this equality holds for an infinite
number of n. Actually, any n is c-equivalent to
A163382(n), but that equivalence only may employ
cyclic permutation of the ordered sequence of zero
length gaps. Since 38 = 100110_binary has a zero gap
sequence (2,0,1), and this cannot be cyclically
permuted to the zero gap sequence (2,1,0) for 37,
C(38) = 37 != 38 = AA163382(38).)

For each n, the ordered sequence of zero gap lengths
for C(n) is achieved by sorting the zero gap
lengths of n in decreasing order. This directly
yields

 (2) The number C(n) is odd iff n containss a zero gap of length 0.

The same goes for A233312(n). This number is defined
by concatenating the binary representation of n with
itself, which represents a number, namely
A020330(n); and then applying the function C to the
result. In other words,

 (3) A233312(n) = C(A020330(n)) for each n.

Now, when you "double" a binary string, you also
double the number of zero gaps with a given length;
wjence e. g. both A020330(1353) and A020330(1226)
have the zero gap lengths multiset {0^2,1^4,2^4}.
Therefore, and by (2), we have

 (4) A233312(n) is even iff n contains no empty zero gap.

Now we're almost done! We just have to interpret
"fibbinarity" in terms of zero gap lengths. Now, a
positive number k is fibbinary if and only if k
contains no empty zero gaps, except possibly at the
rigth end of its binart representation. Since
moreover k is fibbinary if and only if 2*k is
fibbinary, and the rightmost zero gap of n has a
positive length if and only if n is even, indeed we
have

 (5) The positive number n contains no empty zero gap iff n = 2*k for some fibbinary k.

So, by Paul Hanna's observation and Sean Irvine's
verification, and by (4) and (5), we indeed have the
following equivalences, for 1 <= n <= 1028:

        A233312(n)==0 (mod 2)
  <==>  the binary representation of n contains no empty zero gap
  <==>  n = 2*k for some fibbinary k
  <==>  n+1 = 2*k+1 for some fibbinary k
  <==>  A171791(n+1)==1 (mod 2).

This proves (0) for these n.


All the best!

 Jörgen Backelin



More information about the SeqFan mailing list