A080637 - OEIS

%I #92 Nov 29 2024 23:51:05

%S 2,3,5,6,7,9,11,12,13,14,15,17,19,21,23,24,25,26,27,28,29,30,31,33,35,

%T 37,39,41,43,45,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,65,

%U 67,69,71,73,75,77,79,81,83,85,87,89,91,93,95,96,97,98,99,100,101,102

%N a(n) is the smallest positive integer which is consistent with the sequence being monotonically increasing and satisfying a(1)=2, a(a(n)) = 2n+1 for n > 1.

%C Sequence is the unique monotonic sequence satisfying a(a(n)) = 2n+1.

%C Except for the first term, numbers (greater than 2) whose binary representation starts with 11 or ends with 1. - _Yifan Xie_, May 26 2022

%H Yifan Xie, <a href="/A080637/b080637.txt">Table of n, a(n) for n = 1..10000</a>

%H Benoit Cloitre, N. J. A. Sloane and M. J. Vandermast, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL6/Cloitre/cloitre2.html">Numerical analogues of Aronson's sequence</a>, J. Integer Seqs., Vol. 6 (2003), #03.2.2.

%H Benoit Cloitre, N. J. A. Sloane and M. J. Vandermast, <a href="https://arxiv.org/abs/math/0305308">Numerical analogues of Aronson's sequence</a>, arXiv:math/0305308 [math.NT], 2003.

%H Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf">Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications</a>, Preprint, 2016.

%H Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="https://doi.org/10.1145/3127585">Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications</a>, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.

%H <a href="/index/Aa#aan">Index entries for sequences of the a(a(n)) = 2n family</a>

%F a(3*2^k - 1 + j) = 4*2^k - 1 + 3*j/2 + |j|/2 for k >= 0, -2^k <= j < 2^k.

%F a(2n+1) = 2*a(n) + 1, a(2n) = a(n) + a(n-1) + 1.

%F From _Yifan Xie_, May 02 2022: (Start)

%F For n in the range 2*2^i <= n < 3*2^i, for i >= 0:

%F   a(n) = n + 2^i.

%F   a(n) = 1 + a(n-1).

%F Otherwise, for n in the range 3*2^i <= n < 4*2^i, for i >= 0:

%F   a(n) = 2*(n - 2^i) + 1.

%F   a(n) = 2 + a(n-1). (End)

%e From _Yifan Xie_, May 02 2022: (Start)

%e a(8) = 12 because 2*2^2 <= 8 < 3*2^2, hence a(8) = 8 + 2^2 = 12;

%e a(13) = 19 because 3*2^2 <= 13 < 4*2^2, hence a(13) = 2*(13 - 2^2) + 1 = 19. (End)

%p t := []; for k from 0 to 6 do for j from -2^k to 2^k-1 do t := [op(t), 4*2^k - 1 + 3*j/2 + abs(j)/2]; od: od: t;

%t b[n_] := b[n] = If[n<4, n+1, If[OddQ[n], b[(n-1)/2+1]+b[(n-1)/2], 2b[n/2]]];

%t a[n_] := b[n+1]-1;

%t a /@ Range[70] (* _Jean-François Alcover_, Oct 31 2019 *)

%Y Except for first term, same as A079905. Cf. A079000.

%Y A007378, A079905, A080637, A080653 are all essentially the same sequence.

%Y Equals A007378(n+1)-1. First differences give A079882.

%Y Unique monotonic sequence of positive integers satisfying a(a(n)) = k*(n-1) + 3: this sequence (k=2), A003605 (k=3), A353651 (k=4), A353652 (k=5), A353653 (k=6).

%K nonn,easy

%O 1,1

%A _N. J. A. Sloane_ and _Benoit Cloitre_, Feb 28 2003