A079905 -id:A079905 - cp's OEIS frontend

A079000 a(n) is taken to be the 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 odd".

1, 4, 6, 7, 8, 9, 11, 13, 15, 16, 17, 18, 19, 20, 21, 23, 25, 27, 29, 31, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 95, 97

Offset: 1

Matthew Vandermast, Feb 01 2003

a(a(n)) = 2n + 3 for n>1.

			a(2) cannot be 2 because 2 is even; it cannot be 3 because that would require 2 to be a member of the sequence. Hence a(2)=4 and the next odd member of the sequence is the fourth member.

Hsien-Kuei 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/wp-content/files/2016/12/aat-hhrr-1.pdf. Also Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585
N. J. A. Sloane, Seven Staggering Sequences, in Homage to a Pied Puzzler, E. Pegg Jr., A. H. Schoen and T. Rodgers (editors), A. K. Peters, Wellesley, MA, 2009, pp. 93-110.

N. J. A. Sloane, Table of n, a(n) for n = 1..10000
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, arXiv:math/0305308 [math.NT], 2003.
N. J. A. Sloane, Seven Staggering Sequences.
Index entries for sequences of the a(a(n)) = 2n family

Cf. A079250-A079259, A079313, A079325, A064437, A003605, A079352, A079358.
Cf. also A080596, A080731, A080752, A121053, A080032.
Partial sums give A080566. Differences give A079948.

Digits := 50; A079000 := proc(n) local k,j; if n<=2 then n^2; else k := floor(evalf(log( (n+3)/6 )/log(2)) ); j := n-(9*2^k-3); 12*2^k-3+3*j/2 +abs(j)/2; fi; end;
A002264 := n->floor(n/3): A079944 := n->floor(log[2](4*(n+2)/3))-floor(log[2](n+2)): A000523 := n->floor(log[2](n)): f := n->A079944(A002264(n-4)): g := n->A000523(A002264(n+2)/2): A079000 := proc(n) if n>3 then RETURN(simplify(3*n+3-3*2^g(n)+(-1)^f(n)*(9*2^g(n)-n-3))/2) else if n>0 then RETURN([1,4,6][n]) else RETURN(0) fi fi: end;

a[1] = 1; a[n_] := (k = Floor[Log[2, (n+3)/6]]; j = n-(9*2^k - 3); 12*2^k-3 + 3*j/2 + Abs[j]/2); Table[a[n], {n, 1, 71}] (* Jean-François Alcover, May 21 2012, after Maple *)

a(1) = 1, a(2) = 4, then a(9*2^k-3+j) = 12*2^k-3+3*j/2+|j|/2 for k>=0, -3*2^k <= j <= 3*2^k. Also a(3n) = 3*b(n/3), a(3n+1) = 2*b(n)+b(n+1), a(3n+2) = b(n)+2*b(n+1) for n>=2, where b = A079905. - N. J. A. Sloane and Benoit Cloitre, Feb 20 2003
a(n+1) - 2*a(n) + a(n-1) = 1 for n = 9*2^k - 3, k>=0, = -1 for n = 2 and 3*2^k-3, k>=1 and = 0 otherwise.
a(n) = (3*n + 3 - 3*2^g(n) + (-1)^f(n)*(9*2^g(n) - n - 3))/2 for n>3, f(n) = A079944(A002264(n-4)) and g(n) = A000523(A002264(n+2)/2). - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Feb 23 2003
Also a(n) = n + 3*2^A000523(A002264(n+2)/2)*(1 - 3*A080584(n-4)) + A080584(n-4)*(n+3) for n>3, where A080584(n)=A079944(A002264(n)). - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Feb 24 2003

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

Original entry on oeis.org

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

Colin Mallows

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

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

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

Cf. A003605. Equals A080653 + 2.
This sequence, A079905, A080637 and A080653 are all essentially the same.
Cf. A088720, A042965.

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

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

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

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

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

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

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.

