%I #93 Feb 05 2022 11:21:52
%S 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,
%T 74,99,98,97,96,71,72,73,48,47,46,45,70,95,90,85,80,55,60,65,40,35,30,
%U 31,32,33,38,37,36,41,42,43,68,67,66,61,62,63,58,57,56,81,82,83,88
%N A twisted enumeration of the nonnegative integers.
%C 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."
%C 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
%C [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]
%C From _Andrey Zabolotskiy_, Feb 21 2018: (Start)
%C The sequence is defined by Knuth as follows.
%C 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:
%C .
%C (0,4)--(1,4)--(2,4)--(3,4) (4,4)
%C | | |
%C | | |
%C (0,3) (1,3)--(2,3) (3,3) (4,3)
%C | | | | |
%C | | | | |
%C (0,2) (1,2) (2,2) (3,2) (4,2)
%C | | | | |
%C | | | | |
%C (0,1) (1,1) (2,1)--(3,1) (4,1)
%C | | |
%C | | |
%C (0,0) (1,0)--(2,0)--(3,0)--(4,0)
%C .
%C 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.
%C (End)
%C From _Daniel Forgues_, Feb 22 2018: (Start)
%C The first differences appear to be +- 5^k, for some k >= 0.
%C Fractal behavior: when n = 5^k - 1, k >= 2, a similar image is completed.
%C (End)
%C The first differences are +- 5^k, this is a Gray code in base 5. - _Joerg Arndt_, Feb 05 2022
%H Alois P. Heinz, <a href="/A220952/b220952.txt">Table of n, a(n) for n = 0..15624</a>
%H Donald Knuth (Proposer), <a href="http://dx.doi.org/10.4169/amer.math.monthly.120.09.854">A twisted enumeration of the positive integers; Problem 11733</a>, Amer. Math. Monthly, 120 (9) (2013), 76.
%H R. J. Mathar, <a href="/A220952/a220952.txt">Maple program for A220952</a>.
%H Richard Stong (Solver), <a href="http://dx.doi.org/10.4169/amer.math.monthly.123.1.97">A twisted enumeration of the positive integers; Solution to Problem 11733</a>, Amer. Math. Monthly, 123 (1) (2016), 98-100. See <a href="https://lupucezar.files.wordpress.com/2011/02/amer-math-monthly-123-1-97.pdf">here</a> for another link.
%H Richard Stong (Solver), <a href="/A220952/a220952.pdf">A twisted enumeration of the positive integers; Solution to Problem 11733</a>, Amer. Math. Monthly, 123 (1) (2016), 98-100. [Annotated scanned copy]
%H <a href="/index/Per#IntegerPermutation">Index to sequences related to permutations of the nonnegative integers</a>
%e 48 (equals 143 in base 5) is adjacent to 47 = 142_5 and 73 = 243_5, hence 48 follows 73 and precedes 47.
%p # See the link, _R. J. Mathar_, Aug 25 2017
%o (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))}
%o 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
%Y See A300855 for the inverse permutation, A300857 for the base-7 variant.
%K nonn,look,base,nice
%O 0,3
%A _Don Knuth_, Feb 20 2013
%E Extended beyond a(25) by _R. J. Mathar_, Aug 25 2017