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

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

Offset: 2

Author

Colin Mallows

Keywords

• nonn
• easy
• nice

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(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

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. Adams-Watters, Jan 17 2006

Lower density 2/3, upper density 3/4. - Charles R Greathouse IV, Dec 14 2022

References

• 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, N. Rampersad and J. Shallit, On integer sequences whose first iterates are linear, Aequationes Math. 69 (2005), 114-127.
• J.-P. Allouche and J. Shallit, The Ring of k-regular Sequences, II
• J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
• Benoit Cloitre, N. J. A. Sloane and M. J. Vandermast, Numerical analogues of Aronson's sequence, J. Integer Seqs., Vol. 6 (2003), #03.2.2.
• Benoit Cloitre, N. J. A. Sloane and M. J. Vandermast, Numerical analogues of Aronson's sequence, arXiv:math/0305308 [math.NT], 2003.
• Hsien-Kuei Hwang, S. Janson, and T.-H. 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.
• Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47.
• Jeffrey Shallit, k-regular Sequences
• Ralf Stephan, Some divide-and-conquer sequences ...
• Ralf Stephan, Table of generating functions
• Index entries for sequences of the a(a(n)) = 2n family

Crossrefs

Cf. A003605. Equals A080653 + 2.

This sequence, A079905, A080637 and A080653 are all essentially the same.

Cf. A088720, A042965.

Programs

Maple

a := proc(n) option remember; if n < 4 then n+1 else a(iquo(n,2)) + a(iquo(n+1,2)) fi end:
seq(a(n), n = 2..70); # Peter Bala, Aug 03 2022

Mathematica

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. *)
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 *)

PARI

a(n) = my(s=logint(n,2)-1); if(bittest(n,s), n<<1 - 2<Kevin Ryde, Aug 08 2022

Python

from functools import cache
@cache
def a(n): return n+1 if n < 4 else a(n//2) + a((n+1)//2)
print([a(n) for n in range(2, 72)]) # Michael S. Branicky, Aug 04 2022

Formula

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

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/(1-x) + x/(1-x)^2 * (2 + sum(k>=0, t^2(t-1), t=x^2^k)). - Ralf Stephan, Sep 12 2003

Extensions

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