[seqfan] Re: Observation on the parity of A171791 and A233312
Vladimir Shevelev
shevelev at bgu.ac.il
Sat Jan 16 10:48:34 CET 2016
Dear Jörgen,
Thank you for reminder and effective
using in your proof the function C(n).
Could you submit it in OEIS?
Best regards,
Vladimir
________________________________________
From: SeqFan [seqfan-bounces at list.seqfan.eu] on behalf of Joergen Backelin [joeb at math.su.se]
Sent: 15 January 2016 00:15
To: seqfan at list.seqfan.eu
Subject: [seqfan] Re: Observation on the parity of A171791 and A233312
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
_______________________________________________
Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan
mailing list