Original entry on oeis.org

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, 37, 39, 41, 43, 45, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 96, 97, 98, 99, 100, 101, 102

Offset: 1

N. J. A. Sloane and Benoit Cloitre, Feb 28 2003

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

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

			From _Yifan Xie_, May 02 2022: (Start)
a(8) = 12 because 2*2^2 <= 8 < 3*2^2, hence a(8) = 8 + 2^2 = 12;
a(13) = 19 because 3*2^2 <= 13 < 4*2^2, hence a(13) = 2*(13 - 2^2) + 1 = 19. (End)

Yifan Xie, Table of n, a(n) for n = 1..10000
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; DOI: 10.1145/3127585.
Index entries for sequences of the a(a(n)) = 2n family

Except for first term, same as A079905. Cf. A079000.
A007378, A079905, A080637, A080653 are all essentially the same sequence.
Equals A007378(n+1)-1. First differences give A079882.
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).

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;

b[n_] := b[n] = If[n<4, n+1, If[OddQ[n], b[(n-1)/2+1]+b[(n-1)/2], 2b[n/2]]];
a[n_] := b[n+1]-1;
a /@ Range[70] (* Jean-François Alcover, Oct 31 2019 *)

a(3*2^k - 1 + j) = 4*2^k - 1 + 3*j/2 + |j|/2 for k >= 0, -2^k <= j < 2^k.
a(2n+1) = 2*a(n) + 1, a(2n) = a(n) + a(n-1) + 1.
From Yifan Xie, May 02 2022: (Start)
For n in the range 2*2^i <= n < 3*2^i, for i >= 0:
  a(n) = n + 2^i.
  a(n) = 1 + a(n-1).
Otherwise, for n in the range 3*2^i <= n < 4*2^i, for i >= 0:
  a(n) = 2*(n - 2^i) + 1.
  a(n) = 2 + a(n-1). (End)

A080653 a(1) = 2; for n>1, a(n) is taken to be the smallest integer greater than a(n-1) such that the condition "a(a(n)) is always even" is satisfied.

Original entry on oeis.org

2, 4, 5, 6, 8, 10, 11, 12, 13, 14, 16, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 32, 34, 36, 38, 40, 42, 44, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 95, 96, 97

Offset: 1

Matthew Vandermast, Mar 01 2003

Also defined by: a(n) = smallest positive number > a(n-1) such that the condition "n is in sequence if and only if a(n) is odd" is false (cf. A079000); that is, the condition "either n is not in the sequence and a(n) is odd or n is in the sequence and a(n) is even" is satisfied.
If prefixed with a(0) = 0, can be defined by: a(n) = smallest nonnegative number > a(n-1) such that the condition "n is in sequence only if a(n) is even" is satisfied.
Lower density 2/3, upper density 3/4. - Charles R Greathouse IV, Dec 14 2022

Hsien-Kuei 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/wp-content/files/2016/12/aat-hhrr-1.pdf. Also Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585

Yifan Xie, Table of n, a(n) for n = 1..10000
Benoit Cloitre, N. J. A. Sloane and Matthew J. Vandermast, Numerical analogues of Aronson's sequence, J. Integer Seqs., Vol. 6 (2003), #03.2.2.
Benoit Cloitre, N. J. A. Sloane and Matthew J. Vandermast, Numerical analogues of Aronson's sequence (math.NT/0305308)

Equals A007378 - 2.
A007378, A079905, A080637, A080653 are all essentially the same sequence.
Cf. A169956, A169957.

(* b = A007378 *) b[n_] := b[n] = Which[n == 2, 3, n == 3, 4, EvenQ[n], 2 b[n/2], True, b[(n-1)/2+1]+b[(n-1)/2]]; a[1] = 2; a[n_] := b[n+2]-2; Table[a[n], {n, 1, 65}] (* Jean-François Alcover, Oct 05 2016 *)

