Skip to content

Instantly share code, notes, and snippets.

@orlp

orlp/first_with_div.py Secret

Last active January 1, 2017 22:31
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 orlp/0fbb7784782712bc7c411aa58a188143 to your computer and use it in GitHub Desktop.
Save orlp/0fbb7784782712bc7c411aa58a188143 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
first_with_div.py
import sympy
def first_with_div(n):
n_divs = sympy.divisors(n)
d_divs = {d: [e for e in n_divs if e <= d and not d % e] for d in n_divs}
T = {n: 2**(n-1) for n in n_divs}
best = T[n]
for m in range(2, 1+n.bit_length()):
T = {n: min(T[d]*sympy.sieve[m]**(n//d - 1) for d in d_divs[n])
for n in n_divs}
best = min(T[n], best)
return best
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment