Self-recursive generators (Python recipe) by David Eppstein

ActiveState Code (http://code.activestate.com/recipes/221457/)

Another one.

def A000069():
    '''Odious numbers: numbers with an odd number of ones in their binary representation.
For more info, see http://www.research.att.com/projects/OEIS?Anum=A000069'''
    yield 1
    for x in A000069():
        if x & 1 and x > 1:
                yield 2*x - 1
        yield 2*x
        if not (x & 1):
            yield 2*x + 3

Non-Recursive A003714(). A003714() fascinates me because I don't understand how it works. But I do understand

a little about its execution. It causes the "yield stack" depth to grow without bound.

When calculating the nth Fibbinary number the "yield stack" depth for A003714() is

approximately the log base 2 of n. For my own amusement I eliminated the recursion and

hence the unbounded "yield stack" as follows:

def A003714nr():
    """
    Fibbinary numbers (no consecutive ones in binary representation).
    For more info see   http://www.research.att.com/projects/OEIS?Anum=A003714
    http://www.research.att.com/~njas/sequences/A003714

    2006/01/09 M - 2006/01/12 Th Bob Hossley
    Eliminate recursion and the "yield stack" depth growing without bound.
    When calcuating the nth Fibbinary number the "yield stack" depth for
    A003714() is approximately the log base 2 of n.

    The algorithm used by A003714nr() is simple:  Begin with 0.  To calculate
    the next integer in the Fibbinary sequence, add 1 to the previous Fibbinary
    number.  Then skip all non-Fibbinary numbers by adding 2**n
    whenever the result contains ones in positions 2**n and 2**(n+1).  Because
    the previous Fibbinary number is guaranteed not to have consecutive one's
    in its binary representaion, the consecutive ones check can stop as soon
    as three consecutive binary digits are encountered that do not contain two
    consecutive ones.

    Generator context saving preserves local variables Last, LoopCnt, Mask1,
    and Mask2 between yield and continue from yield but only variable Last
    needs to be preserved.
    """

    Last = 0
    LoopCnt = 2
    while (1):
        if (LoopCnt > 1):
            yield Last
            Last += 1
            Mask1 = 1
            Mask2 = 2
            LoopCnt = 0
        if (Last & Mask1) and (Last & Mask2):
            Last += Mask1
            LoopCnt = 0
        else:
            LoopCnt += 1
        Mask1 *= 2
        Mask2 *= 2

A003714() and the zeroth Fibbinary number. A003714() skips the zeroth Fibbinary number, which is zero.

I modified A003714()to make it return the zeroth Fibbinary number.

This is an inelegant kludge:

def A003714x():
    """
    Fibbinary numbers (no consecutive ones in binary representation).
    For more info see http://www.research.att.com/projects/OEIS?Anum=A003714
    http://www.research.att.com/~njas/sequences/A003714

    2006/01/17 Bob Hossley
    Change:  Return A(0) = 0.
    """

    try:
        A003714x.A0
    except AttributeError:
        A003714x.A0 = True
        yield 0

    yield 1
    for x in A003714x():
        yield 2*x
        if not (x & 1):
            yield 2*x+1

A003714x() Bug. A003714x() only includes A(0) in the first sequence it generates.

This bug can be worked around in the code that uses A003714x() by deleting the

control variable between each use of A003714x(). For example:

loops = 0
for seqVal in A003714x():
    print "Fibbinary(", loops, ")=", seqVal
    loops += 1
    if (loops > 10): break

del A003714x.A0 # Kludge to delete control variable
loops = 0
for seqVal in A003714x():
    print "Fibbinary(", loops, ")=", seqVal
    loops += 1
    if (loops > 10): break

But this does not a fix the bug. I don't know how to change A003714()

to include A(0) in the sequence. I don't allow adding a function argument to

A003714(). The "yield statement" magic hides the generator initialization.

If I knew how to rewrite A003714() without yield statements, then I would use

itertools and the generator initialization would be exposed. I would initialize

a control variable in the generator initialization and this problem would solved.

But at this time, I have no solution.