A129760 -id:A129760 - cp's OEIS frontend

A353245 a(n) = A353989(n) AND A353989(n+1), where AND is the binary AND operator.

1, 2, 2, 2, 8, 8, 4, 4, 6, 5, 1, 9, 5, 4, 16, 16, 18, 2, 1, 1, 24, 24, 8, 5, 6, 24, 1, 32, 8, 4, 32, 32, 34, 2, 17, 40, 40, 44, 6, 5, 5, 32, 48, 48, 52, 50, 17, 17, 21, 52, 56, 48, 49, 2, 2, 24, 21, 64, 8, 30, 29, 73, 65, 64, 64, 64, 64, 72, 76, 64, 80, 80, 68, 72, 80, 2, 1, 1, 80, 88, 92, 14

Offset: 1

Scott R. Shannon, May 15 2022

nonn

See A353989 for further details. A graph of the terms displays a repetitive structure below the line y = n. See the linked images.

			a(2) = 2 as A353989(2) = 3 = 11_2 and A353989(3) = 6 = 110_2, and the binary AND of 11_2 and 110_2 = 10_2 = 2.

Scott R. Shannon, Image of the first 10000 terms. The green line is y = n.
Scott R. Shannon, Image of the first 100000 terms.

Cf. A353989, A129760, A064413.

A348648 Triangle T(n, k), n >= 0, 0 <= k <= n, read by rows; the even terms of Pascal's triangle (A007318) are clustered as wXwXw subtriangles with w = 2^s-1 for some s > 0; if A007318(n, k) is even then T(n, k) gives the corresponding s otherwise T(n, k) = 0.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 2, 2, 2, 0, 0, 0, 2, 2, 0, 0, 0, 1, 0, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3, 3, 3, 3, 3, 3, 0, 0, 0, 3, 3, 3, 3, 3, 3, 0, 0, 0, 1, 0, 3, 3, 3, 3, 3, 0, 1, 0, 0, 0, 0, 0, 3, 3, 3, 3, 0, 0, 0, 0, 0, 2, 2, 2, 0, 3, 3, 3, 0, 2, 2, 2, 0

Offset: 0

Rémy Sigrist, Oct 27 2021

It is possible to build this triangle with the following procedure:
- T_0 is the 2X2X2 triangle with all 0's:
          ^
  T_0 =  /0\
        /0 0\
       +-----+
- for s > 0, T_s is obtained by arranging 3 copies of T_{s-1} and one wXwXw triangle (where w=2^s-1) will all s's as follows:
                 ^
                / \
               /   \
              /     \
             /T_{s-1}\
  T_s =     +---------+
           / \s ... s/ \
          /   \.   ./   \
         /     \. ./     \
        /T_{s-1}\s/T_{s-1}\
       +---------+---------+
