A092339 -id:A092339 - cp's OEIS frontend

A361674 Irregular triangle T(n, k), n >= 0, k = 1..2^A092339(n), read by rows; the n-th row lists the numbers k such that n appears in the k-th row of A361644.

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

Offset: 0

Rémy Sigrist, Mar 20 2023

In other words, the n-th row contains the numbers k with the same binary length as n and for any i >= 0, if the i-th bit and the (i+1)-th bit in n are different then they are also different in k (i = 0 corresponding to the least significant bit).

			Triangle T(n, k) begins (in decimal and in binary):
  n   n-th row        bin(n)  n-th row in binary
  --  --------------  ------  ----------------------
   0  0                    0  0
   1  1                    1  1
   2  2                   10  10
   3  2, 3                11  10, 11
   4  4, 5               100  100, 101
   5  5                  101  101
   6  5, 6               110  101, 110
   7  4, 5, 6, 7         111  100, 101, 110, 111
   8  8, 9, 10, 11      1000  1000, 1001, 1010, 1011
   9  9, 10             1001  1001, 1010
  10  10                1010  1010
  11  10, 11            1011  1010, 1011
  12  10, 11, 12, 13    1100  1010, 1011, 1100, 1101
  13  10, 13            1101  1010, 1101
  14  9, 10, 13, 14     1110  1001, 1010, 1101, 1110

Rémy Sigrist, Table of n, a(n) for n = 0..9841 (rows for n = 0..511 flattened)

Cf. A361644, A361645, A361676.

row(n) = { my (r = [n], m); for (e = 1, exponent(n), if (bittest(n, e-1)==bittest(n, e), m = 2^e-1; r = concat(r, [bitxor(v, m) | v <- r]););); vecsort(r); }

T(n, 1) = A361645(n).

T(n, 2^A092339(n)) = A361676(n).

A080791 Number of nonleading 0's in binary expansion of n.

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 1, 0, 3, 2, 2, 1, 2, 1, 1, 0, 4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0, 5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1, 4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0, 6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2, 5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1, 5, 4, 4, 3, 4, 3, 3, 2, 4

Offset: 0

Cino Hilliard, Mar 25 2003

In this version we consider the number zero to have no nonleading 0's, thus a(0) = 0. The variant A023416 has a(0) = 1.

Number of steps required to reach 1, starting at n + 1, under the operation: if x is even divide by 2 else add 1. This is the x + 1 problem (as opposed to the 3x + 1 problem).

			a(4) = 2 since 4 in binary is 100, which has two zeros.
a(5) = 1 since 5 in binary is 101, which has only one zero.

N. J. A. Sloane, Table of n, a(n) for n = 0..10000
Index entries for sequences related to binary expansion of n

Cf. A000120, A007814, A023416, A029837, A036987, A080791-A080801, A048881, A054429, A092339, A102364, A120511, A233271, A233272, A233273.

seq(numboccur(0, Bits[Split](n)), n=0..100); # Robert Israel, Oct 26 2017

{0}~Join~Table[Last@ DigitCount[n, 2], {n, 120}] (* Michael De Vlieger, Mar 07 2016 *)
f[n_] := If[OddQ@ n, f[n -1] -1, f[n/2] +1]; f[0] = f[1] = 0; Array[f, 105, 0] (* Robert G. Wilson v, May 21 2017 *)
Join[{0}, Table[Count[IntegerDigits[n, 2], 0], {n, 1, 100}]] (* Vincenzo Librandi, Oct 27 2017 *)

PARI
```
a(n)=if(n,a(n\2)+1-n%2)
```

A080791(n)=if(n,logint(n,2)+1-hammingweight(n)) \\ M. F. Hasler, Oct 26 2017

def a(n): return bin(n)[2:].count("0") if n>0 else 0 # Indranil Ghosh, Apr 10 2017

;; with memoizing definec-macro from Antti Karttunen's IntSeq-library)
(define (A080791 n) (- (A029837 (+ 1 n)) (A000120 n)))
;; Alternative version based on a simple recurrence:
(definec (A080791 n) (if (zero? n) 0 (+ (A080791 (- n 1)) (A007814 n) (A036987 (- n 1)) -1)))
;; from Antti Karttunen, Dec 12 2013

From Antti Karttunen, Dec 12 2013: (Start)
a(n) = A029837(n+1) - A000120(n).
a(0) = 0, and for n > 0, a(n) = (a(n-1) + A007814(n) + A036987(n-1)) - 1.
For all n >= 1, a(A054429(n)) = A048881(n-1) = A000120(n) - 1.
Equally, for all n >= 1, a(n) = A000120(A054429(n)) - 1.
(End)
Recurrence: a(2n) = a(n) + 1 (for n > 0), a(2n + 1) = a(n). - Ralf Stephan from Cino Hilliard's PARI program, Dec 16 2013. Corrected by Alonso del Arte, May 21 2017 after consultation with Chai Wah Wu and Ray Chandler, "n > 0" added by M. F. Hasler, Oct 26 2017
a(n) = A023416(n) for all n > 0. - M. F. Hasler, Oct 26 2017
G.f. g(x) satisfies g(x) = (1+x)*g(x^2) + x^2/(1-x^2). - Robert Israel, Oct 26 2017

