This site is supported by donations to The OEIS Foundation.



Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

(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)



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).


D. E. Knuth, The Art of Computer Programming, Volume 4A, Addison Wesley, 2011.


Table of n, a(n) for n=0..4.

Richard C. Schroeppel, Comments and examples

David Ian Stevenson, shorter chains for 185 function classes


Cf. A056287, A058759.

Sequence in context: A293537 A073910 A115251 * A104617 A104618 A104616

Adjacent sequences:  A057238 A057239 A057240 * A057242 A057243 A057244




Richard C. Schroeppel, Jan 10 2001



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

License Agreements, Terms of Use, Privacy Policy .

Last modified November 21 13:53 EST 2017. Contains 295001 sequences.