

A007378


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


11



3, 4, 6, 7, 8, 10, 12, 13, 14, 15, 16, 18, 20, 22, 24, 25, 26, 27, 28, 29, 30, 31, 32, 34, 36, 38, 40, 42, 44, 46, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 97, 98, 99, 100, 101, 102, 103
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

2,1


COMMENTS

This is the unique monotonic sequence {a(n)}, n>=2, satisfying a(a(n)) = 2n.
May also be defined by: a(n), n=2,3,4,..., is smallest positive integer greater than a(n1) 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
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
Numbers (greater than 2) whose binary representation starts with "11" or ends with "0".  Franklin T. AdamsWatters, Jan 17 2006


REFERENCES

J.P. Allouche, N. Rampersad and J. Shallit, On integer sequences whose first iterates are linear, Aequationes Math. 69 (2005), 114127
J.P. Allouche and J. Shallit, The ring of kregular sequences, II, Theoret. Computer Sci., 307 (2003), 329.
HsienKuei Hwang, S Janson, TH Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint, 2016; http://140.109.74.92/hk/wpcontent/files/2016/12/aathhrr1.pdf. Also Exact and Asymptotic Solutions of a DivideandConquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS

Vincenzo Librandi, Table of n, a(n) for n = 2..10000
J.P. Allouche and J. Shallit, The Ring of kregular Sequences, II
B. Cloitre, N. J. A. Sloane and M. J. Vandermast, Numerical analogues of Aronson's sequence, J. Integer Seqs., Vol. 6 (2003), #03.2.2.
B. Cloitre, N. J. A. Sloane and M. J. Vandermast, Numerical analogues of Aronson's sequence (math.NT/0305308)
J. Shallit, kregular Sequences
R. Stephan, Some divideandconquer sequences ...
R. Stephan, Table of generating functions
Index entries for sequences of the a(a(n)) = 2n family


FORMULA

a(2^i + j) = 3*2^(i1) + j, 0<=j<2^(i1); a(3*2^(i1) + j) = 2^(i+1) + 2*j, 0<=j<2^(i1).
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
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
G.f. x/(1x) + x/(1x)^2 * (2 + sum(k>=0, t^2(t1), t=x^2^k)).  Ralf Stephan, Sep 12 2003


MATHEMATICA

max = 70; f[x_] := x/(1x) + x/(1x)^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](* JeanFrançois Alcover, May 16 2012, from g.f. *)
a[2]=3; a[3]=4; a[n_?OddQ] := a[n] = a[(n1)/2+1] + a[(n1)/2]; a[n_?EvenQ] := a[n] = 2a[n/2]; Table[a[n], {n, 2, 71}] (* JeanFrançois Alcover, Jun 26 2012, after Vladeta Jovovic *)


CROSSREFS

Cf. A003605. Equals A080653 + 2.
This sequence, A079905, A080637 and A080653 are all essentially the same.
Cf. A088720.
Sequence in context: A022846 A083922 A039042 * A274829 A087758 A227019
Adjacent sequences: A007375 A007376 A007377 * A007379 A007380 A007381


KEYWORD

nonn,easy,nice


AUTHOR

Colin Mallows


EXTENSIONS

More terms from Matthew Vandermast and Vladeta Jovovic, Mar 01 2003


STATUS

approved



