[37] The prefix-code E∗ of Example 1.11.16 is an asymptotically optimal universal code because E2 is already one.

(a) Show that 

n 2−l

∗(n) = c with c = 2.865064 ... . Show that the Kraft inequality, Theorem 1.11.1, is satisfied with equality for the length set ln = l

∗(n) + log

c, n = 1, 2,... .

(b) Let the code E+ be defined by E+(x) = ¯

klk(x)l k−1(x). . . x, where the length function is iterated until the value l k(x) = 1. Show that E+ is prefix-free. Show that this representation of the integers is even more compact than E∗.

Comments. Source for Item (a): [J. Rissanen, Ann. Statist., 11(1983), 416–431].