Solution of Ulam's problem on binary search with two lies

AbstractSomeone thinks of a number between one and one million (which is just less than 220). Another person is allowed to ask up to twenty questions, to each of which the first person is supposed to answer only yes or no. Obviously the number can be guessed by asking first: Is the number in the first half million? then again reduce the reservoir of numbers in the next question by one-half, and so on. Finally the number is obtained in less than log2(1,000,000). Now suppose one were allowed to lie once or twice, then how many questions would one need to get the right answer?—S. M. Ulam, “Adventures of a Mathematician,” p. 281, Scribner's, New York, 1976