A006165 -id:A006165 - cp's OEIS frontend

A357564 a(n) = n - 2*b(b(n)) for n >= 2, where b(n) = A006165(n).

0, 1, 2, 1, 2, 3, 4, 3, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 15, 14, 13, 12, 11, 10, 9, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 17, 18, 19, 20, 21, 22, 23

Offset: 2

Peter Bala, Oct 15 2022

a(n+1) - a(n) is equal to 1 or -1.
The following hold for k >= 0:
Local valley: at n = 5*(2^k) the sequence has a local minimum value of 2^k.
Ascent: on the interval [5*(2^k), 8*(2^k)] of length 3*(2^k) the line graph of the sequence has slope 1.
Local peak: at n = 8*(2^k) the sequence has a local maximum value of 4*(2^k).
Descent: on the interval [8*(2^k), 10*(2^k)] of length 2*(2^k) the line graph of the sequence has slope -1.
Local valley: at n = 10*(2^k) = 5*(2^(k+1)) the sequence has a local minimum value of 2^(k+1).

Peter Bala, Notes on A357564

Cf. A006165, A357562.

# b(n) = A006165(n)
b := proc(n) option remember; if n = 1 then 1 else n - b(n - b(b(n-1))) end if; end proc:
seq( n - 2*b(b(n)), n = 2..100);

a(2) = 0, a(3) = 1 and a(4) = 2. For k >= 0 there holds
a(5*2^k + j) = 2^k + j for 0 <= j <= 3*2^k and
a(8*2^k + j) = 4*2^k - j for 0 <= j <= 2*2^k.

A042965 Nonnegative integers not congruent to 2 mod 4.

Original entry on oeis.org

0, 1, 3, 4, 5, 7, 8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 21, 23, 24, 25, 27, 28, 29, 31, 32, 33, 35, 36, 37, 39, 40, 41, 43, 44, 45, 47, 48, 49, 51, 52, 53, 55, 56, 57, 59, 60, 61, 63, 64, 65, 67, 68, 69, 71, 72, 73, 75, 76, 77, 79, 80, 81, 83, 84, 85, 87, 88, 89, 91, 92

Offset: 1

N. J. A. Sloane

Consider primitive Pythagorean triangles (A^2 + B^2 = C^2, (A, B) = 1, A <= B); sequence (starting at 3) gives values of AUB, sorted and duplicates removed. Values of AUBUC give same sequence. - David W. Wilson
These are the nonnegative integers that can be written as a difference of two squares, i.e., n = x^2 - y^2 for integers x,y. - Sharon Sela (sharonsela(AT)hotmail.com), Jan 25 2002. Equivalently, nonnegative numbers represented by the quadratic form x^2-y^2 of discriminant 4. The primes in this sequence are all the odd primes. - N. J. A. Sloane, May 30 2014
Numbers n such that Kronecker(4,n) == mu(gcd(4,n)). - Jon Perry, Sep 17 2002
Count, sieving out numbers of the form 2*(2*n+1) (A016825, "nombres pair-impairs"). A generalized Chebyshev transform of the Jacobsthal numbers: apply the transform g(x) -> (1/(1+x^2)) g(x/(1+x^2)) to the g.f. of A001045(n+2). Partial sums of 1,2,1,1,2,1,.... - Paul Barry, Apr 26 2005
For n>1, equals union of A020883 and A020884. - Lekraj Beedassy, Sep 28 2004
The sequence 1,1,3,4,5,... is the image of A001045(n+1) under the mapping g(x) -> g(x/(1+x^2)). - Paul Barry, Jan 16 2005
With offset 0 starting (1, 3, 4,...) = INVERT transform of A009531 starting (1, 2, -1, -4, 1, 6,...) with offset 0.
Apparently these are the regular numbers modulo 4 [Haukkanan & Toth]. - R. J. Mathar, Oct 07 2011
Numbers of the form x*y in nonnegative integers x,y with x+y even. - Michael Somos, May 18 2013
Convolution of A106510 with A000027. - L. Edson Jeffery, Jan 24 2015
Numbers that are the sum of zero or more consecutive odd positive numbers. - Gionata Neri, Sep 01 2015
Numbers that are congruent to {0, 1, 3} mod 4. - Wesley Ivan Hurt, Jun 10 2016
Nonnegative integers of the form (2+(3*m-2)/4^j)/3, j,m >= 0. - L. Edson Jeffery, Jan 02 2017
This is { x^2 - y^2; x >= y >= 0 }; with the restriction x > y one gets the same set without zero; with the restriction x > 0 (i.e., differences of two nonzero squares) one gets the set without 1. An odd number 2n-1 = n^2 - (n-1)^2, a number 4n = (n+1)^2 - (n-1)^2. - M. F. Hasler, May 08 2018

			G.f. = x^2 + 3*x^3 + 4*x^4 + 5*x^5 + 7*x^6 + 8*x^7 + 9*x^8 + 11*x^9 + 12*x^10 + ...