- the triangle {T(n, k)} is the limit of T_s as s tends to infinity.
For any n >= 0, A001316(n) gives the number of 1's in row 4*n + 2 (and there are no 1's elsewhere).

			Triangle T(n, k) begins (with dots instead of 0's):
                    .
                   . .
                  . 1 .
                 . . . .
                . 2 2 2 .
               . . 2 2 . .
              . 1 . 2 . 1 .
             . . . . . . . .
            . 3 3 3 3 3 3 3 .
           . . 3 3 3 3 3 3 . .
          . 1 . 3 3 3 3 3 . 1 .
         . . . . 3 3 3 3 . . . .
        . 2 2 2 . 3 3 3 . 2 2 2 .
       . . 2 2 . . 3 3 . . 2 2 . .
      . 1 . 2 . 1 . 3 . 1 . 2 . 1 .
     . . . . . . . . . . . . . . . .

Rémy Sigrist, Table of n, a(n) for n = 0..8255 (rows for n = 0..127, flattened)
Rémy Sigrist, Colored representation of the first 2^9 rows (black pixels correspond to 0's)
Rémy Sigrist, Colored logarithmic scatterplot of A014428 (where the colors are given by the present sequence)
Rémy Sigrist, Colored logarithmic scatterplot of A007318 (where the colors are given by the present sequence, and black pixels denotes 0's)
Index entries for triangles and arrays related to Pascal's triangle

Cf. A001316, A007318, A047999, A014428, A129760.

T(n,k) = { if (n<=1, return (0)); my (s=#binary(n)-1); n-=2^s; if (k<=n, return (T(n,k)), k<2^s, return (s), return (T(n,k-2^s))) }

T(n, k) = 0 iff A047999(n, k) = 1.

2^T(n, 0) OR 2^T(n, 1) OR ... OR 2^T(n, n) = 1 + A129760(n+1) (where OR denotes the bitwise OR operator).

A352729 The binary expansion of a(n) contains the runs of consecutive 1's that appear both in the binary expansions of n and n+1.

Original entry on oeis.org

0, 0, 0, 0, 4, 0, 0, 0, 8, 8, 8, 0, 12, 0, 0, 0, 16, 16, 16, 16, 20, 16, 16, 0, 24, 24, 24, 0, 28, 0, 0, 0, 32, 32, 32, 32, 36, 32, 32, 32, 40, 40, 40, 32, 44, 32, 32, 0, 48, 48, 48, 48, 52, 48, 48, 0, 56, 56, 56, 0, 60, 0, 0, 0, 64, 64, 64, 64, 68, 64, 64, 64

Offset: 0

Rémy Sigrist, Mar 30 2022

We only consider runs of consecutive 1's that completely match in binary expansions of n and n+1, not simply single common 1's.

			For n = 42:
- the binary expansion of 42 is "101010",
- the binary expansion of 43 is "101011",
- the first two runs of 1's are the same, the others differ,
- so the binary expansion of a(42) is "101000",
- and a(42) = 40.

Rémy Sigrist, Table of n, a(n) for n = 0..8192
Index entries for sequences related to binary expansion of n

Cf. A129760, A352727.

A352724(n) = { my (r=[], o=0); while (n, my (v=valuation(n+n%2, 2)); if (n%2, r=concat(r, (2^v-1)*2^o)); o+=v; n\=2^v); r }
a(n) = vecsum(setintersect(A352724(n), A352724(n+1)))

a(n) = A352727(n, n+1).

A355621 a(1) = 1; for n > 1, a(n) is the number of terms in the first n-1 terms of the sequence that share a 1-bit with a(n-1) in their binary expansions.

Original entry on oeis.org

1, 1, 2, 1, 3, 5, 5, 6, 5, 8, 1, 8, 2, 4, 5, 11, 15, 17, 12, 11, 19, 17, 15, 23, 22, 19, 22, 21, 24, 16, 10, 18, 20, 21, 29, 33, 22, 30, 33, 23, 38, 31, 42, 28, 35, 37, 38, 37, 40, 22, 41, 40, 24, 33, 35, 46, 49, 49, 50, 47, 59, 60, 55, 61, 62, 61, 64, 1, 39, 63, 69, 58, 60, 64, 3, 60, 65, 46, 67

Offset: 1

Scott R. Shannon, Jul 10 2022

The indices where a(n) = 1 in the first 500000 terms are 1, 2, 4, 11, 68, 131, 2051, 4099. It is unknown if more exist. Many terms of the sequence are close to the line a(n) = n although only the first term is a possible fixed point. In the first 500000 terms the lowest values not to appear are 7, 9, 14, 25, 26. It is likely these and other numbers never appear although this is unknown.

			a(7) = 5 as a(6) = 5 and the total number of terms in the first six terms that share a 1-bit with 5 in their binary expansions is five, namely 1, 1, 1, 3, 5.

Scott R. Shannon, Table of n, a(n) for n = 1..10000
Scott R. Shannon, Image of the first 500000 terms. The green line is y = n.

Cf. A355625, A030190, A129760, A353989, A352763, A354606.

from itertools import count, islice
def agen():
    an, alst = 1, [1]
    for n in count(2):
        yield an
        an = sum(1 for k in alst if k&an)
        alst.append(an)
print(list(islice(agen(), 79))) # Michael S. Branicky, Jul 10 2022

A355625 a(1) = 1; for n > 1, a(n) is the number of terms in the first n-1 terms of the sequence that share a 1-bit with n in their binary expansions.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 4, 0, 3, 2, 6, 2, 6, 7, 11, 0, 6, 9, 13, 6, 13, 13, 18, 6, 11, 17, 21, 16, 21, 22, 26, 0, 14, 16, 26, 14, 23, 25, 31, 12, 22, 27, 34, 27, 33, 34, 39, 19, 31, 35, 43, 36, 44, 44, 49, 36, 42, 48, 52, 47, 52, 53, 57, 0, 29, 32, 48, 30, 48, 48, 57, 25, 41, 46, 56, 47, 57, 58, 65, 34

Offset: 1

Scott R. Shannon, Jul 10 2022

The indices where a(n) = 1 in the first 500000 terms are 1, 3, 6. It is likely no more exist although this is unknown. Many terms of the sequence are close to the line a(n) = n although only the first term is a possible fixed point. In the first 500000 terms the lowest values not to appear are 5, 8, 10, 15, 20, 24, 28. It is likely these and other numbers never appear although this is unknown. All terms for n > 1 where n is a power of 2 equal 0.

			a(7) = 4 as the total number of terms in the first six terms that share a 1-bit with 7 in their binary expansions is four, namely 1, 1, 2, 1.

Scott R. Shannon, Table of n, a(n) for n = 1..10000
Scott R. Shannon, Image of the first 500000 terms. The green line is y = n.

Cf. A355621, A030190, A129760, A353989, A352763, A354606.

from itertools import count, islice
def agen():
    an, alst = 1, [1]
    for n in count(2):
        yield an
        an = sum(1 for k in alst if k&n)
        alst.append(an)
print(list(islice(agen(), 80))) # Michael S. Branicky, Jul 10 2022

A381405 a(0) = 0; for n > 0, a(n) is the smallest unused number such that a(n) AND a(n-1) = 0, where AND is the binary AND operation, while the binary weight of a(n) does not equal that of a(n-1).

Original entry on oeis.org

0, 1, 6, 8, 3, 4, 9, 2, 5, 16, 7, 24, 32, 10, 21, 34, 13, 18, 37, 64, 11, 20, 35, 12, 19, 36, 25, 66, 28, 33, 14, 17, 38, 65, 22, 40, 23, 72, 39, 80, 15, 48, 67, 60, 128, 26, 68, 27, 96, 29, 98, 129, 30, 97, 130, 41, 86, 136, 49, 78, 144, 42, 85, 138, 53, 74, 132, 43, 84, 139, 52, 75, 148, 99, 140, 51, 76, 147, 44, 83, 160, 31, 192, 45, 82, 141, 50, 77, 146, 101

Offset: 0

Scott R. Shannon, Feb 22 2025

In the first 100000 terms the fixed points are 0, 1, 28, 76, 543, 1580, although more likely exist.

			a(3) = 8 = 1000_2 as 8 is unused and a(2) = 6 = 110_2, and 1000_2 AND 110_2 = 0 while the binary weights of 8 and 6 are 1 and 2 respectively.

Scott R. Shannon, Table of n, a(n) for n = 0..10000

Cf. A000120, A129760, A061712, A057168, A381406.

A192020 Triangle read by rows: T(n,k) is the number of unordered pairs of nodes at distance k in the binomial tree of order n (1 <= k <= 2n-1; entries in row n are the coefficients of the corresponding Wiener polynomial).

Original entry on oeis.org

1, 3, 2, 1, 7, 8, 8, 4, 1, 15, 22, 31, 28, 17, 6, 1, 31, 52, 90, 112, 104, 68, 30, 8, 1, 63, 114, 225, 344, 418, 388, 270, 136, 47, 10, 1, 127, 240, 516, 908, 1331, 1568, 1464, 1064, 589, 240, 68, 12, 1, 255, 494, 1123, 2180, 3663, 5138, 5931, 5560, 4181, 2482, 1137, 388, 93, 14, 1

Offset: 0

Emeric Deutsch, Jun 22 2011

The binomial trees b(k) of order k are ordered trees defined as follows:
1. b(0) consists of a single node.
2. For k >= 1, b(k) is obtained from two copies of b(k-1) by linking them in such a way that the root of one is the leftmost child of the root of the other. See the Iyer & Reddy references.
Row n contains 2n-1 entries.
Kevin Ryde, Sep 14 2019: (Start)
In the formulas below, the generating function for number of vertices at depth is r(n,t) = (t+1)^n = Sum_{i=0..n} binomial(n,i)*t^i.  The w(n,t) recurrence applied repeatedly is a sum of those, and from which the rational function for w(n,t).
T(n,k) as sum over j follows from which binomials are put at which indices in the g.f.  Or the direct interpretation is to number vertices v=0 to 2^n-1 inclusive with parent(v) = A129760(v) in the usual way, then suppose a pair of vertices u,v have their highest differing bit at position j, where j=1 as the least significant bit.  One of u or v has a 1-bit at j.  To be distance k apart requires k-1 further 1-bits among the bits below j in u and v, hence binomial(2(j-1),k-1).  The bits above j are the same in u and v and can be any 2^(n-j) (those bits and 0's below are the common ancestor of u,v).
(End)

			T(2,1)=3, T(2,2)=2, T(2,3)=1 because the binomial tree b(2) is basically the path tree A-B-R-C and we have 3 (AB, BR, RC), 2 (AR, BC), and 1 (AC) pairs of nodes at distances 1, 2, and 3, respectively.
Triangle starts:
   1;
   3,   2,   1;
   7,   8,   8,   4,   1;
  15,  22,  31,  28,  17,   6,   1;
  31,  52,  90, 112, 104,  68,  30,   8,   1;

K. Viswanathan Iyer and K. R. Udaya Kumar Reddy, Wiener index of Binomial trees and Fibonacci trees, Int'l. J. Math. Engin. with Comp., Accepted for publication, Sept. 2009.
T. H. Cormen, C. E. Leiserson and R. L. Rivest: Introduction to Algorithms. MIT Press / McGraw-Hill (1990).

B. E. Sagan, Y-N. Yeh and P. Zhang, The Wiener Polynomial of a Graph, Internat. J. of Quantum Chem., 60, 1996, 959-969.
K. Viswanathan Iyer and K. R. Udaya Kumar Reddy, Wiener index of binomial trees and Fibonacci trees, arXiv:0910.4432 [cs.DM], 2009.

Cf. A000225, A005803, A192021.

G := 1/(1-z-t*z): Gser := simplify(series(G, z = 0, 11)): for n from 0 to 8 do r[n] := sort(coeff(Gser, z, n)) end do: w[0] := 0: for n to 8 do w[n] := sort(expand(2*w[n-1]+t*r[n-1]^2)) end do: for n to 8 do seq(coeff(w[n], t, k), k = 1 .. 2*n-1) end do; # yields sequence in triangular form

max = 8; g = 1/(1 - z - t*z); r = CoefficientList[ Series[g, {z, 0, max}], z]; w[0] = 0; w[n_] := w[n] = 2 w[n-1] + t*r[[n]]^2; Flatten[ Table[ Drop[ CoefficientList[ w[n], t], 1], {n, 1, max}]] (* Jean-François Alcover, Oct 06 2011, after Maple *)

a(n) = my(s=sqrtint(n),r=n-s^2); sum(i=0,s, 2^(s-i)*binomial(2*i,r)); \\ Kevin Ryde, Sep 13 2019

T(n,1) = A000225(n) = 2^n - 1.
T(n,2) = A005803(n+1) = 2^(n+1) - 2*n - 2.
Sum_{k>=1} k*T(n,k) = A192021(n) (the Wiener indices).
The Wiener polynomial w(n,t) of the binomial tree of order n satisfies the recurrence relation w(n,t) = 2*w(n-1,t) + t*(r(n-1,t))^2, w(0,t)=0, where r(n,t) is the generating polynomial of the nodes of the binomial tree b(n) with respect to the level of the nodes (for example, r(1,t) = 1 + t for the one-edge tree b(1)= | ; see the Maple program).
T(n,k) = Sum_{j=1..n} 2^(n-j)*binomial(2*j-2, k-1).
w(n,t) = Sum_{i=0..n-1} 2^(n-1-i)*t*(t+1)^(2i) = t * ((t+1)^(2n) - 2^n)/((t+1)^2 - 2). - Kevin Ryde, Sep 13 2019

A343934 Irregular triangle read by rows: row n gives the sequence of iterations of k - A006519(k), starting with k=n, until 0 is reached.

Original entry on oeis.org

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

Offset: 1

Christian Perfect, May 04 2021

Row n starts with n, then the highest power of 2 dividing n is subtracted to produce the next entry in the row.

n first appears at position A000788(n)+1.

			The triangle begins
1
2
3 2
4
5 4
6 4
7 6 4

Peter Kagey, Rows n = 1..1023, flattened

Cf. A000120 (row widths), A000788, A006519, A129760, A298011 (row sums).

Table[Most @ NestWhileList[# - 2^IntegerExponent[#, 2] &, n, # > 0 &], {n, 1, 30}] // Flatten (* Amiram Eldar, May 05 2021 *)

def gen_a():
    for n in range(1,100):
        k = n
        while k>0:
            yield k
            k = k & (k-1)
a = gen_a()

A355413 Lexicographically earliest infinite sequence of positive numbers such that, for n>1, a(n) AND a(n-1) is distinct from all previous AND operations between adjacent terms, where AND is the binary AND operator.

Original entry on oeis.org

0, 1, 3, 3, 6, 5, 7, 7, 14, 9, 11, 11, 14, 13, 15, 15, 30, 17, 19, 19, 22, 21, 23, 23, 30, 25, 27, 27, 30, 29, 31, 31, 62, 33, 35, 35, 38, 37, 39, 39, 46, 41, 43, 43, 46, 45, 47, 47, 62, 49, 51, 51, 54, 53, 55, 55, 62, 57, 59, 59, 62, 61, 63, 63, 126, 65, 67, 67, 70, 69, 71, 71, 78, 73, 75, 75

Offset: 0

Scott R. Shannon, Jul 01 2022

Each term must be chosen so that a subsequent term can always been found. This implies, for example, no power of 2 can ever be a term as the result of an AND operation between such a number and any following number will be either 0 or the power of 2, both of which have already appeared as the result of AND operations.

Every a(n) where n is odd is a fixed point.

			a(3) = 3 as a(2) = 3 and 3 AND 3 = 3, which has not occurred earlier for any AND's between adjacent terms. Note that a(3) cannot equal 2 = 10_2 as the result of any subsequent AND operation with 2 would be 0 or 2, both of which have already occurred.

Scott R. Shannon, Line graph of the first 100000 terms.

Cf. A007088, A129760, A338824.

cp's OEIS Frontend

A353245 a(n) = A353989(n) AND A353989(n+1), where AND is the binary AND operator.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A348648 Triangle T(n, k), n >= 0, 0 <= k <= n, read by rows; the even terms of Pascal's triangle (A007318) are clustered as wXwXw subtriangles with w = 2^s-1 for some s > 0; if A007318(n, k) is even then T(n, k) gives the corresponding s otherwise T(n, k) = 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A352729 The binary expansion of a(n) contains the runs of consecutive 1's that appear both in the binary expansions of n and n+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A355621 a(1) = 1; for n > 1, a(n) is the number of terms in the first n-1 terms of the sequence that share a 1-bit with a(n-1) in their binary expansions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

A355625 a(1) = 1; for n > 1, a(n) is the number of terms in the first n-1 terms of the sequence that share a 1-bit with n in their binary expansions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

A381405 a(0) = 0; for n > 0, a(n) is the smallest unused number such that a(n) AND a(n-1) = 0, where AND is the binary AND operation, while the binary weight of a(n) does not equal that of a(n-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A192020 Triangle read by rows: T(n,k) is the number of unordered pairs of nodes at distance k in the binomial tree of order n (1 <= k <= 2n-1; entries in row n are the coefficients of the corresponding Wiener polynomial).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A343934 Irregular triangle read by rows: row n gives the sequence of iterations of k - A006519(k), starting with k=n, until 0 is reached.

Views

Author

Keywords

Comments

Examples

Links