A227185 The largest part in the unordered partition encoded in the runlengths of the binary expansion of n.

Original entry on oeis.org

0, 1, 1, 2, 2, 1, 2, 3, 3, 2, 1, 2, 3, 2, 3, 4, 4, 3, 2, 3, 2, 1, 2, 3, 4, 3, 2, 3, 4, 3, 4, 5, 5, 4, 3, 4, 3, 2, 3, 4, 3, 2, 1, 2, 3, 2, 3, 4, 5, 4, 3, 4, 3, 2, 3, 4, 5, 4, 3, 4, 5, 4, 5, 6, 6, 5, 4, 5, 4, 3, 4, 5, 4, 3, 2, 3, 4, 3, 4, 5, 4, 3, 2, 3, 2, 1, 2

Offset: 0

Antti Karttunen, Jul 05 2013

The bijective encoding of nonordered partitions via compositions (ordered partitions) present in the binary expansion of n is explained in A227184.

It appears that a(4n+2) = a(2n+1). - Ralf Stephan, Jul 20 2013

			12 has binary expansion "1100", for which the lengths of runs (consecutive blocks of 0- or 1-bits) are [2,2]. Converting this to a partition in the manner explained in A227184 gives the partition {2+3}. Its largest part is 3, thus a(12)=3, which is actually the first time when this sequence differs from A043276.

Antti Karttunen, Table of n, a(n) for n = 0..8192

For all n, A005811(n) = a(A129594(n)). Cf. also A136480 (for n>= 1, gives the smallest part) and A227183, A227184, A226062, A092339, A227147.

a(n) gives the rightmost nonzero term on the n-th row of A227189.

Table[Function[b, Max@ Accumulate@ Prepend[If[Length@ b > 1, Rest[b] - 1, {}], First@ b] - Boole[n == 0]]@ Map[Length, Split@ Reverse@ IntegerDigits[ n, 2]], {n, 0, 120}] // Flatten (* Michael De Vlieger, May 09 2017 *)

(define (A227185 n) (if (zero? n) n (+ 1 (- (A029837 (+ 1 n)) (A005811 n)))))
(define (A227185v2 n) (if (zero? n) n (car (reverse (binexp_to_ascpart n))))) ;; Alternative definition, using the auxiliary functions given in A227184.

Defining formula:
a(0)=0; and for n>=1, a(n) = A029837(n+1) - (A005811(n)-1). [Because the largest part in the unordered partition in this encoding scheme is computed as (c_1 + (c_2-1) + (c_3-1) + ... + (c_k-1)) where c_1 .. c_k are the parts of the k-part composition that sum together as c_1 + c_2 + ... + c_k = A029837(n+1) (the binary width of n), so we subtract from the total binary width of n the number of runs (A005811) minus 1.]
Equivalently: a(n) = A092339(n)+1 for n>0.
a(n) = A005811(A129594(n)). [This just states the fact that when conjugating a partition, the largest part of an old partition will be the number of the parts in the new, conjugated partition.]

A278217 Filter-sequence related to base-2 run-length encoding: a(n) = A046523(A075159(1+n)) = A046523(1+A075157(n)).

Original entry on oeis.org

1, 2, 2, 4, 6, 2, 4, 8, 12, 6, 2, 6, 12, 4, 8, 16, 24, 12, 6, 30, 6, 2, 6, 12, 36, 12, 4, 12, 24, 8, 16, 32, 48, 24, 12, 60, 30, 6, 30, 60, 12, 6, 2, 6, 30, 6, 12, 24, 72, 36, 12, 60, 12, 4, 12, 36, 72, 24, 8, 24, 48, 16, 32, 64, 96, 48, 24, 120, 60, 12, 60, 180, 60, 30, 6, 30, 210, 30, 60, 120, 24, 12, 6, 30, 6, 2, 6, 12, 60, 30, 6, 30, 60, 12, 24, 48, 144, 72

Offset: 0

Antti Karttunen, Nov 16 2016

nonn

Antti Karttunen, Table of n, a(n) for n = 0..16384

Cf. A046523, A075157, A075159, A286617 (rgs-version of this filter).
Other base-2 related filter sequences: A278219, A278222.
Sequences that partition N into same or coarser equivalence classes are at least these: A092339, A227185.

A005811(n) = hammingweight(bitxor(n, n>>1));  \\ This function from Gheorghe Coserea, Sep 03 2015
A286468(n) = { my(p=((n+1)%2), i=0, m=1); while(n>0, if(((n%2)==p), m *= prime(i), p = (n%2); i = i+1); n = n\2); m };
A075157(n) = if(!n,n,(prime(A005811(n))*A286468(n))-1);
A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); };  \\ This function from Charles R Greathouse IV, Aug 17 2011
A278217(n) = A046523(1+A075157(n)); \\ From Antti Karttunen, May 17 2017

(define (A278217 n) (A046523 (+ 1 (A075157 n))))
(define (A278217 n) (A046523 (A075159 (+ 1 n))))

