Skip to content

Instantly share code, notes, and snippets.

@outofmbufs
Created November 7, 2022 22:42
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save outofmbufs/c05afe04e79bf34d8931b40c44a6daa2 to your computer and use it in GitHub Desktop.
Save outofmbufs/c05afe04e79bf34d8931b40c44a6daa2 to your computer and use it in GitHub Desktop.
Generator for OEIS sequence A092317. I don't know why I like making these, but I do. :)
from fractions import Fraction
from math import gcd
# compute the sequence OEIS A092317
# https://oeis.org/A092317
def _slowway(n):
b = Fraction(0)
i = 3
while b < n:
b += Fraction(1, i)
i += 2
return i - 2
def _fasterway(n):
# instead of using Fraction, just do the fractions manually.
# this is "faster" but it is still far from fast. Computing n==6
# will take a good amount of time and n==7 is stupid.
numerator = 0
denominator = 1
i = 3
while numerator < (denominator * n):
numerator, denominator = (numerator * i) + denominator, denominator * i
i += 2
# operating on unnecessarily-large integers gets slower as they
# get larger, but computing the gcd to prevent that also takes time.
# Experiments showed it is faster to let the numbers get
# "unnecessarily big" (btw: they get HUGE) instead of using gcd to
# reduce them every time. But eventually the gcd reduction becomes
# worth it. This "once every 10000" was determined empirically.
# There must be a better way.
if (i % 10000) == 1:
cd = gcd(numerator, denominator)
if cd > 1:
numerator //= cd
denominator //= cd
return i - 2
def generate_A092317():
i = 1
while True:
yield _fasterway(i)
i += 1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment