[seqfan] Re: Binary digits change sequences

[Antti Karttunen]

On 8/13/19, Ali Sada via SeqFan <seqfan at list.seqfan.eu> wrote:
> Hi Everyone,
>
>
> Please see the sequences below. I just want to check if they were
> “legitimate” to be added to OEIS.
>
> The definition “Number of digits that change when we multiply natural numbers
> by 2 in the binary system” gives us:
>
> 2,2,2,2,4,2,2,2,4,4,4,2,4,2,2,2,4,4,4,4,6,4,4,2,4,4,4,2,4,2,2,2,4,4,4,4,6,4,4,4,6,6,6,4,6,4,4,2,4,4,4,4,6,4,4,2,4,4,4,2,4,2,2,2,4,4,4,4,6,4,4,4,6,6,6,4,6,4,4,4,6,6,6,6…….
>
>  (For example.101*10=1010. All 4 digits changed, so a(5)=4.)
>
> I couldn’t find this sequence. However, when I divided each term by 2, I got
> A069010 (except for the zero at the start.)

This follows from the PARI-code given for A069010 by Gheorghe Coserea:

a(n) = (1 + (hammingweight(bitxor(n, n>>1)))) >> 1;

Multiplying by 2 means shifting the binary representation one step
left, while the above code shifts it first one step right. Taking the
Hamming weight of two numbers xored together is equivalent of your
"number of digits that change in base-2". In the above code 1 +
compensates for the righmotst bit which is lost in the shift n>>1,
while the final >> 1 is equal to division by 2.


>
>
>
> Also, with the same definition but multiplying by 3 instead of 2, I got
>
> 1,1,2,1,2,2,2,1,2,2,3,2,3,2,2,1,2,2,3,2,3,3,3,2,3,3,3,2,3,2,2,1,2,2,3,2,3,3,3,2,3,3,4,3,4,3,3,2,3,3,4,3,4,3,3,2,3,3,3,2,3,2,2,1,2,2,3,2,3,3,3,2,3,3,4,3,4,3,3……
>
> Which is A007302, except for the initial zero again.
>

This interpretation is also already there as a comment:

a(n) is also the number of ones in the binary representation of the
number given by the function XOR(n, 3n) where n is expressed in base
2. - Ramasamy Chandramouli, Aug 20 2010

>
>
> When I repeated the definition, multiplying by 4 this time, I got
>
> 2,2,4,2,2,4,4,2,4,2,4,4,4,4,4,2,4,4,6,2,2,4,4,4,6,4,6,4,4,4,4,2,4,4,6,4,4,6,6,2,4,2,4,4,4,4,4,4,6,6,8,4,4,6,6,4,6,4,6,4,4,4,4,2,4,4,6,4,4,6,6,4,6,4,6,6,6,6,6,2….

These are Hamming weights of A048725 (i.e., number of 1-bits in their terms)

>
> Maybe I didn’t look well, but I couldn’t find this one even when I divided by
> 2.
> (Is multiplying by even numbers always gives us even numbers of digit
> changes? And if so,why?)

Not true for all even numbers, but only for the powers of 2, as then
you are just shifting by some amount, and then it should be quite
obvious why there are even numbers of positions where the bits are not
same.

>
> I am working on multiplying by more numbers. I am also working on
> base-3,4,5,… systems.
>
> I would appreciate any feedback.

I suggest starting reading from https://en.wikipedia.org/wiki/Gray_code
and then follow any links you find interesting there.
(It's https://oeis.org/A003188 in OEIS).

Best regards,

Antti

>
>
>
> Best,
>
>
>
> Ali
>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>