a(n) = A046523(1+A075157(n)) = A046523(A075159(1+n)).

A361644 Irregular triangle T(n, k), n >= 0, k = 1..max(1, 2^(A005811(n)-1)), read by rows; the n-th row lists the integers with the same binary length as n and whose partial sums of run lengths are included in those of n.

Original entry on oeis.org

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

Offset: 0

Rémy Sigrist, Mar 19 2023

In other words, the n-th row contains the numbers k with the same binary length as n and for any i >= 0, if the i-th bit and the (i+1)-th bit in k are different then they are also different in n (i = 0 corresponding to the least significant bit).

The value m appears 2^A092339(m) times in the triangle (see A361674).

			Triangle begins (in decimal and in binary):
  n   n-th row      bin(n)  n-th row in binary
  --  ------------  ------  ------------------
   0  0                  0  0
   1  1                  1  1
   2  2, 3              10  10, 11
   3  3                 11  11
   4  4, 7             100  100, 111
   5  4, 5, 6, 7       101  100, 101, 110, 111
   6  6, 7             110  110, 111
   7  7                111  111
   8  8, 15           1000  1000, 1111
   9  8, 9, 14, 15    1001  1000, 1001, 1110, 1111
.
For n = 9:
- the binary expansion of 9 is "1001",
- the corresponding run lengths are 1, 2, 1,
- so the 9th row contains the values with the following run lengths:
      1, 2, 1  ->   9 ("1001" in binary)
      1,  2+1  ->   8 ("1000" in binary)
      1+2,  1  ->  14 ("1110" in binary)
       1+2+1   ->  15 ("1111" in binary)

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

Cf. A003817, A005811, A092339, A101211, A225081, A342126, A361645, A361646, A361674, A361676.

row(n) = { my (r = []); while (n, my (v = valuation(n+n%2, 2)); n \= 2^v; r = concat(v, r)); my (s = [if (#r, 2^r[1]-1, 0)]); for (k = 2, #r, s = concat(s * 2^r[k], [(h+1)*2^r[k]-1|h<-s]);); vecsort(s); }

T(n, 1) = A342126(n).

T(n, max(1, 2^(A005811(n)-1))) = A003817(n).

A320042 a(n) = a(floor(n/2)) + (-1)^(n*(n+1)/2) with a(1)=0.

Original entry on oeis.org

0, -1, 1, 0, -2, 0, 2, 1, -1, -3, -1, 1, -1, 1, 3, 2, 0, -2, 0, -2, -4, -2, 0, 2, 0, -2, 0, 2, 0, 2, 4, 3, 1, -1, 1, -1, -3, -1, 1, -1, -3, -5, -3, -1, -3, -1, 1, 3, 1, -1, 1, -1, -3, -1, 1, 3, 1, -1, 1, 3, 1, 3, 5, 4, 2, 0, 2, 0, -2, 0, 2, 0, -2, -4, -2, 0, -2, 0, 2, 0

Offset: 1

Jinyuan Wang, Oct 03 2018

For 2^(2*k-1) - 1 < n < 2^(2*k), k>0, there's no n such that a(n)=0.

For 2^(2*k) - 1 < n < 2^(2*k+1), k>0, there are A000984(k+1) n's such that a(n)=0.

			a(9) = a(4) + (-1)^45 = -1, a(10) = a(5) + (-1)^55 = -3.
For 7 < n < 16, there's no n such that a(n)=0; for 15 < n < 32, there are 6 n's such that a(n)=0.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A000523, A000984, A007088, A092339.

a:=proc(n) `if`(n=1,0,a(floor(n/2))+(-1)^(n*(n+1)/2)) end: seq(a(n),n=1..100); # Muniru A Asiru, Oct 07 2018

a[1] = 0; a[n_] := a[n] = a[Floor[n/2]] + (-1)^(n*(n + 1)/2); Table[a@n, {n, 1, 50}]

a(n) = if (n==1, 0, a(n\2) + (-1)^(n*(n+1)/2)); \\ Michel Marcus, Oct 05 2018

a(1) = 0, a(n) = a(floor(n/2)) + (-1)^(n*(n+1)/2).

a(n) = 2*A092339(n+1) - A000523(n).

More terms from Michel Marcus, Oct 05 2018

cp's OEIS Frontend

A361674 Irregular triangle T(n, k), n >= 0, k = 1..2^A092339(n), read by rows; the n-th row lists the numbers k such that n appears in the k-th row of A361644.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A080791 Number of nonleading 0's in binary expansion of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Scheme

Formula

A227185 The largest part in the unordered partition encoded in the runlengths of the binary expansion of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

A278217 Filter-sequence related to base-2 run-length encoding: a(n) = A046523(A075159(1+n)) = A046523(1+A075157(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Scheme

Formula

A361644 Irregular triangle T(n, k), n >= 0, k = 1..max(1, 2^(A005811(n)-1)), read by rows; the n-th row lists the integers with the same binary length as n and whose partial sums of run lengths are included in those of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A320042 a(n) = a(floor(n/2)) + (-1)^(n*(n+1)/2) with a(1)=0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions