A197819 -id:A197819 - cp's OEIS frontend

A358167 Irregular triangle read by rows: T(n, k) = k-th fixed point in Zhegalkin permutation n (row n of A197819).

0, 1, 0, 2, 0, 6, 8, 14, 0, 30, 40, 54, 72, 86, 96, 126, 128, 158, 168, 182, 200, 214, 224, 254, 0, 510, 680, 854, 1224, 1334, 1632, 1950, 2176, 2430, 2600, 3030, 3144, 3510, 3808, 3870, 4320, 4382, 4680, 5046, 5160

Offset: 0

Tilman Piesk, Nov 01 2022

Let R = A197819(n, ...) and F = a(n, ...). Then F are the fixed points of R.
But there is a second relationship between F and R:
  Let X(i) = R(i) XOR i. Then X(i) is an element of F.
  Let I_k = {i | X(i) = F(k)}. Let Q = A197819(n-1, ...).
  Then I_k = {Q(k) XOR f | f in F}.
Row lengths are 2, 2, 4, 16, 256, 65536, ..., i.e., A001146(n-1) for n > 0.
Row sums are 1, 2, 28, 2032, 8388352, ..., i.e., A147537(A000225) for n > 0.

			Triangle begins:
     k  0    1    2   3    4   5   6    7    8    9   10   11   12   13   14   15
  n
  0     0,   1
  1     0,   2
  2     0,   6,   8, 14
  3     0,  30,  40, 54,  72, 86, 96, 126, 128, 158, 168, 182, 200, 214, 224, 254
  4     0, 510, 680...
A197819(3, 168) = a(3, 10) = 168.
How to calculate the term for n=3, k=10:
  p = A197819(n-1, k) = A197819(2, 10) = 2
  p XOR k = 2 XOR 10 = 8
  shifted_k = 2^(2^(n-1)) * k = 2^(2^2) * 10 = 160
  (p XOR k) + shifted_k = 8 + 160 = 168
168 in little-endian binary is 00010101. The corresponding algebraic normal form is XOR(AND(x0, x1), AND(x0, x2), AND(x0, x1, x2)). (Its ANDs correspond to the 3 binary 1s.) The truth table of this Boolean function is again 00010101.
  (With x0 = 01010101, x1 = 00110011, x2 = 00001111.)
Example for the second relationship with A197819, as described in COMMENTS:
  Let R = A197819(3, 0..255), F = a(3, 0..15), Q = A197819(2, 0..15).
  I_3 = {i | R(i) XOR i = F(3)}
      = {Q(3) XOR f | f in F} = {5 XOR f | f in F}
      = {5, 27, 45, 51, 77, 83, 101, 123, 133, 155, 173, 179, 205, 211, 229, 251}
  R(5) XOR 5  =  R(27) XOR 27  =  R(45) XOR 45  =  R(51) XOR 51  =  ...  =  F(3)
   51  XOR 5  =    45  XOR 27  =    27  XOR 45  =     5  XOR 51  =  ...  =   54

Tilman Piesk, Rows 0..4 of the triangle, flattened
Tilman Piesk, row 3 and row 4 as binary matrices, row 3 as part of the permutation
Tilman Piesk, Zhegalkin matrix (Wikiversity)

Cf. A197819, A001146, A147537, A000225, A058891.

def a(n, k):
    if n == 0:
        assert k < 2
        return k
    else:
        row_length = 1 << (1 << (n-1))  # 2 ** 2 ** (n-1)
        assert k < row_length
    p = a197819(n-1, k)
    p_xor_k = p ^ k
    shifted_k = row_length * k
    return p_xor_k + shifted_k

For n>0: T(n, k) = [A197819(n-1, k) XOR k] + [2^(2^(n-1)) * k].
  (On this page "XOR" always is the bitwise exclusive or.)
For n>0: T(n, A058891(n)) = A058891(n+1) is the unique power of 2 in row n.

A195467 Consecutive powers of the Gray code permutation.

Original entry on oeis.org

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

Offset: 0

Tilman Piesk, Sep 23 2011

