Shisheng

Coding / Math / AI enthusiast.

Recent work

• 2026-06-19 Stappers's construction yields all maximum 3-uncolourability-preserving edge sets of the pinched Sierpiński gasket graph
  Proves a conjecture recorded in Knuth's TAOCP Pre-Fascicle 7A, Answer to Exercise 7.2.2.3–227. Identifying two of the three corners of the Sierpiński gasket graph S_n⁽³⁾ yields the pinched graph Ŝ_n⁽³⁾, which is not 3-colourable; an edge set is removable if deleting it leaves the graph still not 3-colourable. Knuth records Filip Stappers's construction of 2ⁿ⁻¹ removable sets of 2ⁿ⁻¹+1 edges each and asks whether these are all the largest removable sets (verified only for n ≤ 4). The answer is yes: using the gasket self-similarity (S_n is three corner-glued copies of S_n−1), the question reduces to a finite transfer system on the 15 realizable corner-colour spectra, closed under the gluing composition, whose cost-optimal decompositions are eventually constant. A short induction gives maximum removable size 2ⁿ⁻¹+1 with exactly 2ⁿ⁻¹ such sets for every n ≥ 3 — matching Stappers's count, so his sets are all of them (the case n = 2 is exceptional, with μ₂ = 2, ν₂ = 1).
• 2026-06-18 Densities of label-d cells in Fillomino patterns: exact values and constructions for d ≤ 25
  Addresses Knuth's TAOCP Pre-Fascicle 7A, Exercise 7.2.2.3–296, which asks for the maximum density δ_d of label-d cells in a plane Fillomino labelling and tabulates lower/upper bounds for each d ≤ 25. Determines δ_d for 13 further values: a short combinatorial counting argument sharpens the slack 1/2 upper bound to meet the construction at d = 1 (3/8) and d = 2 (4/9), and an explicit periodic pattern on a skew lattice meets the halo upper bound d/(d+h_d), with h_d = ⌈√(8d−4)⌉/2, for d = 4, 7, 9, 12, 14, 16, 17, 19, 22, 23, 24. The lower bound is also strictly improved without yet closing the gap for d = 3 (1/2 → 18/35), 6 (3/5 → 18/29), 10 (2/3 → 40/59), and 20 (5/7 → 20/27). Altogether δ_d is pinned down for 19 of the 25 values, leaving d = 3, 6, 10, 15, 20, 21 open. Every construction is verified wrap-free: lifting one fundamental domain to ℤ², every monochromatic rook-component has size exactly equal to its label, with no wrap-around.
• 2026-06-13 Every natural number is a sum of distinct semiprime unit fractions
  arXiv:2606.15159. Proves that every natural number is a finite sum of distinct unit fractions whose denominators are semiprimes (products of two distinct primes) — the ω = 2 integer case of a problem of Erdős and Graham, conjectured by Butler, Erdős and Graham (Integers 15 (2015), A51), who proved the ω = 3 analogue. Counterintuitively the problem hardens as ω decreases — the induction's feed thins — so ω = 2 is the hard case; adapting the Butler–Erdős–Graham induction to this thin-feed regime reduces the entire induction step to an explicit onset inequality Y₀(N) ≤ β(N), proved for all N ≥ 10 via Olson's addition theorem and elementary Chebyshev bounds. The same engine extends to the rationals (every a/b with squarefree b above an explicit threshold is ω = 2 representable, unconditionally) and yields the first complete proof of the rational ω = 3 statement — every a/b with squarefree b is a sum of distinct sphenic unit fractions — that Butler, Erdős and Graham left unpublished. What remains open is the ω = 2 regime below the threshold, reduced to a single explicit conjecture on the gap-free floor of semiprime subset-sum sets.
• 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.