A122569 -id:A122569 - cp's OEIS frontend

A190939 Subgroups of nimber addition interpreted as binary numbers.

1, 3, 5, 9, 15, 17, 33, 51, 65, 85, 105, 129, 153, 165, 195, 255, 257, 513, 771, 1025, 1285, 1545, 2049, 2313, 2565, 3075, 3855, 4097, 4369, 4641, 5185, 6273, 8193, 8481, 8721, 9345, 10305, 12291, 13107, 15555, 16385, 16705, 17025, 17425, 18465, 20485, 21845

Offset: 0

Tilman Piesk, May 24 2011

Each subgroup {0,a,b,...} of nimber addition can be assigned an integer 1+2^a+2^b+...
These integers ordered by size give this sequence.
Without nimbers the sequence may be defined as follows:
The powerset af a set {0,...,n-1} with the symmetric difference as group operation forms the elementary abelian group (Z_2)^n.
The elements of the group can be numbered lexicographically from 0 to 2^n-1, with 0 representing the neutral element:
{}-->0 , {0}-->2^0=1 , {1}-->2^1=2 , {0,1}-->2^0+2^1=3 , ... , {0,...,n-1}-->2^n-1
So the subgroups of (Z_2)^n can be represented by subsets of {0,...,2^n-1}.
So each subgroup {0,a,b,...} of (Z_2)^n can be assigned an integer 1+2^a+2^b+...
For each (Z_2)^n there is a finite sequence of these numbers ordered by size, and it is the beginning of the finite sequence for (Z_2)^(n+1).
This leads to the infinite sequence:
* 1,     (1 until here for (Z_2)^0)
* 3,     (2 until here for (Z_2)^1)
* 5, 9, 15,     (5 until here for (Z_2)^2)
* 17, 33, 51, 65, 85, 105, 129, 153, 165, 195, 255, (16 until here for (Z_2)^3)
* 257, 513, 771, 1025, 1285, 1545, 2049, 2313, 2565, 3075, 3855, 4097, 4369, 4641, 5185, 6273, 8193, 8481, 8721, 9345, 10305, 12291, 13107, 15555, 16385, 16705, 17025, 17425, 18465, 20485, 21845, 23205, 24585, 26265, 26985, 32769, 33153, 33345, 33825, 34833, 36873, 38505, 39321, 40965, 42405, 43605, 49155, 50115, 52275, 61455, 65535,     (67 until here for (Z_2)^4)
* 65537, ...
The number of subgroups of (Z_2)^n is 1, 2, 5, 16, 67, 374, 2825, ... (A006116)
Comment from Tilman Piesk, Aug 27 2013: (Start)
Boolean functions correspond to integers, and belong to small equivalence classes (sec). So a sec can be seen as an infinite set of integers (represented in A227722 by the smallest one). Some secs contain only one odd integer. These unique odd integers, ordered by size, are shown in this sequence. (While the smallest integers from these secs are shown in A227963.)
(End)

			The 5 subgroups of the Klein four-group (Z_2)^2 and corresponding integers are:
{0      }     -->     2^0                     =   1
{0,1    }     -->     2^0 + 2^1               =   3
{0,  2  }     -->     2^0       + 2^2         =   5
{0,    3}     -->     2^0             + 2^3   =   9
{0,1,2,3}     -->     2^0 + 2^1 + 2^2 + 2^3   =  15

Tilman Piesk, Table of n, a(n) for n = 0..2824
Tilman Piesk, Graphical explanation of n, a(n), A227963(n) for n = 0..66
Tilman Piesk, 2825x64 submatrix of the corresponding binary array, corresponding Walsh spectra (human readable versions of these matrices)
Tilman Piesk, Subgroups of nimber addition (Wikiversity)

Cf. A227963 (the same small equivalence classes represented by entries of A227722)
Cf. A198260 (number of runs of ones in the binary strings)
Subsequences:
Cf. A051179 (2^2^n-1).
Cf. A083318 (2^n+1).
Cf. A001317 (rows of the Sierpinski triangle read like binary numbers).
Cf. A228540 (rows of negated binary Walsh matrices r.l.b.n.).
Cf. A122569 (negated iterations of the Thue-Morse sequence r.l.b.n.).

Offset changed to 0 by Tilman Piesk, Jan 25 2012

A228540 Rows of negated binary Walsh matrices interpreted as reverse binary numbers.

Original entry on oeis.org

1, 3, 1, 15, 5, 3, 9, 255, 85, 51, 153, 15, 165, 195, 105, 65535, 21845, 13107, 39321, 3855, 42405, 50115, 26985, 255, 43605, 52275, 26265, 61455, 23205, 15555, 38505, 4294967295, 1431655765, 858993459, 2576980377, 252645135, 2779096485, 3284386755

Offset: 0

Tilman Piesk, Aug 24 2013

T(n,k) is row k of the negated binary Walsh matrix of size 2^n read as reverse binary number. The left digit is always 1, so all entries are odd.
Most of these numbers are divisible by Fermat numbers (A000215): All entries in all rows beginning with row n are divisible by F_(n-1), except the entries 2^(n-1)...2^n-1. (This is the same in A228539.)
Divisibility by Fermat numbers:
All entries in rows n >= 1 are divisible by F_0 =  3, except those with k = 1.
All entries in rows n >= 3 are divisible by F_2 = 17, except those with k = 4..7.

			Negated binary Walsh matrix of size 4 and row 2 of the triangle:
1 1 1 1        15
1 0 1 0         5
1 1 0 0         3
1 0 0 1         9
Triangle starts:
      k  =  0     1     2     3    4     5     6     7   8     9    10    11 ...
n
0           1
1           3     1
2          15     5     3     9
3         255    85    51   153   15   165   195   105
4       65535 21845 13107 39321 3855 42405 50115 26985 255 43605 52275 26265 ...

Tilman Piesk, Rows 0..8 of the triangle, flattened
Tilman Piesk, Prime factorizations
Tilman Piesk, Negated binary Walsh matrix of size 256

A228539 (the same for the binary Walsh matrix, not negated)
A197818 (antidiagonals of the negated binary Walsh matrix converted to decimal).
A000215 (Fermat numbers), A023394 (Prime factors of Fermat numbers).

T(n,k) + A228539(n,k) = 2^2^n - 1
T(n,0) = A051179(n)
T(n,2^n-1) = A122569(n+1)
A211344(n,k) = T(n,2^(n-k))

cp's OEIS Frontend

A190939 Subgroups of nimber addition interpreted as binary numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions