A040996 - OEIS

%I #54 Mar 23 2024 17:32:17

%S 1,6,120,32640,2147450880,9223372034707292160,

%T 170141183460469231722463931679029329920,

%U 57896044618658097711785492504343953926464851149359812787997104700240680714240

%N Maximum number of distinct functions at the bottom of a Boolean (or Binary) Decision Diagram (or BDD) with negation by pointer complementation.

%C At 0, the last variable, the only choice is (t, f) because the first entry is always uncomplemented and the 2nd must be different.

%C At level 1, the 2nd-to-last variable, the first entry is either t or a pointer to a following level (0) and the 2nd entry is either of these or its negation, except it may not equal the first entry.

%C At level n, the n-th-to-last variable, the first entry is either t or a pointer to one of the following levels' functions and the second entry is any of these or its negation, but not equal to the first entry.

%C From _Luis H. Gallardo_, Nov 18 2021: (Start)

%C Another description of a(n) follows: let TP(n) = t^(2^n-1)*(t+1)^(2^n-1) in the ring F_2[t]. Expand TP(n) as a sum of monomials c*t^k in F_2[t], with c equal 0 or 1. Lift TP(n) to LTP(n) in the ring Z[t], i.e., consider the coefficients c of TP(n) to be integers in LTP(n), instead of elements of F_2. Finally, substitute t by 2 in LTP(n). We get: a(n) = LTP(n).

%C Example: a(3) = subs(t=2, TP(3)) = 32640, where TP(3) = t^14 + t^13 + t^12 + t^10 + t^9 + t^8 + t^7 = t^7*(t+1)^7 in F_2[t]. (End)

%H Vincenzo Librandi, <a href="/A040996/b040996.txt">Table of n, a(n) for n = 0..12</a>

%H Cezar Campeanu, Nelma Moreira, and Rogerio Reis, <a href="https://www.dcc.fc.up.pt/Pubs/TR11/dcc-2011-07.pdf">Expected Compression Ratio for DFCA: experimental average case analysis</a>, Technical Report Series: DCC-2011-07, December 2011, Departamento de Ciencia de Computadores, Universidade do Porto.

%H Dagstuhl Seminar Design & Test, <a href="https://web.archive.org/web/20031202020741/http://www.bdd-portal.org/dagstuhl-ppt/dagstuhl-talks.htm">More about BDD's</a>

%H Alan J. Hu, David L. Dill, Andreas J. Drexler and C. Han Yang, <a href="https://doi.org/10.1007/3-540-56496-9_8">Higher-level specification and verification with BDDs</a>, In: von Bochmann G., Probst D.K. (eds) Computer Aided Verification. CAV 1992. Lecture Notes in Computer Science (1993), vol 663. Springer, Berlin, Heidelberg.

%F a(n) = (S(n-1) + 1) * (2*S(n-1) + 1) where S(n-1) = Sum_{k<n} a(k).

%F a(n) is the (2^(2^n)-1)-th triangular number; i.e., a(n) = 2^(2^n)*(2^(2^n)-1)/2.

%p a(n) = subs(t=2,modp(expand(t^(2^n-1)*(t+1)^(2^n-1)),2)); # _Luis H. Gallardo_, Nov 18 2021

%t f[x_]:=Module[{c=2^(2^x)},(c(c-1))/2]; Array[f,10,0] (* _Harvey P. Dale_, Sep 29 2011 *)

%o (PARI) a(n)=if(n<=0,n==0,2^(2^n)*(2^(2^n)-1)/2)

%o (Magma) [2^(2^n)*(2^(2^n)-1)/2: n in [0..10]]; // _Vincenzo Librandi_, Sep 30 2011

%Y Subsequence of A000217.

%K nonn

%O 0,2

%A _R. H. Hardin_