%I #108 Oct 28 2021 06:41:47
%S 0,2,3,1,6,7,5,10,11,8,14,15,4,18,19,13,22,23,16,26,27,12,30,31,21,34,
%T 35,24,38,39,17,42,43,29,46,47,32,50,51,9,54,55,37,58,59,40,62,63,28,
%U 66,67,45,70,71,48,74,75,33,78,79,53,82,83,56
%N To get {a(n)}, start with the nonnegative integers sequence f() and, for each y>=0, shift the f(y) to position f(2y) and reset indices.
%C To get {a(n)}, we use the working sequences f_x(y), where y is the index and x is both, the x-th working sequence and a control variable. x=0,1,2,3,... up to infinity.
%C f_x(y) = f_(x-1)(x) if y = 2x, f_(x-1)(y+1) if x <= y < 2x, and s_(x-1)(y) otherwise.
%C Start with the sequence of nonnegative integers
%C {f(y)} = 0,1,2,3,4,5,6,7,8,9,10,11,12,...
%C The first index is 0: For f(y=0), nothing is changed, since f(2*0=0), so we still have
%C {f_0(y)} = 0,1,2,3,4,5,6,7,8,9,10,11,12,...
%C For x=1: Shift f(1)=1 to f(2*1)=f(2), and all f(1<y<=2) to f(y-1): f(2)=2 to f(1), leaving
%C {f_1(y)} = 0,2,1,3,4,5,6,7,8,9,10,11,12,...
%C For x=2: Shift f(2)=1 to f(2*2)=f(4), and all f(1<y<=4) to f(y-1), leaving
%C {f_2(y)} = 0,2,3,4,1,5,6,7,8,9,10,11,12,...
%C Iterating the "cyclic shifting" indefinitely produces {a(n)}.
%C .
%C Visualization of the term index-position shift:
%C f_1: 0 1 2 3 4 5 6 7 8 9 10 11 12 ...
%C └+1─^
%C f_2: 0 2 1 3 4 5 6 7 8 9 10 11 12 ...
%C └──+2──^
%C f_3: 0 2 3 4 1 5 6 7 8 9 10 11 12 ...
%C └───+3────^
%C f_4: 0 2 3 1 5 6 4 7 8 9 10 11 12 ...
%C └─────+4─────^
%C f_5: 0 2 3 1 6 4 7 8 5 9 10 11 12 ...
%C └───────+5───────^
%C f_6: 0 2 3 1 6 7 8 5 9 10 4 11 12 ...
%C .
%C In the Formula section, formulas (2) and (3) (which build pairs of terms with a certain repeating spacing and difference, unlike formula (1)) give the terms with the single most f(x) to f(2x) shifts.
%C Some terms f(y) only get shifted to f(y-1), decreasing their final index n; other terms f(y) change position to f(2y) multiple times.
%C The value "t" in formulas (1), (2) and (3) gives the number of f(2y) shifts "s" of the resulting terms: For (1): s = t, for (2),(3): s = t-1.
%C E.g., the terms f(y) for the formulas (2) and (3) with t=1 (e.g., 2,3,6,7,10,11,...) only get shifted to f(y-1), e.g., f(y)=14=a(10), decreasing its index n from 14 to 10.
%C Other terms f(y) for formulas (2) and (3) with t>1 change position to f(2y) one or multiple times; e.g., for formula (2) t=3, k=1: f(y)=28=a(48) increases its position 2 times from its original y=28 up to n=48.
%C The number of times that the terms f(y) for formula (1) change position to f(2y) is t. E.g., t=5: f(y)=20=a(120) changes positions 5 times, up to n=120.
%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the nonnegative integers</a>
%F To obtain all terms there are three formulas.
%F For any t=1,2,3,... and k=0,1,2,3,... constellation:
%F (1) a((3^t - 3)/2) = (2^(t+2) + (-1)^(t-1) - 9)/6.
%F (2) a(k*3^t + (5*3^(t-1)-3)/2) = k*2^(t+1) + 2^t + (2^(t+2) + (-1)^(t-1) - 9)/6.
%F (3) a(k*3^t + (7*3^(t-1)-3)/2) = k*2^(t+1) + 2^t + (2^(t+3) - (-1)^(t-1) - 9)/6.
%e Formula (1) has no control value "k" and produces small values (terms) for large index numbers n, compared to formulas (2) and (3).
%e E.g.:
%e For formula (1) t=5: a(363)=41.
%e For formula (2) t=1, k=100: a(301)=402.
%e Formula (1) produces the "Generalized Jacobsthal numbers" as a subsequence "s": s(A029858(t))=A084639(t), and the differences between those terms are the "Jacobsthal numbers" A001045.
%o (PARI) shiftv(v, n) = {my(w = v); for (i=1,n-1, w[i] = v[i];); for (i=n, 2*n-1, w[i] = v[i+1];); w[2*n] = v[n]; w;}
%o lista(nn) = {my(v = [1..nn], va); for (n=1, nn\2, va = shiftv(v, n); v = va;); concat(0, vector(#v\2, k, v[k]));} \\ _Michel Marcus_, Sep 21 2021
%o (PARI) a(n) = n++; my(c=1,r); while([n,r]=divrem(n,3);r==1, c++); n<<(c+1) + (r<<1+1)<<c\3 - 1; \\ _Kevin Ryde_, Oct 09 2021
%Y Cf. A001045 (Jacobsthal numbers), A084639 (generalized Jacobsthal numbers), A029858, A254046, A253786.
%K nonn
%O 0,2
%A _Marc Morgenegg_, Sep 20 2021