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 generalization 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
KEYWORD
nonn,nice,hard,more
AUTHOR
Richard C. Schroeppel, Jan 10 2001
STATUS
approved