This site is supported by donations to The OEIS Foundation.



Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to 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

David Ian Stevenson, Table of a(5,c)


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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 11 13:25 EST 2018. Contains 318049 sequences. (Running on oeis4.)