A305233 -id:A305233 - cp's OEIS frontend

A056641 Least positive integer k for which (b+1)^k is not palindromic in base b, b = 2, 3, 4, ...

4, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9

Offset: 2

Helge Robitzsch (hrobi(AT)math.uni-goettingen.de), Aug 11 2000

Sequence of run lengths is C(n,[ (n-1)/2 ]) (= A037952), n=1,2,3,...; sequence of b where a(b) != a(b-1), b >= 3, is C(b-1,[ (b-1)/2 ]) (= A001405).

			The 4th term is 4 because base 5 representations of (5+1)^1 = 11, (5+1)^2 = 121, (5+1)^3 = 1331, are all palindromic, while (5+1)^4 = 20141 is not.

Cf. A037952, A001405, A305233.

palq[x_] := x == Reverse[x] Table[x = 0; While[palq[IntegerDigits[(t + 1)^x, t]], ++x]; x, {t, START, FINISH}] (* Dylan Hamilton, Aug 15 2010 *)

A349481 a(n) is the number of Boolean factors of the contranominal scale of size n by the GreConD algorithm for Boolean matrix factorization.

Original entry on oeis.org

0, 2, 3, 4, 5, 5, 5, 6, 7, 7, 7, 7, 7, 7, 7, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12

Offset: 1

Dmitry I. Ignatov, Nov 19 2021

nonn

Contranominal scales can be considered as Boolean matrices of size n X n full of ones except the main diagonal, which is filled by zeros (Ganter and R. Wille, 1999). The optimal number k of Boolean factors for a Boolean matrix A is known as its Schein rank (Kim, 1982; Marenich, 2010) and is defined as the smallest k such that A=P*Q, where * is Boolean matrix multiplication, A has the size n X m, and P,Q are n X k and k X m Boolean matrices, respectively. The problem of Boolean matrix factorization (BMF) is NP-hard and one of the state-of-the-art greedy algorithms is GreConD (Belohlavek & Vychodil, 2010). Contranominal scales are known as the worst theoretical case w.r.t. the number of potential Boolean factors (formal concepts), 2^n (Albano, 2014; Albano and Chornomaz, 2017; Dürrschnabel et al., 2021), while their Schein rank is given by A305233. The output of GreConD does not always result in the optimal number of factors for contranominal scales, so the sequence of its outputs is checked empirically for n up to 128 and the formula for a(n) is provided in (Ignatov & Yakovleva, 2021). See the links below for more checked examples up to n=513.

			For n=1 there are zero factors.
For n=2 the factors are ({1}, {0}), ({0}, {1}). The coresspoding factorization is below:
  A  =  P  *  Q
[0 1] [0 1] [1 0]
[1 0] [1 0] [0 1] .
For n=3 the factors are ({1, 2}, {0}), ({0, 2}, {1}), ({0, 1}, {2}). The corresponding trivial factorization, A=P*Q, where P=A and Q is the 3 X 3 identity matrix, is below:
[0 1 1] [0 1 1] [1 0 0]
[1 0 1]=[1 0 1]*[0 1 0]
[1 1 0] [1 1 0] [0 0 1] .
For n=4 the factors are ({2, 3}, {0, 1}), ({0, 1}, {2, 3}), ({1, 3}, {0, 2}), ({0, 2}, {1, 3}).
...
For n=7 the factors are ({3, 4, 5, 6}, {0, 1, 2}), ({0, 1, 2, 6}, {3, 4, 5}), ({1, 2, 4, 5}, {0, 3, 6}), ({0, 2, 3, 5}, {1, 4, 6}), ({0, 1, 3, 4, 6}, {2, 5}).
The nontrivial factorizaion with the number of factors k=5 smaller than n=7 is below:
[0 1 1 1 1 1 1] [0 1 0 1 1]
[1 0 1 1 1 1 1] [0 1 1 0 1] [1 1 1 0 0 0 0]
[1 1 0 1 1 1 1] [0 1 1 1 0] [0 0 0 1 1 1 0]
[1 1 1 0 1 1 1]=[1 0 0 1 1]*[1 0 0 1 0 0 1]
[1 1 1 1 0 1 1] [1 0 1 0 1] [0 1 0 0 1 0 1]
[1 1 1 1 1 0 1] [1 0 1 1 0] [0 0 1 0 0 1 0]
[1 1 1 1 1 1 0] [1 1 0 0 1] .

A. Albano and B. Chornomaz, Why concept lattices are large: extremal theory for generators, concepts, and VC-dimension. Int. J. Gen. Syst. 46(5) (2017) 440-457.
A. Albano, Upper Bound for the Number of Concepts of Contranominal-Scale Free Contexts. ICFCA 2014: 44-53.
R. Belohlavek and V. Vychodil, Discovery of optimal factors in binary data via a novel method of matrix decomposition. Journal of Computer and System Sciences 76(1) (2010) 3 - 20.
D. Dürrschnabel, M. Koyda, and G. Stumme, Attribute Selection Using Contranominal Scales. ICCS 2021: 127-141.
B. Ganter and R. Wille, Formal Concept Analysis - Mathematical Foundations. Springer 1999, ISBN 978-3-540-62771-5, pp. I-X, 1-284.
D. I. Ignatov and A. Yakovleva, On Suboptimality of GreConD for Boolean Matrix Factorisation of Contranominal Scales. FCA4AI@IJCAI 2021, 87-98.
K. H. Kim, Boolean matrix theory and applications. Marcel Dekker, New York and Basel (1982).
E. Marenich, Determining the Schein Rank of Boolean Matrices. Matrix Methods: Theory, Algorithms and Applications (2010) 85-103.

Dmitry I. Ignatov, Table of n, a(n) for n = 1..513
Dmitry I. Ignatov, iPython notebook with the code and the examples of factors up to 513
Dmitry I. Ignatov, iPython notebook in PDF with the code and the examples of factors up to 513
D. I. Ignatov and A. Yakovleva, On Suboptimality of GreConD for Boolean Matrix Factorisation of Contranominal Scales.
A. Yakovleva, Python Code.
Wikipedia, Formal Concept Analysis.

A305233 represents the Schein rank of the contranominal scale of size n.

a(n) = floor(log_2(n)) + ceiling(log_2(n)).

cp's OEIS Frontend

A056641 Least positive integer k for which (b+1)^k is not palindromic in base b, b = 2, 3, 4, ...

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica