# Generating necklaces by the FKM algorithm # of Fredricksen, Kessler and Maiorana. # See F. Ruskey, C. Savage, and T. M. Y. Wang, # "Generating necklaces", Journal of Algorithms, # 13(3), 414 - 430, 1992. # (SageMath) def A054630_count(n, k): a = [0]*(n+1) #print "".join(map(str,a[1:])) count = 1; i = n if k == 1: return 1 while true : a[i] += 1 for j in (1..n-i): a[j+i] = a[j] if n % i == 0: count += 1 #print "".join(map(str,a[1:])) i = n while a[i] == k-1: i -= 1 if i == 0: break return count for n in (1..6): print [A054630_count(k, n) for k in (1..n)] # _Peter Luschny_, Aug 12 2012 # (Julia) function A054630Generate(n::Int, k::Int) necklace(a) = join(map(string, a[2:end])) a = fill(0, n+1) #println(necklace(a)) count = 1; i = n k == 1 && return 1 while i > 0 a[i+1] += 1 for j in 1:n-i a[j+i+1] = a[j+1] end if n % i == 0 count += 1 #println(necklace(a)) end i = n while a[i+1] == k-1 i -= 1 end end return count end for n in 1:6 println([A054630Generate(k, n) for k in 1:n]) end # _Peter Luschny_, Sep 10 2018