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 A057241 #41 May 12 2024 11:42:21 %S A057241 0,0,3,6,10 %N A057241 Circuit cost of the hardest Boolean function of n variables; metric: 2-input AND-gates cost 1, NOT is free, fanout is free, inputs are free, no feedback allowed. %C A057241 a(5) <= 23. Boole expansion (Knuth page 52). %C A057241 XOR costs 3. %C A057241 a(5) <= 20. Modify procedure used to calculate a(5) in A056287 to add XOR. %C A057241 a(5) <= 18. Let f = g(xi = h), then cost(f) <= cost(h) + cost(g). This is a generalization of minimum memory operations (xi = xj op xk -- Knuth page 101). Add this for min(cost(g),cost(h)) <= 3. %C A057241 a(5) <= 17. Add cost(f(xi,xj = xi op1 xj, xi op2 xj)) <= cost(f) + 2 (Knuth page 105). %C A057241 a(5,17) <= 187 where a(5,c) is the number of functions classes that cost c. %C A057241 a(5,17) <= 1 (David Ian Stevenson). %C A057241 a(5) >= 13 Stockmeyer limit for symmetric function S124 (Knuth exercise 7.1.2 - 80 and answer to 20 which clarifies Richard C. Schroeppel's hardest functions). %D A057241 D. E. Knuth, The Art of Computer Programming, Volume 4A, Addison Wesley, 2011. %H A057241 Richard C. Schroeppel, <a href="/A057241/a057241.txt">Comments and examples</a> %H A057241 David Ian Stevenson, <a href="/A057241/a057241_1.txt">Shorter chains for 185 function classes</a> %H A057241 David Ian Stevenson, <a href="/A057241/a057241_2.txt">Table of a(5,c)</a> %Y A057241 Cf. A056287, A058759. %K A057241 nonn,nice,hard,more %O A057241 0,3 %A A057241 Richard C. Schroeppel, Jan 10 2001