Skip to content

Instantly share code, notes, and snippets.

@christian-oudard
Last active September 21, 2022 06:14
Show Gist options
  • Save christian-oudard/d66c4a5de2d2630c3fd673517fc77b43 to your computer and use it in GitHub Desktop.
Save christian-oudard/d66c4a5de2d2630c3fd673517fc77b43 to your computer and use it in GitHub Desktop.
How many ways are there to additively partition a natural number?
# How many unique ways are there to add positive integers to get the number N?
# https://oeis.org/A000041
from itertools import count, chain, islice
def partitions():
"""
>>> list(islice(partitions(), 20))
[1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490]
"""
values = [1]
while True:
yield values[-1]
next_value = 0
for sign, offset in zip(signs(), offsets()):
if offset > len(values):
break
next_value += sign * values[-offset]
values.append(next_value)
def signs():
"""
>>> list(islice(signs(), 8))
[1, 1, -1, -1, 1, 1, -1, -1]
"""
while True:
for s in [+1, +1, -1, -1]:
yield s
def offsets():
"""
>>> list(islice(offsets(), 10))
[1, 2, 5, 7, 12, 15, 22, 26, 35, 40]
"""
offset = 1
for diff in offset_diffs():
yield offset
offset += diff
def offset_diffs():
"""
>>> list(islice(offset_diffs(), 10))
[1, 3, 2, 5, 3, 7, 4, 9, 5, 11]
"""
yield from chain.from_iterable(zip(count(1), count(3, step=2)))
if __name__ == '__main__':
# https://www.youtube.com/watch?v=iJ8pnCO0nTY
index = 665
print(list(islice(partitions(), index, index+1))[0])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment