[seqfan] Re: Ralf's recurrence for off bits of n
Ray Chandler
rayjchandler at sbcglobal.net
Sun May 21 19:47:38 CEST 2017
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/
More information about the SeqFan
mailing list