cp's OEIS Frontend

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).

%I A385674 #36 Sep 04 2025 08:35:52
%S A385674 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,
%T A385674 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,
%U A385674 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
%N 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).
%C A385674 For the purposes of the recurrence, the region of the array above the triangle is filled with 0's.
%C A385674 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<<k), T(n,k) is the first t at which the n-th bit (representing 2^n) of s is turned on. In fact, the n-th bit is on iff t contains 1-bits in a superset of T(n,k)'s positions.
%C A385674 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)).
%C A385674 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.
%H A385674 Paolo Xausa, <a href="/A385674/b385674.txt">Table of n, a(n) for n = 0..11475</a> (rows 0..150 of triangle, flattened).
%H A385674 Natalia L. Skirrow, <a href="/wiki/User:Natalia_L._Skirrow/on_nearsighted_binary_counters">on nearsighted binary counters</a>, theorems 1 and 2 (in which T(k,n) is written as the function o(k) for the n-th cellular automaton).
%F A385674 Let d = floor(n/(k+1)) and m = n mod (k+1), then
%F A385674 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).
%F A385674 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).
%F A385674 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).
%F A385674 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))).
%e A385674 Table begins
%e A385674   n\k| 0  1  2   3   4   5   6   7   8  9 10 11 12 13 14 15
%e A385674   ---+-----------------------------------------------------
%e A385674    0 | 1
%e A385674    1 | 1  1
%e A385674    2 | 1  2  1
%e A385674    3 | 1  3  2   1
%e A385674    4 | 1  4  4   2   1
%e A385674    5 | 1  5  7   4   2   1
%e A385674    6 | 1  6  8   8   4   2   1
%e A385674    7 | 1  7 16  15   8   4   2   1
%e A385674    8 | 1  8 25  16  16   8   4   2   1
%e A385674    9 | 1  9 26  32  31  16   8   4   2  1
%e A385674   10 | 1 10 28  64  32  32  16   8   4  2  1
%e A385674   11 | 1 11 31 113  64  63  32  16   8  4  2  1
%e A385674   12 | 1 12 32 114 128  64  64  32  16  8  4  2  1
%e A385674   13 | 1 13 64 116 256 128 127  64  32 16  8  4  2  1
%e A385674   14 | 1 14 97 120 481 256 128 128  64 32 16  8  4  2  1
%e A385674   15 | 1 15 98 127 482 512 256 255 128 64 32 16  8  4  2  1
%e A385674 Binary expansions of the k=2 column:
%e A385674   . . . . . . . . . . . . 11111111111111111111111
%e A385674   . . . . . . . . . . . .1 1111111111111111111111
%e A385674   . . . . . . 11111111111 . . . . . . 11111111111
%e A385674   . . . . . .1 1111111111 . . . . . .1 1111111111
%e A385674   . . . 11111 . . . 11111 . . . 11111 . . . 11111
%e A385674   . . .1 1111 . . .1 1111 . . .1 1111 . . .1 1111
%e A385674   . .11 . .11 . .11 . .11 . .11 . .11 . .11 . .11
%e A385674   . 1 1 . 1 1 . 1 1 . 1 1 . 1 1 . 1 1 . 1 1 . 1 1
%e A385674   .1 .1 .1 .1 .1 .1 .1 .1 .1 .1 .1 .1 .1 .1 .1 .1
%e A385674 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.
%t A385674 A351995[n_, k_] := If[n <= 1, n, Total[2^(k*(Flatten[Position[Reverse[IntegerDigits[n, 2]], 1]] - 1))]];
%t A385674 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]];
%t A385674 Table[A385674[n, k], {n, 0, 15}, {k, 0, n}] (* _Paolo Xausa_, Sep 04 2025 *)
%o A385674 (Python)
%o A385674 from functools import reduce
%o A385674 ORsum=lambda l: reduce(int.__or__,l,0)
%o A385674 A351995=lambda n,k: ORsum(map(lambda i: (n>>i&1)<<(i*k),range(n.bit_length()))) if k else n.bit_count()
%o A385674 T=lambda n,k: 2*~(~0<<k)*A351995(d:=n//(k+1),k)+((r:=n%(k+1))==k or (d&-d)**k*2*(1+2**r-2**k))
%o A385674 #corollary 1:
%o A385674 T=lambda n,k: T(n-(k+1<<(l:=(d:=n//(k+1)).bit_length()-1)),k)|(~(~0<<k) if d&d-1 or (r:=n%(k+1))==k else 1<<r)<<l*k+1 if n>k else int(n==k)
%o A385674 bit=lambda n,k,i: (i%k==n%(k+1) if n%(k+1)<k and i//k==((d:=n//(k+1))&-d).bit_length()-1 else d>>i//k&1) if i else n%(k+1)==k #returns i-th bit of T(n,k)
%o A385674 (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
%Y A385674 Cf. A338888 (column k=2).
%K A385674 nonn,tabl,new
%O A385674 0,5
%A A385674 _Natalia L. Skirrow_, Aug 04 2025