Created
November 7, 2022 22:42
-
-
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. :)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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