This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A349481 #37 Dec 13 2021 17:44:28
%S A349481 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,
%T A349481 11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,
%U A349481 11,11,11,11,11,11,11,12
%N A349481 a(n) is the number of Boolean factors of the contranominal scale of size n by the GreConD algorithm for Boolean matrix factorization.
%C A349481 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.
%D A349481 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.
%D A349481 A. Albano, Upper Bound for the Number of Concepts of Contranominal-Scale Free Contexts. ICFCA 2014: 44-53.
%D A349481 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 A349481 D. Dürrschnabel, M. Koyda, and G. Stumme, Attribute Selection Using Contranominal Scales. ICCS 2021: 127-141.
%D A349481 B. Ganter and R. Wille, Formal Concept Analysis - Mathematical Foundations. Springer 1999, ISBN 978-3-540-62771-5, pp. I-X, 1-284.
%D A349481 D. I. Ignatov and A. Yakovleva, On Suboptimality of GreConD for Boolean Matrix Factorisation of Contranominal Scales. FCA4AI@IJCAI 2021, 87-98.
%D A349481 K. H. Kim, Boolean matrix theory and applications. Marcel Dekker, New York and Basel (1982).
%D A349481 E. Marenich, Determining the Schein Rank of Boolean Matrices. Matrix Methods: Theory, Algorithms and Applications (2010) 85-103.
%H A349481 Dmitry I. Ignatov, <a href="/A349481/b349481.txt">Table of n, a(n) for n = 1..513</a>
%H A349481 Dmitry I. Ignatov, <a href="/A349481/a349481.txt">iPython notebook with the code and the examples of factors up to 513</a>
%H A349481 Dmitry I. Ignatov, <a href="/A349481/a349481.pdf">iPython notebook in PDF with the code and the examples of factors up to 513</a>
%H A349481 D. I. Ignatov and A. Yakovleva, <a href="http://ceur-ws.org/Vol-2972/paper8.pdf">On Suboptimality of GreConD for Boolean Matrix Factorisation of Contranominal Scales</a>.
%H A349481 A. Yakovleva, <a href="https://github.com/yakovlevalexandra/On-Suboptimality-of-GreConD-for-Boolean-Matrix-Factorisation-of-Contranominal-Scales">Python Code</a>.
%H A349481 Wikipedia, <a href="https://en.wikipedia.org/wiki/Formal_concept_analysis">Formal Concept Analysis</a>.
%F A349481 a(n) = floor(log_2(n)) + ceiling(log_2(n)).
%e A349481 For n=1 there are zero factors.
%e A349481 For n=2 the factors are ({1}, {0}), ({0}, {1}). The coresspoding factorization is below:
%e A349481 A = P * Q
%e A349481 [0 1] [0 1] [1 0]
%e A349481 [1 0] [1 0] [0 1] .
%e A349481 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:
%e A349481 [0 1 1] [0 1 1] [1 0 0]
%e A349481 [1 0 1]=[1 0 1]*[0 1 0]
%e A349481 [1 1 0] [1 1 0] [0 0 1] .
%e A349481 For n=4 the factors are ({2, 3}, {0, 1}), ({0, 1}, {2, 3}), ({1, 3}, {0, 2}), ({0, 2}, {1, 3}).
%e A349481 ...
%e A349481 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}).
%e A349481 The nontrivial factorizaion with the number of factors k=5 smaller than n=7 is below:
%e A349481 [0 1 1 1 1 1 1] [0 1 0 1 1]
%e A349481 [1 0 1 1 1 1 1] [0 1 1 0 1] [1 1 1 0 0 0 0]
%e A349481 [1 1 0 1 1 1 1] [0 1 1 1 0] [0 0 0 1 1 1 0]
%e A349481 [1 1 1 0 1 1 1]=[1 0 0 1 1]*[1 0 0 1 0 0 1]
%e A349481 [1 1 1 1 0 1 1] [1 0 1 0 1] [0 1 0 0 1 0 1]
%e A349481 [1 1 1 1 1 0 1] [1 0 1 1 0] [0 0 1 0 0 1 0]
%e A349481 [1 1 1 1 1 1 0] [1 1 0 0 1] .
%Y A349481 A305233 represents the Schein rank of the contranominal scale of size n.
%K A349481 nonn
%O A349481 1,2
%A A349481 _Dmitry I. Ignatov_, Nov 19 2021