login
The lexicographically earliest sequence a(n) = v(x[n]) where x[k], k >= 0, are distinct finite nonnegative integer sequences with |x[k] - x[k+1]| = 1, and v(x) = Sum_{k >= 0} x(k)*b^k + b^(b-1), b = max(deg(x), sup(x)) + 1.
2

%I #13 Mar 28 2023 08:18:24

%S 1,3,5,4,15,16,17,14,11,20,19,18,21,22,23,26,25,24,33,30,27,28,29,32,

%T 31,34,35,107,91,75,71,67,83,87,103,99,115,114,113,112,116,117,118,

%U 119,123,122,121,120,124,108,92,76,77,78,79,95,94,93,109,110,111

%N The lexicographically earliest sequence a(n) = v(x[n]) where x[k], k >= 0, are distinct finite nonnegative integer sequences with |x[k] - x[k+1]| = 1, and v(x) = Sum_{k >= 0} x(k)*b^k + b^(b-1), b = max(deg(x), sup(x)) + 1.

%C This is actually an enumeration and a Hamiltonian path in N[X] = N^(N) = L^p(N; N), the space of all polynomials (or finite sequences, or equivalently sequences with finite L^p norm for any 1 <= p < oo) with coefficients in N = {0, 1, 2, 3, ...}.

%C |x - y| = 1 means that x and y are nearest neighbors for any of these p-norms, i.e., they differ in exactly one component, and by exactly +-1 in that component.

%C The function v(x) assigns a unique positive integer to any polynomial or finite sequence x, and v(x) is strictly increasing with increasing b(x) = max(sup(x), deg(x)) + 1, where as usual deg(x) = sup { k >= 0 : x(k) != 0 }.

%C Thus, by construction, all finite nonnegative integer sequences are listed exactly once, usually in order of increasing b(x) - but it can happen that some not yet listed sequences with smallest b-value are not among the nearest neighbors.

%C Sequence A360450 is a variant where a(n) = Sum_{k>=0} x(k)*b^k with b = 10 instead, when b(x) <= 10. This makes the sequences more human readable and searchable: e.g., polynomials 1 + X, X, 2*X and 1+X*2 would then become 11, 10, 20, 21, ... which is definitely easier to "read".

%H Dan Asimov, <a href="https://mailman.xmission.com/hyperkitty/list/math-fun@mailman.xmission.com/thread/OJ5OVVKVJJBNZ4OCKU24BFIPM7FYFDZO/">Infinite path in Hilbert space covering all integer points</a>, math-fun mailing list, Feb. 20, 2023.

%e The values a(n) correspond to the following sequences:

%e n | a(n) | deg(x) | sup(x) | b(x) | polynomial = sequence x = x[n].

%e ---+------+--------+--------+------+---------------------

%e 0 | 1 | -oo | 0 | 1 | 0 = (0, ...): Only seq. with b = 1.

%e 1 | 3 | 0 | 1 | 2 | 1 = (1, 0, ...)

%e 2 | 5 | 1 | 1 | 2 | 1 + X = (1, 1, 0, ...)

%e 3 | 4 | 1 | 1 | 2 | X = (0, 1, 0, ...): Last seq. with b = 2.

%e 4 | 15 | 1 | 2 | 3 | 2*X = (0, 2, 0, ...)

%e 5 | 16 | 1 | 2 | 3 | 1 + 2*X = (1, 2, 0, ...)

%e 6 | 17 | 1 | 2 | 3 | 2 + 2*X = (2, 2, 0, ...)

%e 7 | 14 | 1 | 2 | 3 | 2 + X = (2, 1, 0, ...)

%e 8 | 11 | 0 | 2 | 3 | 2 = (2, 0, ...)

%e 9 | 20 | 2 | 2 | 3 | 2 + X^2 = (2, 0, 1, 0, ...)

%e 10 | 19 | 2 | 1 | 3 | 1 + X^2 = (1, 0, 1, 0, ...)

%e 11 | 18 | 2 | 1 | 3 | X^2 = (0, 0, 1, 0, ...)

%e 12 | 21 | 2 | 1 | 3 | X + X^2 = (0, 1, 1, 0, ...)

%e 13 | 22 | 2 | 1 | 3 | 1 + X + X^2 = (1, 1, 1, 0, ...)

%e 14 | 23 | 2 | 2 | 3 | 2 + X + X^2 = (2, 1, 1, 0, ...)

%e 15 | 26 | 2 | 2 | 3 | 2 + 2*X + X^2 = (2, 2, 1, 0, ...)

%e 16 | 25 | 2 | 2 | 3 | 1 + 2*X + X^2 = (1, 2, 1, 0, ...)

%e 17 | 24 | 2 | 2 | 3 | 2*X + X^2 = (0, 2, 1, 0, ...)

%e 18 | 33 | 2 | 2 | 3 | 2*X + 2*X^2 = (0, 2, 2, 0, ...)

%e 19 | 30 | 2 | 2 | 3 | X + 2*X^2 = (0, 1, 2, 0, ...)

%e 20 | 27 | 2 | 2 | 3 | 2*X^2 = (0, 0, 2, 0, ...)

%e ...

%o (PARI) L360449=List('x*0); A360449(n)={local(T, Q, P.m=if(P, max(vecmax(Vec(P))+1, #P), 1), P.v=subst(P, 'x, P=P.m)+P^(P-1), S, chk(P, V=P.v)=(!T||V<T)&& !setsearch(S, P)&& [T=V,Q=P]); for(n=#L360449, n, S=if(Q, setunion(S, [Q]), Set(L360449)); my(P=L360449[n], B=P.m); T=0; for(k=1, #P, polcoef(P, #P-k)&& chk(P-x^(#P-k))); T|| for(k=0, #P+1, chk(P+'x^k)&& polcoef(P,k)<B-1&& break); listput(L360449, Q)); L360449[n+1].v}

%Y Cf. A360450.

%K nonn

%O 0,2

%A _M. F. Hasler_, Feb 21 2023