A220952 A twisted enumeration of the nonnegative integers.

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

Offset: 0

Author

Don Knuth, Feb 20 2013

Keywords

• nonn
• look
• base
• nice

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]

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

Examples

			48 (equals 143 in base 5) is adjacent to 47 = 142_5 and 73 = 243_5, hence 48 follows 73 and precedes 47.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..15624
• Donald Knuth (Proposer), A twisted enumeration of the positive integers; Problem 11733, Amer. Math. Monthly, 120 (9) (2013), 76.
• R. J. Mathar, Maple program for A220952.
• Richard Stong (Solver), A twisted enumeration of the positive integers; Solution to Problem 11733, Amer. Math. Monthly, 123 (1) (2016), 98-100. See here for another link.
• Richard Stong (Solver), A twisted enumeration of the positive integers; Solution to Problem 11733, Amer. Math. Monthly, 123 (1) (2016), 98-100. [Annotated scanned copy]
• Index to sequences related to permutations of the nonnegative integers

Crossrefs

See A300855 for the inverse permutation, A300857 for the base-7 variant.

Programs

Maple

# See the link, R. J. Mathar, Aug 25 2017

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

Extensions

Extended beyond a(25) by R. J. Mathar, Aug 25 2017