R. K. Guy, Unsolved Problems in Number Theory, Springer, 1st edition, 1981. See section D9.
J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, p. 83.

Ray Chandler, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
Pentti Haukkanen and László Tóth, An analogue of Ramanujan's sum with respect to regular integers (mod r), Ramanujan J., Vol. 27, No. 1 (2012), pp. 71-88.
Ron Knott, Pythagorean Triples and Online Calculators.
N. J. A. Sloane et al., Binary Quadratic Forms and OEIS (Index to related sequences, programs, references).
Index entries for linear recurrences with constant coefficients, signature (1,0,1,-1).

Cf. A001045, A006165, A009531, A020883, A020884, A047209, A047222, A214546, A143978, A042968.
Essentially the complement of A016825.
See A267958 for these numbers multiplied by 4.

a042965 =  (`div` 3) . (subtract 3) . (* 4)
a042965_list = 0 : 1 : 3 : map (+ 4) a042965_list
-- Reinhard Zumkeller, Nov 09 2012

[n: n in [0..100] | not n mod 4 in [2]]; // Vincenzo Librandi, Sep 03 2015

a_list := proc(len) local rec; rec := proc(n) option remember;
ifelse(n <= 4, [0, 1, 3, 4][n], rec(n-1) + rec(n-3) - rec(n-4)) end:
seq(rec(n), n=1..len) end: a_list(76); # Peter Luschny, Aug 06 2022

