A327461 Maximal size of a Binary Decision Diagram (or BDD) of index n.

3, 5, 7, 11, 19, 31, 47, 79, 143, 271, 511, 767, 1279, 2303, 4351, 8447, 16639, 33023, 65791, 131071, 196607, 327679, 589823, 1114111, 2162687, 4259839, 8454143, 16842751, 33619967, 67174399, 134283263, 268500991, 536936447, 1073807359, 2147549183, 4295032831

Offset

1,1

References

D. E. Knuth, The Art of Computer Programming, Volume 4A, Combinatorial Algorithms. Addison-Wesley Professional, 2011. See Section 7.1.4, Theorem U, page 234.

Links

Pontus von Brömssen, Table of n, a(n) for n = 1..1024

Julien Clément and Antoine Genitrini, Binary Decision Diagrams: from Tree Compaction to Sampling, arXiv:1907.06743 [cs.DS], 2019. See Section 6.1, especially Fact 24. (This section appears only in version 1 of the paper.)

Julien Clément and Antoine Genitrini, Combinatorics of Reduced Ordered Binary Decision Diagrams: Application to uniform random sampling, arXiv:2211.04938 [cs.DS], 2022, Theorem 13, p. 8.

Julien Clément and Antoine Genitrini, An Iterative Approach for Counting Reduced Ordered Binary Decision Diagrams, Symp. Math. Found. Comp. Sci. (2023) Vol. 272, Art. 36.

Formula

a(n) = 2^(n - A284248(n)) + 2^2^A284248(n) - 1. (See Knuth 2011.) - Pontus von Brömssen, Apr 08 2020

Prog

(Python)
def A327461(n):
  return 2**(n-(n-n.bit_length()+1).bit_length()+1)+2**2**((n-n.bit_length()+1).bit_length()-1)-1 # Pontus von Brömssen, Apr 08 2020

Crossrefs

Cf. A284248.

Sequence in context: A367195 A175196 A077858 * A126116 A161423 A133846

Adjacent sequences: A327458 A327459 A327460 * A327462 A327463 A327464

Keyword

nonn

Author

N. J. A. Sloane, Sep 26 2019

Extensions

More terms from Pontus von Brömssen, Apr 08 2020

Status

approved