A055010 -id:A055010 - cp's OEIS frontend

A204202 Triangle based on (0,2/3,1) averaging array.

2, 2, 5, 2, 7, 11, 2, 9, 18, 23, 2, 11, 27, 41, 47, 2, 13, 38, 68, 88, 95, 2, 15, 51, 106, 156, 183, 191, 2, 17, 66, 157, 262, 339, 374, 383, 2, 19, 83, 223, 419, 601, 713, 757, 767, 2, 21, 102, 306, 642, 1020, 1314, 1470, 1524, 1535, 2, 23, 123, 408, 948

Offset: 1

Clark Kimberling, Jan 12 2012

See A204201 for a discussion of averaging arrays and related triangles

			First six rows:
2
2...5
2...7....11
2...9....18...23
2...11...27...41...47
2...13...38...68...88..95

Cf. A204201.

a = 0; r = 2/3; b = 1;
t[1, 1] = r;
t[n_, 1] := (a + t[n - 1, 1])/2;
t[n_, n_] := (b + t[n - 1, n - 1])/2;
t[n_, k_] := (t[n - 1, k - 1] + t[n - 1, k])/2;
u[n_] := Table[t[n, k], {k, 1, n}]
Table[u[n], {n, 1, 5}]   (* averaging array *)
u = Table[(1/r) 2^n*u[n], {n, 1, 12}];
TableForm[u]  (* A204202 triangle *)
Flatten[u]    (* A204202 sequence *)

From Philippe Deléham, Dec 24 2013: (Start)
T(n,n) = A055010(n) = A083329(n) = A153893(n-1).
Sum_{k=1..n} T(n,k) = A066373(n+1).
T(n,k) = T(n-1,k)+3*T(n-1,k-1)-2*T(n-2,k-1)-2*T(n-2,k-2), T(1,1)=2, T(2,1)=2, T(2,2)=5, T(n,k)=0 if k<1 or if k>n. (End)

A323420 Lexicographically earliest sequence of positive integers such that for any n > 0, a(n + a(n)) > a(n).

Original entry on oeis.org

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

Offset: 1

Rémy Sigrist, Aug 30 2019

nonn

Every positive integer appears in the sequence.
Empirically:
- for any n > 0, the least d > 0 such that a(n) = a(n+d) is a power of 2 (see scatterplot in Links section),
- the run-length transform of the first differences of the positions of the 1's in the sequence corresponds to A055010 (excluding the leading 0).

			a(1) = 1, hence a(1 + a(1)) = a(2) > 1.
a(2) = 2, hence a(2 + a(2)) = a(4) > 2.
a(3) = 1, hence a(3 + a(1)) = a(4) > 1.
a(4) = 3, etc.

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Rémy Sigrist, Colored scatterplot of the first 100000 terms (where the color is function of the least d > 0 such that a(n) = a(n+d))

Cf. A000124, A055010.

a = vector(84, n, 1); for (n=1, #a, print1 (a[n] ", "); nan = n+a[n]; if (nan <= #a, a[nan] = max(a[nan], 1+a[n])))

a(A000124(n)) = n + 1 for any n >= 0.

A335133 Binary interpretation of the left diagonal of the EQ-triangle with first row generated from the binary expansion of n, with most significant bit given by first row.

Original entry on oeis.org

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

Offset: 0

Rémy Sigrist, May 24 2020

For any nonnegative number n, the EQ-triangle for n is built by taking as first row the binary expansion of n (without leading zeros), having each entry in the subsequent rows be the EQ of the two values above it (a "1" indicates that these two values are equal, a "0" indicates that these values are different).

This sequence is a self-inverse permutation of the nonnegative numbers.

			For n = 42:
- the binary representation of 42 is "101010",
- the corresponding EQ-triangle is:
         1 0 1 0 1 0
          0 0 0 0 0
           1 1 1 1
            1 1 1
             1 1
              1
- the bits on the left diagonal are: 1, 0, 1, 1, 1, 1,
- so a(42) = 2^5 + 2^3 + 2^2 + 2^1 + 2^0 = 47.

Rémy Sigrist, Table of n, a(n) for n = 0..8192 (n = 0..2^13)
Index entries for sequences related to binary expansion of n
Index entries for sequences that are permutations of the natural numbers

Cf. A055010, A070939, A279645, A334727 (XOR variant).

a(n) = {
    my (b=binary(n), v=0);
    forstep (x=#b-1, 0, -1,
        if (b[1], v+=2^x);
        b=vector(#b-1, k, b[k]==b[k+1])
    );
    return (v)
}

a(floor(n/2)) = floor(a(n)/2).
abs(a(2*n+1) - a(2*n)) = 1.
a(2^k) = 2^k for any k >= 0.
a(2^k+1) = 2^k+1 for any k >= 0.
a(2^k-1) = 2^k-1 for any k >= 0.
Apparently, a(n) + A334727(n) = A055010(A070939(n)) for any n > 0.

A060152 Nim-factorial(a(n))=1.

Original entry on oeis.org

1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 62914, 65535, 131071, 262143, 524287, 716479, 1048575, 1132639, 2069471, 2097151, 3618111, 4194303, 8388607

Offset: 1

John W. Layman, Mar 09 2001

nonn

Except for the term a(16)=62914, all listed terms agree with those of A000225: 2^n - 1.

A059970 (Nim-factorials), A055010.

a(18)-a(28) from Sean A. Irvine, Oct 28 2022

A129161 Triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n and having height k (1 <= k <= n).

Original entry on oeis.org

1, 1, 2, 1, 5, 4, 1, 11, 16, 8, 1, 23, 53, 44, 16, 1, 47, 165, 186, 112, 32, 1, 95, 494, 725, 568, 272, 64, 1, 191, 1442, 2707, 2576, 1600, 640, 128, 1, 383, 4141, 9813, 11065, 8184, 4272, 1472, 256, 1, 767, 11763, 34827, 45961, 39026, 24208, 10976, 3328, 512

Offset: 1

Emeric Deutsch, Apr 03 2007

A skew Dyck path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1)(up), D=(1,-1)(down) and L=(-1,-1)(left) so that up and left steps do not overlap. The length of the path is defined to be the number of its steps.

Row sums yield A002212.

			T(3,2)=5 because we have UDUUDD, UDUUDL, UUDDUD, UUDUDD and UUDUDL.
Triangle starts:
  1;
  1,  2;
  1,  5,  4;
  1, 11, 16,  8;
  1, 23, 53, 44, 16;

E. Deutsch, E. Munarini, S. Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203

Cf. A000079, A002212, A055010, A129162.

H[0]:=1: for k from 1 to 11 do H[k]:=simplify((1+z*H[k-1]-z)/(1-z*H[k-1])) od: for k from 1 to 11 do h[k]:=factor(simplify(H[k]-H[k-1])) od: for k from 1 to 11 do hser[k]:=series(h[k],z=0,15) od: T:=(n,k)->coeff(hser[k],z,n): for n from 1 to 11 do seq(T(n,k),k=1..n) od; # yields sequence in triangular form

T(n,1) = 1;
T(n,2) = 3*2^(n-2) - 1 = A055010(n-1).
T(n,n) = 2^(n-1) = A000079(n-1).
Sum_{k=1..n} k*T(n,k) = A129162(n).
Column k has g.f. h[k]=H[k]-H[k-1], where H[k]=(1-z+zH[k-1])/(1-zH[k-1]), H[0]=1 (H[k] is the g.f. of paths of height at most k). For example, h[1]=z/(1-z); h[2]=z^2*(2-z)/[(1-z)(1-2z)]; h[3]=z^3*(2-z)^2/[(1-2z)(1-3z+z^2-z^3)].

A213668 Irregular triangle read by rows: T(n,k) is the number of dominating subsets with k vertices of the graph G(n) consisting of a pair of endvertices joined by n internally disjoint paths of length 2 (the n-ary generalized theta graph THETA_{2,2,...2}; n>=1, 1<=k<=n+2).

Original entry on oeis.org

1, 3, 1, 0, 6, 4, 1, 0, 7, 10, 5, 1, 0, 9, 16, 15, 6, 1, 0, 11, 25, 30, 21, 7, 1, 0, 13, 36, 55, 50, 28, 8, 1, 0, 15, 49, 91, 105, 77, 36, 9, 1, 0, 17, 64, 140, 196, 182, 112, 45, 10, 1, 0, 19, 81, 204, 336, 378, 294, 156, 55, 11, 1

Offset: 1

Emeric Deutsch, Jul 06 2012

Row n>=2 contains n+1 entries.
Sum of entries in row n=3*2^n-1 = A052940(n) = A153893(n) = A055010(n+1) = A083329(n+1).
The graph G(n) is the join of the graph consisting of 2 isolated vertices and the graph consisting of n isolated vertices. Then the expression of the domination polynomial follows from Theorem 12 of the Akbari et al. reference.

			Row 1 is 1,3,1 because the graph G(1) is the path abc; there are 1 dominating subset of size 1 ({b}), 3 dominating subsets of size 2 ({a,b}, {a,c}, {b,c}), and 1 dominating subset of size 3 ({a,b,c}).
Row 2 is 0,6,4,1 because the graph G(2) is the cycle a-b-c-d-a and has dominating subsets ab, ac, ad, bc, bd, cd, abc, abd, acd, bcd, and abcd (see A212634).
Triangle starts:
1,3,1;
0,6,4,1;
0,7,10,5,1;
0,9,16,15,6,1;

S. Akbari, S. Alikhani, and Y. H. Peng, Characterization of graphs using domination polynomials, European J. Comb., 31, 2010, 1714-1724.

S. Alikhani and Y. H. Peng, Introduction to domination polynomial of a graph, arXiv:0905.2251.
T. Kotek, J. Preen, F. Simon, P. Tittmann, and M. Trinks, Recurrence relations and splitting formulas for the domination polynomial, arXiv:1206.5926.

Cf. A052940, A153893, A055010, A083329, A212634

p := proc (n) options operator, arrow: ((1+x)^n-1)*((1+x)^2-1)+x^n+x^2 end proc: for n to 12 do seq(coeff(p(n), x, k), k = 1 .. n+2) end do; # yields sequence in triangular form

T[n_, k_] := SeriesCoefficient[((1+x)^n-1) ((1+x)^2-1)+x^n+x^2, {x, 0, k}];
Table[T[n, k], {n, 1, 9}, {k, 1, n+2}] // Flatten (* Jean-François Alcover, Dec 06 2017 *)

The generating polynomial of row n is p(n)=((1+x)^n-1)*((1+x)^2-1)+x^n+x^2; by definition, p(n) is the domination polynomial of the graph G(n).
Bivariate g.f.: x*z/(1-x*z)-2*x*z/(1-z)+x*z*(1+x)*(2+x)/(1-z-x*z).
T(n,3)=n^2 for n!=3.

A249452 Numbers k such that A249441(k) = 3.

Original entry on oeis.org

15, 31, 47, 63, 95, 127, 191, 255, 383, 511, 767, 1023, 1535, 2047, 3071, 4095, 6143, 8191, 12287, 16383, 24575, 32767, 49151, 65535, 98303, 131071, 196607, 262143, 393215, 524287, 786431, 1048575, 1572863, 2097151, 3145727, 4194303, 6291455, 8388607, 12582911

Offset: 1

Vladimir Shevelev, Oct 29 2014

Or k for which none of entries in the k-th row of Pascal's triangle (A007318) is divisible by 4 (cf. comment in A249441).
Using the Kummer carries theorem, one can prove that, for n>=2, a(n) has the form of either 1...1 or 101...1 in base 2.
The sequence is a subset of so-called binomial coefficient predictors (BCP) in base 2 (see Shevelev link, Th. 6 and Cor. 8), which were found also using Kummer theorem and have a very close binary structure.

E. E. Kummer, Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen, J. Reine Angew. Math. 44 (1852), 93-146.
V. Shevelev, Binomial Coefficient Predictors, Journal of Integer Sequences, Vol. 14 (2011), Article 11.2.8
Index entries for linear recurrences with constant coefficients, signature (1,2,-2).

Cf. A000225, A029744, A048278, A052955, A055010, A089633, A249441.

CoefficientList[Series[(15 + 16 x - 14 x^2 - 16 x^3)/(1 - x -2 x^2 + 2 x^3), {x, 0, 70}], x] (* Vincenzo Librandi, Oct 30 2014 *)
LinearRecurrence[{1,2,-2},{15,31,47,63},40] (* Harvey P. Dale, Apr 01 2019 *)

a(n)=if(n==1, 15, (n%2+2)<<(n\2+3)-1) \\ Charles R Greathouse IV, Nov 06 2014

is(n)=(n+1)>>valuation(n+1, 2)<5 && !setsearch([1, 2, 3, 5, 7, 11, 23], n) \\ Charles R Greathouse IV, Nov 06 2014

a(n) has either form 2^k - 1 or 3*2^m-1, k, m >= 4 (cf. A000225, A055010). Since, for k>=5, 2^k-1<3*2^(k-1)-1<2^(k+1)-1, we have that, for n>=1, a(2*n) = 2^(n+4)-1; a(2*n+1) = 3*2^(n+3)-1. - Vladimir Shevelev, Oct 29 2014, Nov 06 2014
a(1) = 15, and for n>1, a(n) = A052955(n+6). [Follows from above] - Antti Karttunen, Nov 03 2014
G.f.: (15+16*x-14*x^2-16*x^3)/(1-x-2*x^2+2*x^3); a(n) = 16*A029744(n)-1. - Peter J. C. Moses, Oct 30 2014

More terms from Peter J. C. Moses, Oct 29 2014

A367252 a(n) is the number of ways to tile an n X n square as explained in comments.

Original entry on oeis.org

1, 0, 1, 4, 88, 3939, 534560, 185986304, 175655853776, 437789918351688, 2898697572048432368, 50698981110982431863735, 2342038257118692026082013568, 285250169294740386915765591840768, 91531011920509198679773321121428857296, 77312253225939431362091700178995800855209496

Offset: 0

Anna Tscharre, Nov 11 2023

nonn

Draw a Dyck path from (0,0) to (n,n) so the path always stays above the diagonal. Now section the square into horizontal rows of height one to the left of the path and tile these rows using 1 X 2 and 1 X 1 tiles. Similarly, section the part to the right of the path into columns with width one and tile these using 2 X 1 and 1 X 1 tiles. Furthermore, no 1 X 1 tiles are allowed in the bottom row.

Anna Tscharre, A possible 6 X 6 tiling

Special case of A003150.

Cf. A055010, A307082.

b:= proc(x, y) option remember; (F->
     `if`(x=0 and y=0, 1, `if`(x>0, b(x-1, y)*F(y-1), 0)+
     `if`(y>x, b(x, y-1)*F(x+1), 0)))(combinat[fibonacci])
    end:
a:= n-> b(n$2):
seq(a(n), n=0..15);  # Alois P. Heinz, Nov 11 2023

b[x_, y_] := b[x, y] = With[{F = Fibonacci},
     If[x == 0 && y == 0, 1,
     If[x > 0, b[x - 1, y]*F[y - 1], 0] +
     If[y > x, b[x, y - 1]*F[x + 1], 0]]];
a[n_] := b[n, n];
Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Nov 14 2023, after Alois P. Heinz *)