nn=100; Complement[Range[0,nn], Range[2,nn,4]] (* Harvey P. Dale, May 21 2011 *)
f[n_]:=Floor[(4*n-3)/3]; Array[f,70] (* Robert G. Wilson v, Jun 26 2012 *)
LinearRecurrence[{1, 0, 1, -1}, {0, 1, 3, 4}, 70] (* L. Edson Jeffery, Jan 21 2015 *)
Select[Range[0, 100], ! MemberQ[{2}, Mod[#, 4]] &] (* Vincenzo Librandi, Sep 03 2015 *)

a(n)=(4*n-3)\3 \\ Charles R Greathouse IV, Jul 25 2011

def A042965(n): return (n<<2)//3-1 # Chai Wah Wu, Feb 10 2025

Recurrence: a(n) = a(n-1) + a(n-3) - a(n-4) for n>4.
a(n) = n - 1 + (3n-3-sqrt(3)*(1-2*cos(2*Pi*(n-1)/3))*sin(2*Pi*(n-1)/3))/9. Partial sums of the period-3 sequence 0, 1, 1, 2, 1, 1, 2, 1, 1, 2, ... (A101825). - Ralf Stephan, May 19 2013
G.f.: A(x) = x^2*(1+x)^2/((1-x)^2*(1+x+x^2)); a(n)=Sum{k=0..floor(n/2)}, binomial(n-k-1, k)*A001045(n-2*k), n>0. - Paul Barry, Jan 16 2005, R. J. Mathar, Dec 09 2009
a(n) = floor((4*n-3)/3). - Gary Detlefs, May 14 2011
A214546(a(n)) != 0. - Reinhard Zumkeller, Jul 20 2012
From Michael Somos, May 18 2013: (Start)
Euler transform of length 3 sequence [3, -2, 1].
a(2-n) = -a(n). (End)
From Wesley Ivan Hurt, Jun 10 2016: (Start)
a(n) = (12*n-12+3*cos(2*n*Pi/3)+sqrt(3)*sin(2*n*Pi/3))/9.
a(3k) = 4k-1, a(3k-1) = 4k-3, a(3k-2) = 4k-4. (End)
a(n) = round((4*n-4)/3). - Mats Granvik, Sep 24 2016
The g.f. A(x) satisfies (A(x)/x)^2 + A(x)/x = x*B(x)^2, where B(x) is the o.g.f. of A042968. - Peter Bala, Apr 12 2017
Sum_{n>=2} (-1)^n/a(n) = log(sqrt(2)+2)/sqrt(2) - (sqrt(2)-1)*log(2)/4. - Amiram Eldar, Dec 05 2021
From Peter Bala, Aug 03 2022: (Start)
a(n) = a(floor(n/2)) + a(1 + ceiling(n/2)) for n >= 2, with a(2) = 1 and a(3) = 3.
a(2*n) = a(n) + a(n+1); a(2*n+1) = a(n) + a(n+2). Cf. A047222 and A006165. (End)
E.g.f.: (9 + 12*exp(x)*(x - 1) + exp(-x/2)*(3*cos(sqrt(3)*x/2) + sqrt(3)*sin(sqrt(3)*x/2)))/9. - Stefano Spezia, Apr 05 2023

Edited by N. J. A. Sloane at the suggestion of Andrew S. Plewe, Peter Pein and Ralf Stephan, Jun 17 2007

Typos fixed in Gary Detlefs's formula and in PARI program by Reinhard Zumkeller, Nov 09 2012

A053646 Distance to nearest power of 2.

Original entry on oeis.org

0, 0, 1, 0, 1, 2, 1, 0, 1, 2, 3, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25

Offset: 1

Henry Bottomley, Mar 22 2000

Sum_{j=1..2^(k+1)} a(j) = A002450(k) = (4^k - 1)/3. - Klaus Brockhaus, Mar 17 2003

			a(10)=2 since 8 is closest power of 2 to 10 and |8-10| = 2.

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Klaus Brockhaus, Illustration for A053646, A081252, A081253 and A081254
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 related to distance to nearest element of some set

Cf. A006165, A053188, A060973, A081134, A002450, A081252, A081253, A081254.

a:= n-> (h-> min(n-h, 2*h-n))(2^ilog2(n)):
seq(a(n), n=1..100);  # Alois P. Heinz, Mar 28 2021

np2[n_]:=Module[{min=Floor[Log[2,n]],max},max=min+1;If[2^max-nHarvey P. Dale, Feb 21 2012 *)

a(n)=vecmin(vector(n,i,abs(n-2^(i-1))))

for(n=1,89,p=2^floor(0.1^25+log(n)/log(2)); print1(min(n-p,2*p-n),","))

a(n) = my (p=#binary(n)); return (min(n-2^(p-1), 2^p-n)) \\ Rémy Sigrist, Mar 24 2018

def A053646(n): return min(n-(m := 2**(len(bin(n))-3)),2*m-n) # Chai Wah Wu, Mar 08 2022

a(2^k+i) = i for 1 <= i <= 2^(k-1); a(3*2^k+i) = 2^k-i for 1 <= i <= 2^k; (Sum_{k=1..n} a(k))/n^2 is bounded. - Benoit Cloitre, Aug 17 2002
a(n) = min(n-2^floor(log(n)/log(2)), 2*2^floor(log(n)/log(2))-n). - Klaus Brockhaus, Mar 08 2003
From Peter Bala, Aug 04 2022: (Start)
a(n) = a( 1 + floor((n-1)/2) ) + a( ceiling((n-1)/2) ).
a(2*n) = 2*a(n); a(2*n+1) = a(n) + a(n+1) for n >= 2. Cf. A006165. (End)
a(n) = 2*A006165(n) - n for n >= 2. - Peter Bala, Sep 25 2022

A005942 a(2n) = a(n) + a(n+1), a(2n+1) = 2a(n+1), if n >= 2.

Original entry on oeis.org

1, 2, 4, 6, 10, 12, 16, 20, 22, 24, 28, 32, 36, 40, 42, 44, 46, 48, 52, 56, 60, 64, 68, 72, 76, 80, 82, 84, 86, 88, 90, 92, 94, 96, 100, 104, 108, 112, 116, 120, 124, 128, 132, 136, 140, 144, 148, 152, 156, 160, 162, 164, 166, 168, 170, 172, 174, 176, 178, 180, 182

Offset: 0

N. J. A. Sloane, Jeffrey Shallit

a(n) is the subword complexity (or factor complexity) of Thue-Morse sequence A010060, that is, the number of factors of length n in A010060. See Allouche-Shallit (2003). - N. J. A. Sloane, Jul 10 2012

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003. See Problem 10, p. 335. - From N. J. A. Sloane, Jul 10 2012
J. Berstel et al., Combinatorics on Words: Christoffel Words and Repetitions in Words, Amer. Math. Soc., 2008. See p. 83.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..1000
S. Brlek, Enumeration of factors in the Thue-Morse word, Discrete Applied Math. 24 (1989), 83-96.
A. de Luca and S. Varricchio, Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups, Theoret. Comput. Sci. 63 (1989), 333-348.
Jakub Konieczny and Clemens Müllner, Arithmetical subword complexity of automatic sequences, arXiv:2309.03180 [math.NT], 2023.
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.
Luís M. S. Russo, Ana D. Correia, Gonzalo Navarro, and Alexandre P. Francisco, Approximating Optimal Bidirectional Macro Schemes, arXiv:2003.02336 [cs.DS], 2020.

Cf. A005943, A006697, A010060, A275202.

import Data.List (transpose)
a005942 n = a005942_list !! n
a005942_list = 1 : 2 : 4 : 6 : zipWith (+) (drop 6 ts) (drop 5 ts) where
   ts = concat $ transpose [a005942_list, a005942_list]
-- Reinhard Zumkeller, Nov 15 2012

a[0] = 1; a[1] = 2; a[2] = 4; a[3] = 6; a[n_?EvenQ] := a[n] = a[n/2] + a[n/2 + 1]; a[n_?OddQ]  := a[n] = 2*a[(n + 1)/2]; Array[a,60,0] (* Jean-François Alcover, Apr 11 2011 *)

a(n)=if(n<4,2*max(0,n)+(n==0),if(n%2,2*a((n+1)/2),a(n/2)+a(n/2+1)))

a(n) = 2*(A006165(n-1) + n - 1), n > 1.
G.f. (1+x^2)/(1-x)^2 + 2*x^2/(1-x)^2 * Sum_{k>=0} (x^2^(k+1)-x^(3*2^k)). - Ralf Stephan, Jun 04 2003
For n > 2, a(n) = 3*(n-1) + A053646(n-1). - Max Alekseyev, May 15 2011
a(n) = 2*A275202(n-1) for n > 1. - N. J. A. Sloane, Jun 04 2019

Typo in definition corrected by Reinhard Zumkeller, Nov 15 2012

A356988 a(n) = n - a^[2](n - a^[3](n-1)) with a(1) = 1, where a^[2](n) = a(a(n)) and a^[3](n) = a(a(a(n))).

Original entry on oeis.org

1, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 8, 8, 9, 10, 11, 12, 13, 13, 13, 13, 14, 15, 16, 17, 18, 19, 20, 21, 21, 21, 21, 21, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 34, 34, 34, 34, 34, 34, 34, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 55, 55, 55, 55, 55

Offset: 1

Peter Bala, Sep 08 2022

This is the second sequence in a family of nested-recurrent sequences with apparently similar structure defined as follows. Given a sequence s = {s(n) : n >= 1} we define the k-th iterated sequence s^[k] by putting s^[1](n) = s(n) and setting s^[k](n) = s^[k-1](s(n)) for k >= 2. For k >= 1, we define a nested-recurrent sequence, dependent on k, by putting u(1) = 1 and setting u(n) = n - u^[k](n - u^[k+1](n-1)) for n >= 2. This is the case k = 2. For other cases see A006165 (k = 1), A356989 (k = 3) and A356990 (k = 4).
The sequence is slow, that is, for n >= 1, a(n+1) - a(n) is either 0 or 1. The sequence is unbounded.
The line graph of the sequence {a(n)} thus consists of a series of plateaus (where the value of the ordinate a(n) remains constant as n increases) joined by lines of slope 1.
The sequence of plateau heights begins 3, 5, 8, 13, 21, 34, 55, ..., the Fibonacci numbers A000045.
The plateaus start at abscissa values n = 4, 7, 11, 18, 29, 47, 76, ..., the Lucas numbers A000032, and finish at abscissa values n = 5, 8, 13, 21, 34, 55, 89, ..., the Fibonacci numbers. The sequence of plateau lengths 1, 1, 2, 3, 5, 8, 13, ... is thus the Fibonacci sequence.
The iterated sequences{a^[k](n) : n >= 1}, k = 2, 3,..., share similar properties to the present sequence. See the Example section below.

			Related sequences:
1) The square of the sequence: {a^[2](n) : n >= 1} = {a(a(n)) : n >= 1}. The first few terms are
  1, 1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 5, 6, 7, 8, 8, 8, 8, 8, 8, 9, 10, 11, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 15, 16, 17, 18, 19, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 35, 36, 37, 38, 39, ...
The sequence is slow. The line graph of the sequence has plateaus of height Fibonacci(k), k >= 2, starting at abscissa value 2*Fibonacci(k) and ending at abscissa Fibonacci(k+2).
2) The cube of the sequence: {a^[3](n) : n >= 1} = {a(a(a(n))) : n >= 1}. The first few terms are
  1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 4, 5, 5, 5, 5, 5, 5, 5, 6, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 10, 11, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 15, 16, 17, 18, 19, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 22, 23, 24, 25, 26, 27, ...
The line graph of the sequence has plateaus of height Fibonacci(k), k >= 2, starting at abscissa value 3*Fibonacci(k) and ending at abscissa Fibonacci(k+3).

Peter Bala, Notes on A356988

Cf. A000032, A000045, A001611, A006165, A022114, A022120, A022367, A104449, A356989, A356990, A356991 - A356999.

a := proc(n) option remember; if n = 1 then 1 else n - a(a(n - a(a(a(n-1))))) end if; end proc:
seq(a(n), n = 1..100);

a(n+1) - a(n) = 0 or 1.
The terms of the sequence are completely determined by the following two results:
a) for n >= 2, a(L(n-1) + j) = F(n) for 0 <= j <= F(n-3), where F(n) = A000045(n), the n-th Fibonacci number with F(-1) = 1 and L(n) = A000032(n), the n-th Lucas number;
b) for n >= 2, a(F(n+1) + j) = F(n) + j for 0 <= j <= F(n-1).
Hence a(F(n+2)) = a(F(n+1)) + a(F(n)) for n >= 2 and a(L(n+2)) = a(L(n+1)) + a(L(n)) for n >= 0.
a(2*F(n)) = Lucas(n-1) for n >= 2;
a(3*F(n)) = 2*F(n) for n >= 1;
a(4*F(n)) = F(n+2) for n >= 2;
a(5*F(n)) = 4*F(n) - F(n-1) = A022120(n-2) for n >= 2.
a(2*L(n)) = F(n) + 3*F(n-1) = A104449(n) for n >= 0;
a(3*L(n)) = F(n+3) for n >= 3;
a(4*L(n)) = F(n+4) - L(n-3) = A022114(n-1) for n >= 3;
a(5*L(n)) = 11*F(n-1) + F(n-4) = A022367(n-1) for n >= 4.
For n >= 1, m >= 2, a(F(m*n)) = F(m*n-1) and a(L(m*n)) = F(m*n+1). Hence
a(L(m*n)) + a(F(m*n)) = L(m*n) and a(L(m*n)) - a(F(m*n)) = F(m*n).
Conjectures:
1) a(n) + a^[2](n - a^[2](n - a^[2](n))) = n for n >= 2.
2) If k >= 2 and  m = 2*k - 1 then a(m*n - a(k*n)) = a(m*n - a(m*n - a(m*n - a(k*n)))).

A375825 Triangle read by rows where row n is the Eytzinger array layout of n elements (a permutation of {1..n}).

Original entry on oeis.org

1, 2, 1, 2, 1, 3, 3, 2, 4, 1, 4, 2, 5, 1, 3, 4, 2, 6, 1, 3, 5, 4, 2, 6, 1, 3, 5, 7, 5, 3, 7, 2, 4, 6, 8, 1, 6, 4, 8, 2, 5, 7, 9, 1, 3, 7, 4, 9, 2, 6, 8, 10, 1, 3, 5, 8, 4, 10, 2, 6, 9, 11, 1, 3, 5, 7, 8, 4, 11, 2, 6, 10, 12, 1, 3, 5, 7, 9, 8, 4, 12, 2, 6, 10, 13, 1, 3, 5, 7, 9, 11

Offset: 1

Darío Clavijo, Aug 30 2024

The Eytzinger layout arranges elements of an array so that a binary search can be performed starting with index k = 1 and at a given k step to 2*k or 2*k+1, according to whether the target is smaller or larger than the element at k.

Row n is formed by: Take a binary search tree of n vertices which is a complete tree except for a possibly incomplete last row; number the vertices 1 to n by an in-order traversal; then read those vertex numbers row-wise (breadth first).

			Triangle begins:
   n  | k 1  2  3  4  5  6  7   8  9  10
  ---------------------------------------
   1  |   1
   2  |   2, 1
   3  |   2, 1, 3
   4  |   3, 2, 4, 1
   5  |   4, 2, 5, 1, 3
   6  |   4, 2, 6, 1, 3, 5
   7  |   4, 2, 6, 1, 3, 5, 7
   8  |   5, 3, 7, 2, 4, 6, 8,  1
   9  |   6, 4, 8, 2, 5, 7, 9,  1, 3
   10 |   7, 4, 9, 2, 6, 8, 10, 1, 3, 5
For n=10, the binary search tree numbered in-order is as follows and row 10 is by reading row-wise.
           7
         /   \
       4       9
     /  \     / \
    2    6   8   10
   /\   /
  1  3  5

Gergely Flamich, Stratis Markou and José Miguel Hernández-Lobato, Fast Relative Entropy Coding with A* coding, arXiv:2201.12857 [cs.IT], 2022. (Section 3)
Paul-Virak Khuong and Pat Morin, Array Layouts for Comparison-Based Searching, arXiv:1509.05053 [cs.DS], 2017.
Sergey Slotin, Eytzinger binary search.

Cf. A000217 (row sums), A375544 (alternating row sums), A006257 (main diagonal, (central terms)/2), A006165 (col 1).

Cf. A368783 (rank), A370006 (SJT rank), A369802 (inversions).

def A375825row(n):
    row = [0] * (n + 1)
    def e_rec(j, i):
        if j <= n:
            i = e_rec(2 * j, i)
            row[j] = i
            i = e_rec(2 * j + 1, i + 1)
        return i
    e_rec(1, 1)
    return row

A060973 a(2n+1) = a(n+1)+a(n), a(2n) = 2*a(n), with a(1)=0 and a(2)=1.

Original entry on oeis.org

0, 1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 4, 5, 6, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 10, 11, 12, 13, 14, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32

