cp's OEIS Frontend

A286496 Renyi-Ulam liar numbers: maximum k such that n questions "Is x in subset S of {1,...,k}?" are guaranteed to determine x when at most one answer can be a lie.

%I A286496 #19 Jan 30 2024 14:59:27
%S A286496 1,1,1,2,2,4,8,16,28,50,92,170,314,584,1092,2048,3854,7280,13796,
%T A286496 26214,49932,95324,182360,349524,671088,1290554,2485512,4793490,
%U A286496 9256394,17895696,34636832,67108864,130150524,252645134,490853404,954437176,1857283154,3616814564
%N A286496 Renyi-Ulam liar numbers: maximum k such that n questions "Is x in subset S of {1,...,k}?" are guaranteed to determine x when at most one answer can be a lie.
%C A286496 Calculated from Andrzej Pelc's complete solution for 1-liar games which gives the minimum number of questions required for a given set {1,...,k}.
%C A286496 Andrzej Pelc's formula for the minimum number of questions required for a given set {1,...,k} is: the least value of q such that f(q)>=k, where f(q)=2^q/(q+1) for even k, and f(q)=(2^q-q+1)/(q+1) for odd k. We use this to generate the sequence of maximum set sizes for each value of q.
%H A286496 D. Osthus and R. Watkinson, <a href="http://dx.doi.org/10.4171/EM/92">A simple solution to Ulam's liar game with one lie</a>, Elemente der Mathematik 63 (2008), 97-101.
%H A286496 A. Pelc, <a href="https://doi.org/10.1016/0097-3165(87)90065-3">Solution of Ulam’s Problem on searching with a lie</a>, J. Combinatorial Theory, Series A, vol. 44 (1987), 129-140.
%e A286496 a(1) = 1 since 1 question is (vacuously) sufficient to determine x in {1}; a(2) = 1, since 2 questions (with one possible lie) is no better than 1; a(3) >= 2, since we can determine x in {1,2} by asking "Is x in {1}?" three times and majority voting. But a(3) is not >2 because we need 5 questions for {1,2,3}; which implies a(4) = 2 also.
%p A286496 LiarSequence:=proc(n)
%p A286496 local q,L,k;
%p A286496 q:=1: L:=NULL;
%p A286496 for k from 1 to n do
%p A286496    while 2^q/(q+1)-(k+1 mod 2)*(q-1)/(q+1)<k+1 do q:=q+1; L:=L,k end:
%p A286496 end: L end:
%Y A286496 Cf. A325908.
%K A286496 nonn
%O A286496 0,4
%A A286496 _Robin W. Whitty_, Jun 15 2017
%E A286496 a(0) and a(29)-a(37) from _Pontus von Brömssen_, Jan 30 2024