OFFSET
0,3
COMMENTS
This represents a Hamiltonian path and an enumeration of all finite nonnegative integer sequences, or polynomials in N[X], N = {0, 1, 2, ...}, or equivalently, sequences in N^N with finite L^p-norm, such that any two consecutive terms are nearest neighbors for the L^p norm, with any 1 <= p < oo.
|x - y| = 1 (for any of these L^p norms) means that x and y differ in exactly one component, and by exactly +-1 in that component. Given this constraint, the path can only reach sequences with a finite number of nonzero components (a.k.a. polynomials), when the initial sequence has this property.
As usual, deg(x) = sup { k >= 0 : x(k) != 0 } >= -oo.
In order to list this sequence of sequences in a human-readable and searchable format, we represent them as the base-b number v(x) with b = 10 as long as m(x) < 10, so that all sequences with m(x) < 10 correspond to the decimal number having the terms of the sequence as digits. When m(x) >= 10 (which happens around n ~ 10^10) we use b = m(x) + 1, and add the term b^(b-1) in order to make the representation unambiguous. See A360449 for a different encoding of the same sequence of polynomials, which always uses b = m(x) + 1 and never prefers b = 10 in any way.
In reply to a question raised on the math-fun list, we note that there can be no space-filling path of nearest neighbors with lim |x[n]| = oo when |.| is any of the usual L^p norms, because there are infinitely many points with |x| = 1 for any of these norms. However, we do have this property for the present sequence for any norm with increasing weight for components with larger indices.
The sequence also enumerates all nonnegative integers up to 10^10-1, subject to a similar constraint: consecutive terms differ in exactly 1 digit by exactly +- 1. Thereafter many integers are missing, 10^10 is the smallest of them.
LINKS
Dan Asimov, Infinite path in Hilbert space covering all integer points, math-fun mailing list, Feb. 20, 2023.
EXAMPLE
The values a(n) correspond to the following sequences:
n | a(n) | m | sequence x = x[n]; comment. Note: m = max(deg(x),sup(x))
---+------+-----+----------------------------------
0 | 0 | 0 | 0, 0, 0, ...: The only sequence with m = 0.
1 | 1 | 1 | 1, 0, 0, ...: The first sequence with m = 1.
2 | 11 | 1 | 1, 1, 0, ... (There are 2^2 - 1 = 3 sequences with m = 1.)
3 | 10 | 1 | 0, 1, 0, ...: The last of the 3 sequences with m = 1.
4 | 20 | 2 | 0, 2, 0, ...: The first sequence with m = 2.
5 | 21 | 2 | 1, 2, 0, ... (There are 3^3 - 2^2 = 23 elements with m = 2.)
6 | 22 | 2 | 2, 2, 0, ...
7 | 12 | 2 | 2, 1, 0, ...
8 | 2 | 2 | 2, 0, 0, ...: The "smallest" sequence with m = 2.
9 | 102 | 2 | 2, 0, 1, 0, ...: Earliest sequence with degree 2.
10 | 101 | 2 | 1, 0, 1, 0, ...
11 | 100 | 2 | 0, 0, 1, 0, ...: Smallest sequence with degree 2.
12 | 110 | 2 | 0, 1, 1, 0, ...
13 | 111 | 2 | 1, 1, 1, 0, ...
14 | 112 | 2 | 2, 1, 1, 0, ...
15 | 122 | 2 | 2, 2, 1, 0, ...
16 | 121 | 2 | 1, 2, 1, 0, ...
17 | 120 | 2 | 0, 2, 1, 0, ...
18 | 220 | 2 | 0, 2, 2, 0, ...
...
PROG
(PARI) L360450=List(1); A360450(n)={if(n>1, for(n=#L360450+1, n, my(S=Set(L360450), L=L360450[n-1], D=digits(L), i=0, ok(x)=x && (x<L360450[n]||!L360450[n]) && !setsearch(S, x) && L360450[n]=x); listput(L360450, 0); while(i<#D, D[i++] && ok(L-10^(#D-i))); L360450[n]&& next; i < vecmax(D) && D=Vec(D, -i=vecmax(D)); until(!i-- && !i = #D=Vec(D, -1-#D), D[i] < #D-1 && ok(L+10^(#D-i)) && next(2))); L360450[n], n)}
(Python)
def A360450(n, A=[0]):
while n >= len(A):
L = A[-1]; S = str(L); m = len(S); P = 10**m
while M := L % P:
P //= 10
if M >= P and L - P not in A: L -= P; break
else:
P = 1; m = max(int(max(S)), m); M = 10**m
while True:
if L//P % 10 < m and L + P not in A: L += P; break
P *= 10
if P == M: M *= 10; P = 1
A += [L]
return A[n]
CROSSREFS
KEYWORD
nonn
AUTHOR
M. F. Hasler, Feb 21 2023
STATUS
approved