Offset: 1

Henry Bottomley, May 09 2001

			a(6) = 2*a(3) = 2*1 = 2.
a(7) = a(3) + a(4) = 1 + 2 = 3.

R. J. Mathar, Table of n, a(n) for n = 1..1000
Max A. Alekseyev, Enumeration of Payphone Permutations, arXiv:2304.04324 [math.CO], 2023.
Michael De Vlieger, Log-log scatterplot of a(n), n = 1..2^16.
H.-K. 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.
H.-K. 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
Jeffrey Shallit, Intertwining of Complementary Thue-Morse Factors, arXiv:2203.02917 [cs.FL], 2022.
Ralf Stephan, Some divide-and-conquer sequences ....
Ralf Stephan, Table of generating functions.

Cf. A006165, A053646.

A060973 := proc(n)
    option remember;
    if n <= 2 then
        return n-1;
    fi;
    if n mod 2 = 0 then
        2*procname(n/2)
    else
        procname((n-1)/2)+procname((n+1)/2);
    fi;
end proc:  # R. J. Mathar Nov 30 2014

nn = 77; Array[Set[a[#], # - 1] &, 2]; Do[Set[a[i], If[EvenQ[i], 2 a[i/2], a[# + 1] + a[#] &[(i - 1)/2]]], {i, 3, nn}]; Array[a, nn] (* Michael De Vlieger, Mar 22 2022 *)

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

from functools import lru_cache
@lru_cache(maxsize=None)
def A060973(n): return n-1 if n <= 2 else A060973(n//2) + A060973((n+1)//2) # Chai Wah Wu, Mar 08 2022

a(n) = n - A006165(n) = A006165(n) - A053646(n) = (n - A053646(n))/2 [for n > 1].
If n = 2*(2^m) + k with 0 <= k <= 2^m, then a(n) = 2^m; if n = 3*(2^m) + k with 0 <= k <= 2^m, then a(n) = 2^m + k.
G.f.: -x/(1 - x) + x/(1 - x)^2 * ( 1 + Sum_{k >= 0} t^2*(t - 1) ), t = x^(2^k). - Ralf Stephan, Sep 12 2003
Conjectures from Peter Bala, Aug 03 2022: (Start)
a(n - a(n)) = a(n - a(n - a(n - a(n)))).
If b(n) = a(a(n)) then b(n - b(n)) = b(n - b(n - b(n - b(n)))) for n >= 2. (End)
Sum_{n>=2} 1/a(n)^2 = Pi^2/6 + 2. - Amiram Eldar, Sep 08 2022

A275202 Subword complexity (number of distinct blocks of length n) of the period doubling sequence A096268.

Original entry on oeis.org

2, 3, 5, 6, 8, 10, 11, 12, 14, 16, 18, 20, 21, 22, 23, 24, 26, 28, 30, 32, 34, 36, 38, 40, 41, 42, 43, 44, 45, 46, 47, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126, 128, 130, 132, 134, 136, 138, 140, 142, 144, 146, 148, 150, 152, 154, 156, 158, 160, 161, 162, 163, 164, 165

Offset: 1

Daniel Rust, Jul 19 2016

			For n = 1 there are two words {0,1}.
For n = 2 there are three words {00,01,10}.
For n = 3 there are five words {000,001,010,100,101}.

Jinyuan Wang, Table of n, a(n) for n = 1..1000
Scott Balchin and Dan Rust, Computations for Symbolic Substitutions, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.
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.

Cf. A006165, A096268, A035263, A005942.

a := proc(n) option remember; if n = 1 then 2 elif n = 2 then 3 else a(iquo(n,2)) + a(iquo(n+1,2)) end if; end proc:
seq(a(n), n = 1..100); # Peter Bala, Aug 05 2022

t = Nest[Flatten[# /. {0 -> {1, 0}, 1 -> {0, 0}}] &, {1}, 12]; Table[2^n - Count[SequencePosition[t, #] & /@ Tuples[{0, 1}, n], {}], {n, 16}] (* Michael De Vlieger, Jul 19 2016, Version 10.1, after Robert G. Wilson v at A096268 *)

lista(nn) = {my(v=vector(nn-nn%2)); v[1]=2; v[2]=3; for(n=2, nn\2, v[2*n-1]=v[n-1]+v[n]; v[2*n]=2*v[n]); v; } \\ Jinyuan Wang, Feb 27 2020

a(n) = my(k=logint(n,2)-1); if(bittest(n,k), n + 2<Kevin Ryde, Aug 09 2022

a(n) = A005942(n+1)/2, and the latter satisfies a simple recurrence. - N. J. A. Sloane, Jun 04 2019

Proof: let b(n) = A096268(n) and c(n) = b(2n+1). For n >= 2, distinct blocks of length 2n are of the form 0_0_...0_ or 0_0..._0, and distinct blocks of length 2n-1 are of the form 0_0...0 or _0_0...0. Therefore, a(2n) is twice the n-subword complexity of {c(k)}, and a(2n-1) is the sum of (n-1)-subword complexity and n-subword complexity of {c(k)}. Note that n-subword complexity of {c(k)} is a(n) because c(2k) = b(4k+1) = 1, c(4k+1) = b(8k+3) = b(2k) = 0 and c(4k+3) = b(8k+7) = b(2k+1) = c(k). In conclusion, a(2n) = 2a(n) and a(2n-1) = a(n-1) + a(n), with a(1) = 2 and a(2) = 3. So a(n) = A005942(n+1)/2. - Jinyuan Wang, Feb 27 2020

A356990 a(n) = n - a^[4](n - a^[5](n-1)) with a(1) = 1, where a^[4](n) = a(a(a(a(n)))) and a^[5](n) = a(a(a(a(a(n))))).

Original entry on oeis.org

1, 1, 2, 3, 4, 5, 5, 6, 7, 7, 8, 9, 10, 10, 11, 12, 13, 14, 14, 15, 16, 17, 18, 19, 19, 19, 20, 21, 22, 23, 24, 25, 26, 26, 26, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 36, 36, 36, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 50, 50, 50, 50, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 69, 69, 69, 69, 69, 69, 69, 70, 71

Offset: 1

Peter Bala, Sep 08 2022

This is the fourth sequence in a family of nested-recurrent sequences with apparently similar structure defined as follows. Given a sequence s = {s(n); n >= 1} we define the k-th iterated sequence s^[k] by putting s^[1](n) = s(n) and setting s^[k](n) = s^[k-1](u(n)) for k >= 2. For k >= 1, we define a nested-recurrent sequence {u(n): n >= 1}, dependent on k, by putting u(1) = 1 and setting u(n) = n - u^[k](n - u^[k+1](n-1)) for n >= 2. This is the case k = 4. For other cases see A006165 (k = 1), A356988 (k = 2) and A356989 (k = 3).
The sequence is slow, that is, for n >= 1, a(n+1) - a(n) is either 0 or 1.
The line graph of the sequence {a(n)} thus consists of a series of plateaus (where the value of the ordinate a(n) remains constant as n increases) joined by lines of slope 1.
The sequence of plateau heights begins 5, 7, 10, 14, 19, 26, 36, 50, ..., which appears to be A003269.
The plateaus start at absiccsa values n = 6, 9, 13, 18, 24, 33, 46, 64, ..., which appears to be A014101, and terminate at abscissa values 7, 10, 14, 19, 26, 36, 50, ..., conjecturally A003269.

Cf. A003269, A006165, A014101, A356988, A356989.

a := proc(n) option remember; if n = 1 then 1 else n - a(a(a(a(n - a(a(a(a(a(n-1))))))))) end if; end proc:
seq(a(n), n = 1..100);

from functools import lru_cache
@lru_cache(maxsize=None)
def A356990(n): return 1 if n <= 1 else n-A356990(A356990(A356990(A356990(n-A356990(A356990(A356990(A356990(A356990(n-1))))))))) # Chai Wah Wu, Oct 01 2022

A006166 a(0)=0, a(1)=a(2)=1; for n >= 1, a(3n+2) = 2a(n+1) + a(n), a(3n+1) = a(n+1) + 2a(n), a(3n) = 3a(n).

Original entry on oeis.org

0, 1, 1, 3, 3, 3, 3, 5, 7, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69

Offset: 0

N. J. A. Sloane

J. Arkin, D. C. Arney, L. S. Dewald and W. E. Ebel, Jr., Families of recursive sequences, J. Rec. Math., 22 (No. 22, 1990), 85-94.
vN. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29. [Preprint.]
Hsien-Kuei Hwang, Svante Janson and Tsung-Hsi 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, Svante Janson and Tsung-Hsi Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, Vol. 13, No. 4 (2017), Article #47.

a(n) + n = A003605(n). Cf. A006165, A080678, A081134.

From Peter Bala, Oct 08 2022: (Start)
a(n+2) - a(n) = 0 or 2.
a(3^k + j) = 3^k for k >= 0 and for 0 <= j <= 3^k.
a(2*3^k + j) = 3^k + 2*j for k >= 0 and for 0 <= j <= 3^k.
A081134(n) = n - a(n). (End)

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 28 2003

cp's OEIS Frontend

A357564 a(n) = n - 2*b(b(n)) for n >= 2, where b(n) = A006165(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A042965 Nonnegative integers not congruent to 2 mod 4.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A053646 Distance to nearest power of 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

A005942 a(2n) = a(n) + a(n+1), a(2n+1) = 2a(n+1), if n >= 2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

Extensions

A356988 a(n) = n - a^[2](n - a^[3](n-1)) with a(1) = 1, where a^[2](n) = a(a(n)) and a^[3](n) = a(a(a(n))).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A375825 Triangle read by rows where row n is the Eytzinger array layout of n elements (a permutation of {1..n}).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

A060973 a(2n+1) = a(n+1)+a(n), a(2n) = 2*a(n), with a(1)=0 and a(2)=1.