A385674 Triangle read by rows: T(n,n) = 1 and T(n,k) = (T(n-1,k) | T(n-2,k) | ... | T(n-k,k)) + 1, where | is bitwise OR, (0<=k<=n).

1, 1, 1, 1, 2, 1, 1, 3, 2, 1, 1, 4, 4, 2, 1, 1, 5, 7, 4, 2, 1, 1, 6, 8, 8, 4, 2, 1, 1, 7, 16, 15, 8, 4, 2, 1, 1, 8, 25, 16, 16, 8, 4, 2, 1, 1, 9, 26, 32, 31, 16, 8, 4, 2, 1, 1, 10, 28, 64, 32, 32, 16, 8, 4, 2, 1, 1, 11, 31, 113, 64, 63, 32, 16, 8, 4, 2, 1, 1, 12, 32, 114, 128, 64, 64, 32, 16, 8, 4, 2, 1

Offset: 0

Author

Natalia L. Skirrow, Aug 04 2025

Keywords

• nonn
• tabl
• new

Comments

For the purposes of the recurrence, the region of the array above the triangle is filled with 0's.

In the cellular automaton, on binary representations, that starts with s = 2^n-1 on iteration t=0, then each iteration sets s := s XOR (s<<1 AND s<<2 AND ... AND s<

With respect to n, T(n,k) is in Theta(n^k); this corresponds with the k-th cellular automaton growing with width Theta(t^(1/k)).

Rows are not always unimodal! Row 18 (1 < 18 < 104 < 512 > 496 < 1986 < 2048 > 1024 > 512 = 512 > 256 > 128 > 64 > 32 > 16 > 8 > 4 > 2 > 1) is the first exception.

Examples

			Table begins
  n\k| 0  1  2   3   4   5   6   7   8  9 10 11 12 13 14 15
  ---+-----------------------------------------------------
   0 | 1
   1 | 1  1
   2 | 1  2  1
   3 | 1  3  2   1
   4 | 1  4  4   2   1
   5 | 1  5  7   4   2   1
   6 | 1  6  8   8   4   2   1
   7 | 1  7 16  15   8   4   2   1
   8 | 1  8 25  16  16   8   4   2   1
   9 | 1  9 26  32  31  16   8   4   2  1
  10 | 1 10 28  64  32  32  16   8   4  2  1
  11 | 1 11 31 113  64  63  32  16   8  4  2  1
  12 | 1 12 32 114 128  64  64  32  16  8  4  2  1
  13 | 1 13 64 116 256 128 127  64  32 16  8  4  2  1
  14 | 1 14 97 120 481 256 128 128  64 32 16  8  4  2  1
  15 | 1 15 98 127 482 512 256 255 128 64 32 16  8  4  2  1
Binary expansions of the k=2 column:
  . . . . . . . . . . . . 11111111111111111111111
  . . . . . . . . . . . .1 1111111111111111111111
  . . . . . . 11111111111 . . . . . . 11111111111
  . . . . . .1 1111111111 . . . . . .1 1111111111
  . . . 11111 . . . 11111 . . . 11111 . . . 11111
  . . .1 1111 . . .1 1111 . . .1 1111 . . .1 1111
  . .11 . .11 . .11 . .11 . .11 . .11 . .11 . .11
  . 1 1 . 1 1 . 1 1 . 1 1 . 1 1 . 1 1 . 1 1 . 1 1
  .1 .1 .1 .1 .1 .1 .1 .1 .1 .1 .1 .1 .1 .1 .1 .1
The recurrence emulates binary counting, albeit with k X k 'metabits' in this diagram; the bit being  carried to is filled along the diagonal, followed by a single number in which all metabits are full and the 0th bit is on.
		

Links

• Paolo Xausa, Table of n, a(n) for n = 0..11475 (rows 0..150 of triangle, flattened).
• Natalia L. Skirrow, on nearsighted binary counters, theorems 1 and 2 (in which T(k,n) is written as the function o(k) for the n-th cellular automaton).

Crossrefs

Cf. A338888 (column k=2).

Programs

Mathematica

A351995[n_, k_] := If[n <= 1, n, Total[2^(k*(Flatten[Position[Reverse[IntegerDigits[n, 2]], 1]] - 1))]];
A385674[n_, k_] := 2*(2^k - 1)*A351995[#[[1]], k] + If[#[[2]] == k, 1, 2*2^(k*IntegerExponent[#[[1]], 2])*(1 + 2^#[[2]] - 2^k)] & [QuotientRemainder[n, k + 1]];
Table[A385674[n, k], {n, 0, 15}, {k, 0, n}] (* Paolo Xausa, Sep 04 2025 *)

PARI

lista(nn) = my(m=matrix(nn, nn)); for (n=1, nn, m[n,n] = 1; for (k=1, n-1, for (i=1, k-1, m[n,k] = bitor(m[n,k], m[n-i,k]);); m[n,k]++;);); my(vrows=vector(nn, i, vector(i, k, m[i,k]))); vrows; \\ Michel Marcus, Aug 04 2025

Python

from functools import reduce
ORsum=lambda l: reduce(int._or_,l,0)
A351995=lambda n,k: ORsum(map(lambda i: (n>>i&1)<<(i*k),range(n.bit_length()))) if k else n.bit_count()
T=lambda n,k: 2*~(~0<A351995(d:=n//(k+1),k)+((r:=n%(k+1))==k or (d&-d)**k*2*(1+2**r-2**k))
#corollary 1:
T=lambda n,k: T(n-(k+1<<(l:=(d:=n//(k+1)).bit_length()-1)),k)|(~(~0<k else int(n==k)
bit=lambda n,k,i: (i%k==n%(k+1) if n%(k+1)>i//k&1) if i else n%(k+1)==k #returns i-th bit of T(n,k)

Formula

Let d = floor(n/(k+1)) and m = n mod (k+1), then

T(n,k) = 2 * (2^k-1) * A351995(d,k) + b(n,k) where b(n,k) = 1 if n==k (mod k+1), otherwise b(n,k) = 2*2^(k*val_2(d))*(1+2^m-2^k).

Bounds: 2*(n/(k+1))^k <= T(n,k) <= 2*(2^k-1) * ((n-k)/(k+1))^k+1, with upper equality when n is of form 2^(k*i+1) and lower when n is of form (2^k-1)*2^(k*i+1).

T(n,k) = T(n-(k+1)*2^floor(log_2(d)),k) + 2^(k*floor(log_2(d))+1)*(if d is a power of 2 and m != k then 2^m, else 2^k-1).

O.g.f. for k-th column: 2*(2^k-1) * (Sum_{i>=0} 2^(k*i) * x^((k+1)*2^i) / (1+x^((k+1)*2^i))) / (1-x) + x^k / (1-x^(k+1)) + 2 * ((1-2^k) * (1-x^k)/(1-x) + (1-(2*x)^k)/(1-2*x)) * Sum_{i>=0} 2^(k*i) * x^((k+1)*2^i) / (1-x^((k+1)*2^(i+1))).

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.