Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%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