cp's OEIS Frontend

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]

From Andrey Zabolotskiy, Feb 21 2018: (Start)

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)

From Daniel Forgues, Feb 22 2018: (Start)

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

Base-7 variant of Knuth's A220952, i.e., two numbers a, b are adjacent iff for all i > j, the pairs (a_i,a_j) and (b_i,b_j) (where indices denote base-7 digits: a = Sum_{k>=0} a_k*7^k), are equal or neighbors in the following graph:

.

(0,6)--(1,6)--(2,6)--(3,6)--(4,6)--(5,6) (6,6)

| | |

| | |

(0,5) (1,5)--(2,5)--(3,5)--(4,5) (5,5) (6,5)

| | | | |

| | | | |

(0,4) (1,4) (2,4)--(3,4) (4,4) (5,4) (6,4)

| | | | | | |

| | | | | | |

(0,3) (1,3) (2,3) (3,3) (4,3) (5,3) (6,3)

| | | | | | |

| | | | | | |

(0,2) (1,2) (2,2) (3,2)--(4,2) (5,2) (6,2)

| | | | |

| | | | |

(0,1) (1,1) (2,1)--(3,1)--(4,1)--(5,1) (6,1)

| | |

| | |

(0,0) (1,0)--(2,0)--(3,0)--(4,0)--(5,0)--(6,0)

.

It turns out that for any positive integer there are exactly two other adjacent nonnegative integers, and this sequence in which (a(n),a(n+1)) are pairs of adjacent integers, defines a permutation of the nonnegative integers.

The analog graph for base-3 would yield more than two other adjacent numbers for some n, e.g., n = 5 would be adjacent to 3, 4, 6, 7, and 8. For even bases there is not an exact analog of this graph.