This site is supported by donations to The OEIS Foundation.
User:M. F. Hasler/Work in progress/Enumeration of integer sequences
From OeisWiki
Idea: construct a Hamiltonian path of nearest neighbors filling the space in A[X] = Lp(N,A) where A = Z or N (= nonnegative integers), 1 ≤ p < ∞.
Definitions
- Nonnegative integers N = {0, 1, 2, ...}, a.k.a. natural numbers.
- Sequences where ; we also write x(k) for xk.
- degree: deg(x) := sup { k ∈ N | xk ≠ 0 } ∈ N ∪ { ± ∞ }?
- finite sequences = polynomials = A[X] = { x ∈ AN | deg(x) < ∞ } = { P = ∑0 ≤ k ≤ deg(x) xk Xk }. (But then even if P = x we have P(k) ≠ x(k); P(k) means subsitute X = k.)
- L^p norm: . Since A ⊂ Z, deg(x) < oo <=> |x|p < oo, as long as 1 <= p < oo, since then each nonzero term in the sum is ≥ 1.
- For p = oo we mean |x|oo = sup|x| = sup { |xk| ; k ≥ 0 }, which is finite for bounded, but not only for finite sequences.
- Nearest neighbors: x, y ∈ AN such that |x-y|p = 1 <=> x and y differ in exactly one component, and by ±1 in that component, as long as p < oo.
The idea
To fill the space we construct a sequence starting from 0 and always appending the smallest nearest neighbor not seen earlier, where "small" refers to some order relation. Most natural seems:
- if we order first by degree only, we have to visit all infinitely many polynomials of degree 0 before we visit the first polynomial of degree 1: impossible -- we'll never see those (with degree ≥ 1).
- if we order first by L^p norm only, we have to visit all infinitely many polynomials with |x| = 1 before we visit the first one with |x| = 2: impossible -- we'll never see those (with |x| > 1).
- Therefore we order by increasing m(x) = max(deg(x), |x|_p) where we may also (and preferrably do) choose p = oo.
- Then we have to add a tie-breaker for sequences with equal m(x).
- One natural idea is to use v(x) = sum x(k)*b^k for some b: This v(x) uniquely gives back the x(k) if 0 ≤ x < b.
- So we should use b > |x|_oo = sup(x) for sequences with nonnegative coefficients; a natural choice seems b = m(x) + 1.
- If negative coefficients may occur, we could "shift" these up by m(x) so that -1, ..., -m become m+1, ..., 2m; and use b = 2m+1 instead.
- It is then a priori not possible to get back b from v(x) only, without knowing the b-value used to get this v(x).
- (For example, v(x) = 3 for x = (3, 0, ...) but also for x = (1, 1, ...) (b = 2 since m = 1) .
- But we can add an additional term large enough to uniquely determine b, for example, b^(b-1).
- (The largest value of v(x) that may and will occur is b^(b-1) - 1, namely, if there are b-1 = deg(x) terms each of which equals b-1 = sup |x|.)