Skip to content

Instantly share code, notes, and snippets.

@endolith
Created May 18, 2009 04:05
Show Gist options
  • Save endolith/113310 to your computer and use it in GitHub Desktop.
Save endolith/113310 to your computer and use it in GitHub Desktop.
Python function for generating the nth number of Stern's diatomic series recursively

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

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)
@rosemichaele
Copy link

Any idea why your generator for the Calkin-Wilf sequence is so much faster than mine here?

The millionth rational number in the sequence is [191, 1287], and it takes mine about 15 seconds to find that out, while yours is sub-second. I'm confused because both seem to be based on:

Would use of the fractions module slow down performance that significantly?

@roman-shuhov
Copy link

@rosemichaele i think the issue is division, I didn't use Fractions but my was also slow until i eliminated division operation.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment