|
%I #38 Aug 21 2023 12:44:43
%S 3,5,7,11,19,31,47,79,143,271,511,767,1279,2303,4351,8447,16639,33023,
%T 65791,131071,196607,327679,589823,1114111,2162687,4259839,8454143,
%U 16842751,33619967,67174399,134283263,268500991,536936447,1073807359,2147549183,4295032831
%N Maximal size of a Binary Decision Diagram (or BDD) of index n.
%D 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.
%H Pontus von Brömssen, <a href="/A327461/b327461.txt">Table of n, a(n) for n = 1..1024</a>
%H Julien Clément and Antoine Genitrini, <a href="https://arxiv.org/abs/1907.06743">Binary Decision Diagrams: from Tree Compaction to Sampling</a>, arXiv:1907.06743 [cs.DS], 2019. See Section 6.1, especially Fact 24. (This section appears only in version 1 of the paper.)
%H Julien Clément and Antoine Genitrini, <a href="https://arxiv.org/abs/2211.04938">Combinatorics of Reduced Ordered Binary Decision Diagrams: Application to uniform random sampling</a>, arXiv:2211.04938 [cs.DS], 2022, Theorem 13, p. 8.
%H Julien Clément and Antoine Genitrini, <a href="https://doi.org/10.4230/LIPIcs.MFCS.2023.36">An Iterative Approach for Counting Reduced Ordered Binary Decision Diagrams</a>, Symp. Math. Found. Comp. Sci. (2023) Vol. 272, Art. 36.
%F a(n) = 2^(n - A284248(n)) + 2^2^A284248(n) - 1. (See Knuth 2011.) - _Pontus von Brömssen_, Apr 08 2020
%o (Python)
%o def A327461(n):
%o 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
%Y Cf. A284248.
%K nonn
%O 1,1
%A _N. J. A. Sloane_, Sep 26 2019
%E More terms from _Pontus von Brömssen_, Apr 08 2020
|
