[seqfan] Re: Ralf's recurrence for off bits of n

[Vladimir Shevelev]

Dear Al,

You are right: for 2n it is sufficient to remove only
 "- (n mod 2)".
Indeed,  if n=2^k, then the formula a(2n)=a(n)+1
is trivial (k+1=k+1). Otherwise,
set A029837(n)=b(n), A000120(n)=c(n).
By formula a(n)=b(n+1)-c(n), mentioned by Antti,
we have a(2n)=b(2n+1)-c(2n)=b(n)+1-c(n).  
But if n>=3 is not a power of 2, then
b(n)=b(n+1) and a(2n)=b(n+1)-c(n)+1=a(n)+1.

Best regards,
Vladimir
________________________________________
From: SeqFan [seqfan-bounces at list.seqfan.eu] on behalf of Ray Chandler [rayjchandler at sbcglobal.net]
Sent: 21 May 2017 20:47
To: 'Sequence Fanatics Discussion list'
Subject: [seqfan] Re: Ralf's recurrence for off bits of n

Alonso,
I agree you should remove the -(n mod 2) part for a(2n).

The PARI code would translate to (for the even case)
a(2n) = a(floor(2n/2)) + 1 - mod(2n,2) = a(n) +1.
Ray Chandler


> -----Original Message-----
> From: SeqFan [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of Alonso
> Del Arte
> Sent: Sunday, May 21, 2017 10:47 AM
> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
> Subject: [seqfan] Ralf's recurrence for off bits of n
>
> A year ago, Neil remarked that Ralf's recurrence for the significant off bits of
> n (A080791) might be wrong.
>
> a(2n) = a(n) + 1 - (n mod 2), a(2n+1) = a(2n) - 1. - Ralf Stephan
> <http://oeis.org/wiki/User:Ralf_Stephan> from Cino Hillard's Pari program,
> Dec 16 2013
>
> I am now convinced that it is indeed wrong, at least for the even n part of it.
> Try it for a(6), for which we immediately know the correct answer is 1.
>
> a(2 * 3) = a(3) + 1 - (3 mod 2) = 0 + 1 - 1 = 0.
>
> Maybe this can be salvaged by some tiny adjustment, which is why I hesitate
> to simply delete the whole line. Maybe it should just be a(2n) = a(n) + 1, with
> no mod operation at all.
>
> I know next to nothing about PARI, but I still believe Cino's program is correct
> and that there might be some subtlety Ralf misunderstood in trying to derive
> a formula from it.
>
> As for the odd part of the recurrence, that's obviously correct. By adding
> 1 to an even integer, the least significant bit is turned on, reducing the
> number of off bits by 1 and increasing the binary weight of the number by 1.
>
> Al
>
> --
> Alonso del Arte
> Author at SmashWords.com
> <https://www.smashwords.com/profile/view/AlonsoDelarte>
> Musician at ReverbNation.com
> <http://www.reverbnation.com/alonsodelarte>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/


--
Seqfan Mailing list - http://list.seqfan.eu/