|
| |
|
|
A220952
|
|
A twisted enumeration of the nonnegative integers.
|
|
8
|
|
|
|
0, 1, 2, 3, 4, 9, 14, 19, 18, 17, 16, 11, 12, 13, 8, 7, 6, 5, 10, 15, 20, 21, 22, 23, 24, 49, 74, 99, 98, 97, 96, 71, 72, 73, 48, 47, 46, 45, 70, 95, 90, 85, 80, 55, 60, 65, 40, 35, 30, 31, 32, 33, 38, 37, 36, 41, 42, 43, 68, 67, 66, 61, 62, 63, 58, 57, 56, 81, 82, 83, 88
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
Initially Don Knuth gave as the definition of this sequence "A sequence that I'm submitting as a problem for publication (see note in comments!)" and the comment that "As soon as a solution is published, I'll provide lots more info; the sequence is so fascinating, it has caused me to take three days off from writing The Art of Computer Programming, but I plan to use it in Chapter 8 some day."
In order for the definition to make sense, it looks like any integer has to be preceded by infinitely many zeros in its base-5 representation. This ensures that the condition is not vacuous for single-digit numbers, so that (except for 0) they also have two adjacent numbers. - Jean-Paul Allouche, Aug 25 2017
[Obviously it is understood that a_i = 0 for all i > log_5(a)+1. But it is sufficient to take all i < log_5(max(a,b))+2, i.e., to consider just one "leading zero" for the larger number, and as many digits for the smaller number. - M. F. Hasler, Mar 13 2018]
The sequence is defined by Knuth as follows.
Say that nonnegative integers a and b are adjacent when their base-5 expansions ...a_2 a_1 a_0 and ...b_2 b_1 b_0 satisfy the condition that if i > j then the pairs of base-5 digits (a_i,a_j) and (b_i,b_j) are either equal or consecutive in the path through {0, 1, 2, 3, 4}^2 shown at the diagram:
.
(0,4)--(1,4)--(2,4)--(3,4) (4,4)
| | |
| | |
(0,3) (1,3)--(2,3) (3,3) (4,3)
| | | | |
| | | | |
(0,2) (1,2) (2,2) (3,2) (4,2)
| | | | |
| | | | |
(0,1) (1,1) (2,1)--(3,1) (4,1)
| | |
| | |
(0,0) (1,0)--(2,0)--(3,0)--(4,0)
.
Actually, every positive integer is adjacent to exactly two nonnegative integers, and we can write down a permutation of nonnegative integers starting with 0 such that the two consecutive numbers in it are adjacent. That permutation is this sequence.
(End)
The first differences appear to be +- 5^k, for some k >= 0.
Fractal behavior: when n = 5^k - 1, k >= 2, a similar image is completed.
(End)
The first differences are +- 5^k, this is a Gray code in base 5. - Joerg Arndt, Feb 05 2022
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
48 (equals 143 in base 5) is adjacent to 47 = 142_5 and 73 = 243_5, hence 48 follows 73 and precedes 47.
|
|
|
MAPLE
|
|
|
|
PROG
|
(PARI) isAdj(a, b)={a=Vec(digits(min(a, b), 5), -#b=concat(0, digits(max(a, b), 5))); normlp(a-b, 1)<2 && !for(j=2, #b, for(i=1, j-1, if(a[i]==b[i], !a[i] || a[i]==4 || (a[i]==3 && min(a[j], b[j])) || (a[i]==1 && max(a[j], b[j])<4) || (a[i]==2 && !#setminus(Set([a[j], b[j]]), [1, 2, 3])) || a[j]==b[j], (!a[j] && min(a[i], b[i])) || (a[j]==4 && max(a[i], b[i])<4) || (a[j]==1 && Set([a[i], b[i]])==[2, 3]) || (a[j]==3 && Set([a[i], b[i]])==[1, 2]) || a[i]==b[i]) || return))}
u=[]; for(n=a=0, 100, print1(a", "); u=setunion(u, [a]); while(#u>1&&u[2]==u[1]+1, u=u[^1]); for(k=u[1]+1, oo, !setsearch(u, k)&&isAdj(a, k)&&(a=k)&&next(2))) \\ M. F. Hasler, Mar 13 2018
|
|
|
CROSSREFS
|
See A300855 for the inverse permutation, A300857 for the base-7 variant.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
