cp's OEIS Frontend

A007378 a(n), for n >= 2, is smallest positive integer which is consistent with sequence being monotonically increasing and satisfying a(a(n)) = 2n.

%I A007378 M2317 #73 Jun 05 2025 08:10:00
%S A007378 3,4,6,7,8,10,12,13,14,15,16,18,20,22,24,25,26,27,28,29,30,31,32,34,
%T A007378 36,38,40,42,44,46,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,
%U A007378 66,68,70,72,74,76,78,80,82,84,86,88,90,92,94,96,97,98,99,100,101,102,103
%N A007378 a(n), for n >= 2, is smallest positive integer which is consistent with sequence being monotonically increasing and satisfying a(a(n)) = 2n.
%C A007378 This is the unique monotonic sequence {a(n)}, n>=2, satisfying a(a(n)) = 2n.
%C A007378 May also be defined by: a(n), n=2,3,4,..., is smallest positive integer greater than a(n-1) which is consistent with the condition "n is a member of the sequence if and only if a(n) is an even number >= 4". - _N. J. A. Sloane_, Feb 23 2003
%C A007378 A monotone sequence satisfying a^(k+1)(n) = mn is unique if m=2, k >= 0 or if (k,m) = (1,3). See A088720. - _Colin Mallows_, Oct 16 2003
%C A007378 Numbers (greater than 2) whose binary representation starts with "11" or ends with "0". - _Franklin T. Adams-Watters_, Jan 17 2006
%C A007378 Lower density 2/3, upper density 3/4. - _Charles R Greathouse IV_, Dec 14 2022
%D A007378 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A007378 Vincenzo Librandi, <a href="/A007378/b007378.txt">Table of n, a(n) for n = 2..10000</a>
%H A007378 J.-P. Allouche, N. Rampersad and J. Shallit, <a href="https://doi.org/10.1007/s00010-004-2750-x">On integer sequences whose first iterates are linear</a>, Aequationes Math. 69 (2005), 114-127.
%H A007378 J.-P. Allouche and J. Shallit, <a href="http://www.math.jussieu.fr/~allouche/kreg2.ps">The Ring of k-regular Sequences, II</a>
%H A007378 J.-P. Allouche and J. Shallit, <a href="https://doi.org/10.1016/S0304-3975(03)00090-2">The ring of k-regular sequences, II</a>, Theoret. Computer Sci., 307 (2003), 3-29.
%H A007378 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 A007378 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 A007378 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 A007378 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.
%H A007378 Jeffrey Shallit, <a href="http://www.cs.uwaterloo.ca/~shallit/Talks/kreg7.ps">k-regular Sequences</a>
%H A007378 Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>
%H A007378 Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>
%H A007378 <a href="/index/Aa#aan">Index entries for sequences of the a(a(n)) = 2n family</a>
%F A007378 a(2^i + j) = 3*2^(i-1) + j, 0<=j<2^(i-1); a(3*2^(i-1) + j) = 2^(i+1) + 2*j, 0<=j<2^(i-1).
%F A007378 a(3*2^k + j) = 4*2^k + 3j/2 + |j|/2, k>=0, -2^k <= j < 2^k. - _N. J. A. Sloane_, Feb 23 2003
%F A007378 a(2*n+1) = a(n+1)+a(n), a(2*n) = 2*a(n). a(n) = n+A060973(n). - _Vladeta Jovovic_, Mar 01 2003
%F A007378 G.f.: -x/(1-x) + x/(1-x)^2 * (2 + sum(k>=0, t^2(t-1), t=x^2^k)). - _Ralf Stephan_, Sep 12 2003
%p A007378 a := proc(n) option remember; if n < 4 then n+1 else a(iquo(n,2)) + a(iquo(n+1,2)) fi end:
%p A007378 seq(a(n), n = 2..70); # _Peter Bala_, Aug 03 2022
%t A007378 max = 70; f[x_] := -x/(1-x) + x/(1-x)^2*(2 + Sum[ x^(2^k + 2^(k+1)) - x^2^(k+1) , {k, 0, Ceiling[Log[2, max]]}]); Drop[ CoefficientList[ Series[f[x], {x, 0, max + 1}], x], 2](* _Jean-François Alcover_, May 16 2012, from g.f. *)
%t A007378 a[2]=3; a[3]=4; a[n_?OddQ] := a[n] = a[(n-1)/2+1] + a[(n-1)/2]; a[n_?EvenQ] := a[n] = 2a[n/2]; Table[a[n], {n, 2, 71}] (* _Jean-François Alcover_, Jun 26 2012, after _Vladeta Jovovic_ *)
%o A007378 (Python)
%o A007378 from functools import cache
%o A007378 @cache
%o A007378 def a(n): return n+1 if n < 4 else a(n//2) + a((n+1)//2)
%o A007378 print([a(n) for n in range(2, 72)]) # _Michael S. Branicky_, Aug 04 2022
%o A007378 (PARI) a(n) = my(s=logint(n,2)-1); if(bittest(n,s), n<<1 - 2<<s, n + 1<<s); \\ _Kevin Ryde_, Aug 08 2022
%Y A007378 Cf. A003605. Equals A080653 + 2.
%Y A007378 This sequence, A079905, A080637 and A080653 are all essentially the same.
%Y A007378 Cf. A088720, A042965.
%K A007378 nonn,easy,nice
%O A007378 2,1
%A A007378 _Colin Mallows_
%E A007378 More terms from _Matthew Vandermast_ and _Vladeta Jovovic_, Mar 01 2003