# Tchoukaillon hooks

2022-03-19, post № 256

Ever since watching D. Knuth’s talk “Tchoukaillon numbers” [1] in the Rutgers experimental mathematics seminar back in January of 2022, I was intrigued by the algorithm he presented to iteratively generate the Tchoukaillon arrays ꚓ⁽ⁿ⁾. Their discrete pointwise limit defines a two-dimensional permutation of the natural numbers, whereby pointwise exactly one value is attained more than once. These properties make calculating the discrete limit expressible as a lazy computation:

tcheInf i j = discreteLimit $\n -> tche n i j Despite the seeming simplicity of iteratively taking hooks from an $\infty\times n$-matrix, two-dimensional problems seem to require extra scrutiny when approached with a linear data model, even more so without arbitrary jumps. To not transpose too often — thereby invalidating the previous computations’ linearity — I took the approach of linearly evaluating a micro-DSL to express each finitely wide tche n as finite chunks of tcheFlat n :: [Int]: tcheFlat 1 = [1..] tcheFlat n = eval (cycle actions)$ tcheFlat (n-1) where
actions = concat [[flat (n-m), grab (n-m-1,m)] | m <- [1..n-1]]

tche n i j | j <= n    = (chunksOf n \$ tcheFlat n) ## i ## j
| otherwise = -n

Of course left in the dust by the closed-form formula, D. Knuth’s table’s corner element is computationally viably accessible using this method:

*Main> tcheInf 32 32
2093

Source: tche.hs

Extra assets: tche-inefficient.hs

## Footnotes

1. D. Knuth: Tchoukaillon numbers. Rutgers experimental mathematics seminar, 2022-01-27. Online: https://sites.math.rutgers.edu/~zeilberg/expmath/archive22.html [accessed 2022-03-19].
Jonathan Frech's blog; built 2024/05/27 06:43:58 CEST