a(n) == 1 (mod 2) <=> n in { A055010 }. - Alois P. Heinz, Nov 11 2023

A377612 a(n) is the number of iterations of x -> 2*x + 1 until (# composites reached) = (# primes reached), starting with prime(n).

Original entry on oeis.org

15, 7, 13, 1, 11, 1, 1, 1, 7, 7, 1, 1, 5, 1, 1, 11, 1, 1, 1, 1, 1, 1, 3, 23, 1, 1, 1, 1, 1, 11, 1, 3, 1, 1, 1, 1, 1, 1, 1, 3, 19, 1, 3, 1, 1, 1, 1, 1, 1, 1, 7, 3, 1, 3, 1, 1, 1, 1, 1, 3, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 17, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1, 3

Offset: 1

Clark Kimberling, Nov 05 2024

nonn

For a guide to related sequences, see A377609.

			Starting with prime(1) = 2, we have 2*2+1 = 5, then 2*5+1 = 11, etc., resulting in a chain 2, 5, 11, 23, 47, 95, 191, 383, 767, 1535, 3071, 6143, 12287, 24575, 49151, 983033 having 8 primes and 8 composites. Since every initial subchain has fewer composites than primes, a(1) = 16-1 = 15. (For more terms from the mapping x -> 2x+1, see A055010.)

Cf. A377609.

chain[{start_, u_, v_}] := NestWhile[Append[#, u*Last[#] + v] &, {start}, !
     Count[#, ?PrimeQ] == Count[#, ?(! PrimeQ[#] &)] &];
chain[{Prime[1], 2, 1}]
Map[Length[chain[{Prime[#], 2, 1}]] &, Range[100]] - 1
(* Peter J. C. Moses, Oct 31 2024 *)

A381764 Nearest integer not equal to n with the same Hamming weight (number of 1 bits) as n.

Original entry on oeis.org

2, 1, 5, 2, 6, 5, 11, 4, 10, 9, 13, 10, 14, 13, 23, 8, 18, 17, 21, 18, 22, 21, 27, 20, 26, 25, 29, 26, 30, 29, 47, 16, 34, 33, 37, 34, 38, 37, 43, 36, 42, 41, 45, 42, 46, 45, 55, 40, 50, 49, 53, 50, 54, 53, 59, 52, 58, 57, 61, 58, 62, 61, 95, 32, 66, 65, 69, 66

Offset: 1

Chai Wah Wu, Mar 06 2025

nonn

a(n) = integer m nearest to n such that m <> n and A000120(n) = A000120(m).
Theorem: a tie does not occur for n>0, i.e. A057168(n)-n <> n-A243109(n).
Proof: If n is of the form 2^k-1, then there are no smaller numbers with the same Hamming weight as n and a(n) = A057168(n) = (3n+1)/2.
If n is of the form (2^k-1)*2^m for some k,m>0, then n in binary is of the form 11..1100..00 and A057168(n) = 2^(k+m)+2^(k-1)-1, i.e. 100..0011..11 in binary. On the other hand, A243109(n) = (2^(k-1)-1)*2^(m+1)+2^(m-1), i.e. 11..110100..00 in binary. Thus A057168(n)-n = 2^(k-1)-1+2^m >= 2^m and n-A243109(n) = 2^(m-1) < 2^m. There is no tie and a(n) = A243109(n).
If n is not of the form (2^k-1)*2^m, then n in binary is of the form xxx...xxx0yyy...yyy, where xxxxxx and yyyyy are both not all zeros. If yyy...yyy is of the form 2^r-1, then A243109(n) must flip one of the '1' bit in xxx...xxx whereas A057168(n) leaves xxx...xxx unchanged. Thus n-A243109(n) > A057168(n)-n. Otherwise A057168(n) and A243109(n) will not change the bits xxx...xxx and reduces to the problem for yyy...yyy and thus the result follows by induction.
The above also gives a procedure to determine when a(n) = A057168(n) and when a(n) = A243109(n) or more succinctly a(n) = A243109(n) if n is even and a(n) = A057168(n) otherwise.

			For n = 2, A057168(2) = 4 and A243109(2) = 1 and 1 is closer to 2 than 4, thus a(2) = 1.

Robert Israel, Table of n, a(n) for n = 1..10000
Marc B. Reynolds, Popcount walks: next, previous, toward and nearest (2023).

Cf. A000120, A055010, A057168, A243109.

f:= proc(n) local t,k,d;
  if n::even then d:=-1 else d:= 1 fi;
  t:= convert(convert(n,base,2),`+`);
  for k from n+d by d do
    if convert(convert(k,base,2),`+`) = t then return k fi
  od
end proc:
map(f, [$1..100]); # Robert Israel, Jun 20 2025

def A381764(n): return n^((a:=-n&n+1)|(a>>1))

a(n) = A243109(n) if n is even and a(n) = A057168(n) otherwise.
a(2^k-1) = A055010(k).
For k,m > 0, a((2^k-1)*2^m) = 2^(m-1)*(2^(k+1)-3).

cp's OEIS Frontend

A204202 Triangle based on (0,2/3,1) averaging array.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A323420 Lexicographically earliest sequence of positive integers such that for any n > 0, a(n + a(n)) > a(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A335133 Binary interpretation of the left diagonal of the EQ-triangle with first row generated from the binary expansion of n, with most significant bit given by first row.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A060152 Nim-factorial(a(n))=1.

Views

Author

Keywords

Comments

Crossrefs

Extensions

A129161 Triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n and having height k (1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A213668 Irregular triangle read by rows: T(n,k) is the number of dominating subsets with k vertices of the graph G(n) consisting of a pair of endvertices joined by n internally disjoint paths of length 2 (the n-ary generalized theta graph THETA_{2,2,...2}; n>=1, 1<=k<=n+2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A249452 Numbers k such that A249441(k) = 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A367252 a(n) is the number of ways to tile an n X n square as explained in comments.

Views

Author