Skip to content

Instantly share code, notes, and snippets.

@ShinNoNoir

ShinNoNoir/necklace.py

Created May 23, 2017 13:11
Show Gist options
  • Save ShinNoNoir/3533f0fb447f5bb0330d5cb32416e9bd to your computer and use it in GitHub Desktop.
Save ShinNoNoir/3533f0fb447f5bb0330d5cb32416e9bd to your computer and use it in GitHub Desktop.
Download ZIP
Number of necklaces (combinatorics)
Raw
necklace.py
# https://en.wikipedia.org/wiki/Necklace_%28combinatorics%29#Number_of_necklaces
from eulerlib import Divisors
def N(k, n):
divs = Divisors()
return sum( divs.phi(d) * k**(float(n)/d) for d in divs.divisors(n) ) / float(n)
@ShinNoNoir
Copy link
Author

Alternative:

from fractions import gcd
N = lambda k, n: sum(k**gcd(n,i) for i in xrange(1, n+1)) / n

(Based on slide 9 of http://teaching.csse.uwa.edu.au/units/CITS7209/polya.pdf)

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