a(a(n)) = 2n + 2. - Yifan Xie, Jul 14 2022

a(n+1) - a(n) is in {1, 2}. In particular, n < a(n) <= 2n. More is true: lim inf a(n)/n = 4/3 and lim sup a(n)/n = 3/2. - Charles R Greathouse IV, Dec 14 2022

A169956 Lexicographically earliest sequence with positive integers satisfying a(a(n)) = 2*n+2.

Original entry on oeis.org

2, 4, 5, 6, 8, 10, 9, 12, 16, 14, 13, 18, 24, 22, 17, 20, 32, 26, 21, 34, 40, 30, 25, 28, 48, 38, 29, 50, 56, 46, 33, 36, 64, 42, 37, 66, 72, 54, 41, 44, 80, 70, 45, 82, 88, 62, 49, 52, 96, 58, 53, 98, 104, 78, 57, 60, 112, 102, 61, 114, 120, 94, 65, 68, 128, 74

Offset: 1

Eric Angelini, Aug 02 2010

Previous name was: Similar to A080653, but without the "monotonically increasing sequence" condition.

Sequence contains all the even numbers and odd numbers k such that k mod 4 = 1. - Yifan Xie, Jul 05 2022

			For n=3, a(3) must satisfy a(a(3)) = 2*3+2 = 8. If a(3) = 0, we get 8 = a(a(3)) = a(0) = 1, so a(3) > 0. Using the same method twice we get a(3) > 2. If a(3) = 3, hence 3 = a(3) = a(a(3)) = 8, so a(3) > 3. If a(3) = 4, using a(2) = 4 we get 8 = a(a(3)) = a(4) = 2*2+2 = 6, so a(3) > 4. If a(3) = 5, there are no conflicts using the definition, so a(3) = 5. - _Yifan Xie_, Jul 05 2022

Yifan Xie, Table of n, a(n) for n = 1..10000

Cf. A080653, A079905, A169957.

From Yifan Xie, Jul 05 2022: (Start)
a(A169957(n)-1) = 2*n for n > 1.
a(4*n-1) = 4*n+1 for n >= 1.
a(4*n+1) = 8*n for n >= 1. (End)

New name and more terms from Yifan Xie, Jul 05 2022

a(23) corrected by Yifan Xie, Jul 05 2022

A169957 a(1) = 1, then a(n) is the smallest number such that a(a(n)) = 2n+1.

Original entry on oeis.org

1, 3, 5, 6, 7, 9, 11, 10, 13, 17, 15, 14, 19, 25, 23, 18, 21, 33, 27, 22, 35, 41, 31, 26, 29, 49, 39, 30, 51, 57, 47, 34, 37, 65, 43, 38, 67, 73, 55, 42, 45, 81, 71, 46, 83, 89, 63, 50, 53, 97, 59, 54, 99, 105, 79, 58, 61, 113, 103, 62, 115

Offset: 1

Eric Angelini, Aug 02 2010

Original name was "Similar to A079905, but without the 'monotonically increasing sequence' condition."

Yifan Xie, Table of n, a(n) for n = 1..10000 (first 499 terms from Charlie Neder)

Cf. A080653, A079905, A169956.

a(1) = 1, a(2) = 3, a(4k) = 4k + 2, all other terms follow from the criterion defining the sequence. - Charlie Neder, Dec 21 2018

a(25)-a(61) from Charlie Neder, Dec 21 2018

Name changed by Charlie Neder, Dec 22 2018

cp's OEIS Frontend

A079000 a(n) is taken to be the 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 odd".

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A080653 a(1) = 2; for n>1, a(n) is taken to be the smallest integer greater than a(n-1) such that the condition "a(a(n)) is always even" is satisfied.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

A169956 Lexicographically earliest sequence with positive integers satisfying a(a(n)) = 2*n+2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A169957 a(1) = 1, then a(n) is the smallest number such that a(a(n)) = 2n+1.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions