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

Alonso Del Arte alonso.delarte at gmail.com
Sun May 21 17:46:49 CEST 2017

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.


Alonso del Arte
Author at SmashWords.com
Musician at ReverbNation.com <http://www.reverbnation.com/alonsodelarte>

More information about the SeqFan mailing list