Shisheng

Coding / Math / AI enthusiast.

Recent work

• 2026-06-06 Closed form and asymptotics for the two averages in Exercise 7.2.2.3–306(f)
  Solves Knuth's TAOCP Pre-Fascicle 7A, Exercise 7.2.2.3–306(f), the two averages produced by interval-list method (b) over random Dyck-path level sequences. The saved-interval count has the exact closed form T_r(m) = (4^m − (m+3)C_m)/2, so E[r_t] ∼ √(πm)/4. The gap l_t − s_t averages ½log m + (3γ/2 − 1) + smaller terms — essentially half a harmonic number plus (γ − 1) — with limiting law Pr[d_t = k] → 1/((k+1)(k+2)). The exact gap total has generating function T_d(z) = 𝔏(R)/z with 𝔏 the divisor Lambert series and R = zA(z)², so the number-of-divisors function d(N) governs it and T_d is not D-finite, obstructing any uniform bijection. Derivations by first-arch decomposition, generating functions, and singularity analysis (with an elementary route to the constant), all confirmed by direct enumeration.
• 2026-05-21 Cube-divisibility fails for 5 × n knight-tour generating functions
  Disproves Knuth's TAOCP Pre-Fascicle 8A, Exercise 210 [HM46] — “prove or disprove that Q⁺_m(z) is a multiple of Q_m(z)³ when m ≥ 5” — in the negative at m = 5. Here Q_m and Q⁺_m are the minimum-denominator generating-function polynomials for the closed (Hamiltonian-cycle) and open (Hamiltonian-path) knight-tour counts on the m × n board. For m = 5, Q₅ divides Q⁺₅ and Q₅² divides Q⁺₅, but Q₅³ does not, so the conjectured cube-divisibility fails. The denominators are recovered by Berlekamp–Massey from bignum Hamilton-count sequences (computed by a live-state-pruned, bisimulation-reduced state-space DP) and certified by an independent chain of checks: a random-prime 3-way diff, an exact Z[z] recurrence identity, and a gcd = 1 coprimality test.
• 2026-05-20 Compact trie nodes and pointers for random marked involutions
  Addresses Knuth's TAOCP Pre-Fascicle 8A, Exercise 7.2.2.4–205 [HM46]: closed-form asymptotic expansions, as q → ∞ with n ≥ 1 fixed, of the average node count P_nodes(n, q) = nq + (n−1) − c_n*√q − d_n* + O(q^−1/2) and pointer count P_ptr(n, q) = (n/6)q² − (n/3)q^3/2 + A_nq + B_n√q + O(1) of the compact trie of exercise 204 built from n i.i.d. random length-q marked involutions, with the clean closed form A_n = 5n/2 + H_n + 2c_n* mediated by the alternating-binomial identity ∑_j(−1)^j+1(ⁿ_j)/j = H_n. Verified against exact-rational enumeration through (n, q) = (4, 5) and log-space float64 evaluation through q = 10⁴.
• 2026-05-18 An 11.5n asymptotic upper bound on crossings in closed knight's tours
  Improves the BJMOW (Besa, Johnson, Mamano, Osegueda, 2022) 12n asymptotic upper bound on the minimum number of crossings χ(T_n) of a closed knight's tour on the n × n board to 11.5n. A 4 × 40 template found by constraint programming replaces five adjacent 4 × 8 “heel” templates (140 → 130 crossings), and is interface-preserving so that BJMOW's Hamiltonian-cycle proof carries over unchanged. Addresses Knuth's TAOCP Pre-Fascicle 8A, Exercise 7.2.2.4–161.
• 2026-05-11 SB(3, n) has no Hamiltonian cycle when n is even
  arXiv:2605.09489. Resolves Knuth's TAOCP Pre-Fascicle 8a, Exercise 7.2.2.4–224: the shift-and-save-or-bump digraph SB(3, n) admits no Hamiltonian cycle for even n. A sign-of-permutation obstruction — writing the successor map as f_S = A_b ∘ σ and computing sgn via a dihedral Burnside argument — gives the stronger statement that SB(m, n) has no Hamiltonian cycle whenever m is odd, m ≡ 3 (mod 4), and n is even. Included in TAOCP Pre-Fascicle 8A.
• 2026-05-07 Nonexistence of whirling-knight tours at half coil count for n ≡ 4, 6 (mod 8)
  arXiv:2605.04603. Settles a conjecture of Beluhov: whirling knight's tours (Hamiltonian cycles in the counterclockwise-knight digraph on the n × n board) with coil count c = n/2 do not exist for n ≡ 4 (mod 8), n ≥ 4, or n ≡ 6 (mod 8), n ≥ 6. The proof gives Farkas dual certificates for a cycle-cover LP relaxation, with structurally distinct certificates for the two residue classes. Included in TAOCP Pre-Fascicle 8A.
• 2026-05-01 A note on the parameter ℓ in Buchbinder–Feldman's deterministic submodular matroid algorithm
  arXiv:2604.27362. Two purely elementary tightenings of the bound on (1+1/ℓ)^−ℓ shrink the hidden constant in the Õ_ε(nr) query complexity of Buchbinder–Feldman's deterministic (1−1/e−ε)-approximation by a factor ≈ 2^0.816/ε. Lean 4 formalization at github.com/daizisheng/bf24-note. Listed as an associated resource on Moran Feldman's publications page.
• 2026-04-19 TAOCP Pre-Fascicle 8A, Exercise 11
  A closely related published result, and a small correction to the answer — on Hamiltonian paths in generalized Petersen graphs GP(2q, 2).
• 2026-04-18 TAOCP Pre-Fascicle 8A, Exercise 65
  A search for the smallest Hamiltonian graph on which Warnsdorff's Algorithm W always fails. Tight lower bound: n ≥ 14, with exactly seven non-isomorphic counter-examples at n = 14. Included in TAOCP Pre-Fascicle 8A.
• 2026-04-11 TAOCP Pre-Fascicle 9B, Exercise 89
  Complete proof that the Pythagorean triple (20, 21, 29) admits no 4-piece discrete Pythagorean dissection. Included in TAOCP Pre-Fascicle 9B.