cp's OEIS Frontend

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.

Showing 1-1 of 1 results.

A112535 Number of truth tables generated by 3CNF expressions of n variables.

Original entry on oeis.org

2, 4, 16, 256, 43146, 120510132, 4977694100656
Offset: 0

Views

Author

C. Bradford Barber (bradb(AT)shore.net), Dec 13 2005

Keywords

Comments

For n=5, computing the number of 3CNF truth tables took 2^32 bytes and 2^38 iterations. Computing the same number for n=6 may require 2^64 bits and 2^71 iterations.
I calculated a(6) using a different method; a(7) looks a lot harder. - Don Knuth, Dec 10 2012

References

  • Knuth, Donald E., Satisfiability, Fascicle 6, volume 4 of The Art of Computer Programming. Addison-Wesley, 2015, pages 148 and 220, Problem 191.

Links

Crossrefs

Cf. A034472, A109457 (corresponding sequences for 1CNF and 2CNF), A112650, A000157, A000371, A000613, A000618, A003181.

Extensions

a(6) from Don Knuth, Dec 10 2012
Showing 1-1 of 1 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.