

A286496


RenyiUlam 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.


2



1, 1, 1, 2, 2, 4, 8, 16, 28, 50, 92, 170, 314, 584, 1092, 2048, 3854, 7280, 13796, 26214, 49932, 95324, 182360, 349524, 671088, 1290554, 2485512, 4793490, 9256394, 17895696, 34636832, 67108864, 130150524, 252645134, 490853404, 954437176, 1857283154, 3616814564
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

Calculated from Andrzej Pelc's complete solution for 1liar games which gives the minimum number of questions required for a given set {1,...,k}.
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^qq+1)/(q+1) for odd k. We use this to generate the sequence of maximum set sizes for each value of q.


LINKS



EXAMPLE

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.


MAPLE

LiarSequence:=proc(n)
local q, L, k;
q:=1: L:=NULL;
for k from 1 to n do
while 2^q/(q+1)(k+1 mod 2)*(q1)/(q+1)<k+1 do q:=q+1; L:=L, k end:
end: L end:


CROSSREFS



KEYWORD

nonn


AUTHOR



EXTENSIONS



STATUS

approved



