cp's OEIS Frontend

A328950 Numerators for the "Minimum-Redundancy Code" card problem.

%I A328950 #52 Aug 23 2024 22:54:20
%S A328950 0,3,9,19,33,51,74,102,135,173,216,264,318,378,444,516,594,678,768,
%T A328950 864,966,1074,1188,1308,1435,1569,1710,1858,2013,2175,2344,2520,2703,
%U A328950 2893,3090,3294,3505,3723,3948,4180,4419,4665,4918,5178,5445,5719,6000,6288,6584,6888,7200,7520,7848
%N A328950 Numerators for the "Minimum-Redundancy Code" card problem.
%C A328950 Given a deck of cards consisting of one 1, two 2's, three 3's, ..., n n's, what's the best average number of yes-or-no questions needed to ask to determine a randomly drawn card?  The answer is the above sequence divided by the number of cards (A000217).
%C A328950 The problem can be solved using Huffman codes.
%C A328950 This problem was popularized in Martin Gardner's Scientific American "Mathematical Games" column, and was included in his book "My Best Mathematical and Logic Puzzles".
%C A328950 Also a(n) is the merge cost in the optimal file merge pattern algorithm applied to the list comprising 1 to n. - _Darío Clavijo_, Aug 21 2024
%D A328950 Martin Gardner, My best mathematical and logic puzzles. New York: Dover Publications Inc., 1995, p. 29, puzzle #52 "Playing Twenty Questions when Probability Values Are Known".
%H A328950 geeksforgeeks.org, <a href="https://www.geeksforgeeks.org/optimal-file-merge-patterns/&#34;">Optimal merge patterns</a>.
%H A328950 D. A. Huffman, <a href="https://pzs.dstu.dp.ua/ComputerGraphics/ic/bibl/huffman.pdf">A Method for the Construction of Minimum-Redundancy Codes</a>, in Proceedings of the IRE, vol. 40, no. 9, pp. 1098-1101, Sept. 1952.
%e A328950 For n=2, there are 3 cards, so a(2)/3 = 3/3 = 1 question is needed on average.
%e A328950 For n=3, there are 6 cards, so a(3)/6 = 9/6 = 1.5 questions are needed on average.
%o A328950 (Python)
%o A328950 def Ofmp(f):
%o A328950     c = 0
%o A328950     while len(f) > 1:
%o A328950         f.sort()
%o A328950         m = f[0] + f[1]
%o A328950         c += m
%o A328950         f[0] = m
%o A328950         f.pop(1)
%o A328950     return c
%o A328950 a = lambda n: Ofmp(list(range(1, n+1)))
%o A328950 print([a(n) for n in range(1, 49)]) # _Darío Clavijo_, Aug 21 2024
%Y A328950 Cf. A286496.
%K A328950 nonn,frac
%O A328950 1,2
%A A328950 _Danny Pflughoeft_, Nov 10 2019