login
Maximal number of symbols in terms generated by an inefficient set of rewrite rules for flattening combinator expressions of initial size n.
0

%I #1 Jun 29 2008 03:00:00

%S 1,2,4,8,16,32,273,65569,4294967361,

%T 15177100720513508366558296147058741458143803430094840009779784451085189728165691939

%N Maximal number of symbols in terms generated by an inefficient set of rewrite rules for flattening combinator expressions of initial size n.

%H C. Okasaki, <a href="http://okasaki.blogspot.com/2008/04/spectacular-failure.html">A Spectacular Failure</a>

%F a(n) = 2^(n-1), for n <= 6; a(n) = 2^a(n-3) + 2*a(n-3) + 1, for n > 6

%e For n=6, the maximum result is generated from the initial term X (X (X (X (X X)))). For n=10, the maximum result is generated from the initial term X (X X) (X (X X) (X (X (X X)))).

%K nonn

%O 1,2

%A Chris Okasaki (cokasaki(AT)acm.org), Apr 04 2008