cp's OEIS Frontend

A080637 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.

%I A080637 #105 Jun 05 2025 08:12:52
%S A080637 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 A080637 37,39,41,43,45,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,65,
%U A080637 67,69,71,73,75,77,79,81,83,85,87,89,91,93,95,96,97,98,99,100,101,102
%N A080637 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 A080637 Sequence is the unique monotonic sequence satisfying a(a(n)) = 2n+1.
%C A080637 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 A080637 Yifan Xie, <a href="/A080637/b080637.txt">Table of n, a(n) for n = 1..10000</a>
%H A080637 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 A080637 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 A080637 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 A080637 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 A080637 <a href="/index/Aa#aan">Index entries for sequences of the a(a(n)) = 2n family</a>
%F A080637 a(3*2^k - 1 + j) = 4*2^k - 1 + 3*j/2 + |j|/2 for k >= 0, -2^k <= j < 2^k.
%F A080637 a(2n+1) = 2*a(n) + 1, a(2n) = a(n) + a(n-1) + 1.
%F A080637 From _Yifan Xie_, May 02 2022: (Start)
%F A080637 For n in the range 2*2^i <= n < 3*2^i, for i >= 0:
%F A080637   a(n) = n + 2^i.
%F A080637   a(n) = 1 + a(n-1).
%F A080637 Otherwise, for n in the range 3*2^i <= n < 4*2^i, for i >= 0:
%F A080637   a(n) = 2*(n - 2^i) + 1.
%F A080637   a(n) = 2 + a(n-1). (End)
%e A080637 From _Yifan Xie_, May 02 2022: (Start)
%e A080637 a(8) = 12 because 2*2^2 <= 8 < 3*2^2, hence a(8) = 8 + 2^2 = 12;
%e A080637 a(13) = 19 because 3*2^2 <= 13 < 4*2^2, hence a(13) = 2*(13 - 2^2) + 1 = 19. (End)
%p A080637 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 A080637 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 A080637 a[n_] := b[n+1]-1;
%t A080637 a /@ Range[70] (* _Jean-François Alcover_, Oct 31 2019 *)
%Y A080637 Except for first term, same as A079905. Cf. A079000.
%Y A080637 A007378, A079905, A080637, A080653 are all essentially the same sequence.
%Y A080637 Equals A007378(n+1)-1. First differences give A079882.
%Y A080637 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 A080637 nonn,easy
%O A080637 1,1
%A A080637 _N. J. A. Sloane_ and _Benoit Cloitre_, Feb 28 2003