MathDB

Alice and Bob are playing a guessing game. Bob is thinking of a number n of the form

2^a3^b

, where a and b are positive integers between

1

and

2020

, inclusive. Each turn, Alice guess a number m, and Bob will tell her either

\gcd (m, n)

lcm (m, n)

(letting her know that he is saying that

gcd

lcm

), as well as whether any of the respective powers match up in their prime factorization. In particular, if

m = n

, Bob will let Alice know this, and the game is over. Determine the smallest number

k

so that Alice is always able to find

n

within

k

guesses, regardless of Bob’s number or choice of revealing either the

lcm

, or the

gcd

Problem Statement