endolith/fusc.py

## readme.md

      
    Raw
  

              readme.md
            
          
    See The oddest numbers
Sanity check:
In [1]: print [fusc(x) for x in range(92)]
[0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 6, 5, 9, 4, 11, 7, 10, 3, 11, 8, 13, 5, 12, 7, 9, 2, 9, 7, 12, 5, 13, 8, 11, 3, 10, 7, 11, 4, 9, 5, 6, 1, 7, 6, 11, 5, 14, 9, 13, 4, 15, 11, 18, 7, 17, 10, 13, 3, 14, 11, 19, 8, 21, 13, 18, 5, 17, 12, 19]

matches the Encyclopedia of Integer Sequences A002487 Stern's diatomic series (or Stern-Brocot sequence)
Sanity check:
a = calkin_wilf()
print([a.next() for x in range(50)])
[(1, 1), (1, 2), (2, 1), (1, 3), (3, 2), (2, 3), (3, 1), (1, 4), (4, 3), (3, 5), (5, 2), (2, 5), (5, 3), (3, 4), (4, 1), (1, 5), (5, 4), (4, 7), (7, 3), (3, 8), (8, 5), (5, 7), (7, 2), (2, 7), (7, 5), (5, 8), (8, 3), (3, 7), (7, 4), (4, 5), (5, 1), (1, 6), (6, 5), (5, 9), (9, 4), (4, 11), (11, 7), (7, 10), (10, 3), (3, 11), (11, 8), (8, 13), (13, 5), (5, 12), (12, 7), (7, 9), (9, 2), (2, 9), (9, 7), (7, 12)]

Maybe it should output using fractions module?
Similar: Python implementation of the Gibbons-Lester-Bird algorithm[1] for enumerating the positive rationals

  
## fusc.py
def fusc(n):
    """Return the nth number of Stern's diatomic series recursively"""

    if n == 0 or n == 1:
        return n
    elif n > 0 and n % 2 == 0: # even
        return fusc(n // 2)
    elif n > 0 and n % 2 == 1: # odd
        return fusc((n - 1) // 2) + fusc((n + 1) // 2)
    else:
        raise ValueError ('Input must be a positive integer')


def calkin_wilf():
    """Generate the Calkin-Wilf sequence of rational numbers

    Output is tuples of (numerator, denominator)

    """
    n = 1
    d = 1
    yield (n, d)
    while True:
        n, d = d, 2 * (n // d) * d + d - n
        yield (n, d)
	def fusc(n):
	"""Return the nth number of Stern's diatomic series recursively"""

	if n == 0 or n == 1:
	return n
	elif n > 0 and n % 2 == 0: # even
	return fusc(n // 2)
	elif n > 0 and n % 2 == 1: # odd
	return fusc((n - 1) // 2) + fusc((n + 1) // 2)
	else:
	raise ValueError ('Input must be a positive integer')


	def calkin_wilf():
	"""Generate the Calkin-Wilf sequence of rational numbers

	Output is tuples of (numerator, denominator)

	"""
	n = 1
	d = 1
	yield (n, d)
	while True:
	n, d = d, 2 * (n // d) * d + d - n
	yield (n, d)