The powers of the Gray code permutation (GCP, A003188) form an infinite array, where row n is the n-th power of the GCP. Row 0 is the identity permutation (i.e., the sequence of nonnegative integers), and row 1 is the GCP itself.
The different powers of the n-bit GCP form a matrix of size (A062383(n-1)) X (2^n).
This sequence represents the infinite array in a somewhat redundant way: It shows the rows of all the (2^n) X (2^2^n) matrices of powers of (2^n)-bit GCP. So this sequence forms a triangle, and these 3 matrices are its first 7 rows:
The 1-bit GCP is the identity permutation:
0:   0  1
The 2 different powers of the 2-bit GCP:
0:   0  1  2  3
1:   0  1  3  2
The 4 different powers of the 4-bit GCP:
0:   0  1  2  3   4  5  6  7   8  9 10 11  12 13 14 15
1:   0  1  3  2   6  7  5  4  12 13 15 14  10 11  9  8
2:   0  1  2  3   5  4  7  6  10 11  8  9  15 14 13 12
3:   0  1  3  2   7  6  4  5  15 14 12 13   8  9 11 10
.
This array A can be defined using the binary array B = A197819 by
A  =  B + 2 * 2stretched(B) + 4 * 4stretched(B) + 8 * 8stretched(B) + ...
where nstretched has the following meaning:
2stretched(1,2,3,4,...) = 1,1,2,2,3,3,4,4,...
4stretched(1,2,3,4,...) = 1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,...
etc.

Tilman Piesk, First 15 rows of the triangle, flattened
Tilman Piesk, Explanations (including the 8x256 submatrix) and MATLAB code showing the connection with A197819
Tilman Piesk, The 8 different powers of the 6-bit Gray code permutation
Tilman Piesk, Gray code permutation powers (Wikiversity)

Cf. A003188 (Gray code permutation).
Cf. A006068 (inverse of the Gray code permutation).
Cf. A064706 (square of the Gray code permutation).
Cf. A197819 (this array mod 2).

Huge edit by Tilman Piesk, Aug 25 2013

A358126 Replace 2^k in binary expansion of n with 2^(2^k).

Original entry on oeis.org

0, 2, 4, 6, 16, 18, 20, 22, 256, 258, 260, 262, 272, 274, 276, 278, 65536, 65538, 65540, 65542, 65552, 65554, 65556, 65558, 65792, 65794, 65796, 65798, 65808, 65810, 65812, 65814, 4294967296, 4294967298, 4294967300

Offset: 0

Tilman Piesk, Oct 30 2022

Sums of distinct terms of A001146.
The name "ballooned integers" is proposed for this sequence.
a(n) is the index of the first occurrence of n in A253315.

			Let    n   =     25  =  1 +   8 +    16  =     2^0  +    2^3  +    2^4.
Then a(n)  =  65794  =  2 + 256 + 65536  =  2^(2^0) + 2^(2^3) + 2^(2^4).
The binary indices of n are {0, 3, 4}. Those of a(n) are {1, 8, 16}.

Tilman Piesk, Table of n, a(n) for n = 0..4095
Tilman Piesk, Boolean Walsh functions and corresponding balloons
Tilman Piesk, First 32 entries in little-endian binary

Cf. A253317, A001146, A060803, A133457, A197819, A228539, A253315.

a := proc(n) select(d -> d[2] <> 0, ListTools:-Enumerate(convert(n,base,2))):
add(2^(2^(%[j][1] - 1)), j = 1..nops(%)) end: seq(a(n), n = 0..34); # Peter Luschny, Oct 31 2022

a[n_] := Total[2^(2^Range[If[n == 0, 1, IntegerLength[n,2]] - 1, 0, -1]) * IntegerDigits[n, 2]]; Array[a, 35, 0] (* Amiram Eldar, Oct 31 2022 *)

a(n) = my(d=Vecrev(digits(n,2))); for (k=1, #d, d[k] *= 2^(2^(k-1))); vecsum(d); \\ Michel Marcus, Oct 31 2022

def a(n):
    binary_string = "{0:b}".format(n)[::-1]  # little-endian
    result = 0
    for i, binary_digit in enumerate(binary_string):
        if binary_digit == '1':
            result += 1 << (1 << i)  # 2 ** (2 ** i)
    return result

If n = Sum_{i=0..k} 2^s_i, then a(n) = Sum_{i=0..k} 2^(2^s_i).
a(n) = 2 * A253317(n+1).
a(2^n-1) = A060803(n-1) for n >= 1.
a(2^n) = A001146(n).
A197819[m, a(n)] = A228539[m, n]. (Compare link about Boolean Walsh functions.)

cp's OEIS Frontend

A358167 Irregular triangle read by rows: T(n, k) = k-th fixed point in Zhegalkin permutation n (row n of A197819).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

A195467 Consecutive powers of the Gray code permutation.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A358126 Replace 2^k in binary expansion of n with 2^(2^k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula