This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. 3
 0, 0, 3, 6, 10 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS a(5) <= 23 Boole expansion (Knuth page 52) XOR costs 3 a(5) <= 20. Modify procedure used to calculate a(5) in A056287 to add XOR. a(5) <= 18. Let f = g(xi = h), then cost(f) <= cost(h) + cost(g). This is a generalisation of minimum memory operations (xi = xj op xk - Knuth page 101). Add this for min(cost(g),cost(h)) <= 3. a(5) <= 17. Add cost(f(xi,xj = xi op1 xj, xi op2 xj)) <= cost(f) + 2 (Knuth page 105). a(5,17) <= 187 where a(5,c) is the number of functions classes that cost c. a(5,17) <= 1 (David Ian Stevenson). 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). REFERENCES D. E. Knuth, The Art of Computer Programming, Volume 4A, Addison Wesley, 2011. LINKS Richard C. Schroeppel, Comments and examples David Ian Stevenson, shorter chains for 185 function classes David Ian Stevenson, Table of a(5,c) CROSSREFS Cf. A056287, A058759. Sequence in context: A293537 A073910 A115251 * A104617 A104618 A104616 Adjacent sequences:  A057238 A057239 A057240 * A057242 A057243 A057244 KEYWORD nonn,nice,hard,more AUTHOR Richard C. Schroeppel, Jan 10 2001 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified October 22 22:34 EDT 2019. Contains 328335 sequences. (Running on oeis4.)