tag:blogger.com,1999:blog-3722233.post8899223100463789787..comments2021-04-17T12:06:11.845-05:00Comments on Computational Complexity: Find the Number- againLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-56763535603951044162009-08-05T09:51:09.980-05:002009-08-05T09:51:09.980-05:00Never mind open problems, I want this Alex as a gr...Never mind open problems, I want this Alex as a grad student. Tell him we'll give him a big stipend.some profnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9479160077692172592009-08-04T16:47:39.558-05:002009-08-04T16:47:39.558-05:00This problem (the general one) is well-known under...This problem (the general one) is well-known under the name of Ulam's game (or Ulam's problem).<br /><br />Take a look for instance at http://www.usna.edu/Users/math/wdj/montague/montague_mathhonors1998-1999.htmlgodel10https://www.blogger.com/profile/07722863911482570986noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8077015055732165732009-08-03T19:11:05.718-05:002009-08-03T19:11:05.718-05:00I mean Apply Chinese remaindering recursively: Sho...I mean Apply Chinese remaindering recursively: Should give O(\prod log^i n) where log^i is the i^th iterated log. I think the Chinese remainder should also give the lower bound. <br />anonymous #2.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77606029834110085222009-08-03T18:56:54.735-05:002009-08-03T18:56:54.735-05:00use the chinese remainder theorem for #2use the chinese remainder theorem for #2Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11934302676057369302009-08-03T16:36:43.471-05:002009-08-03T16:36:43.471-05:00For question 1, you need log_2 n questions. Ask i...For question 1, you need log_2 n questions. Ask if x is congruent to 0 mod 2. If it is, ask if it's congruent to 0 mod 4; if it's not, ask if it's congruent to 1 mod 4. Continue in this vein, basically building up the binary expansion of the number from the right, one bit at a time. On information-theoretic grounds you can't do better than getting one bit of information per question, so this is best possible.<br /><br />For question 2, I suspect the optimal strategy (at least as n goes to infinity) is to ask, each time, the question that rules out the largest portion of what remains of the search space. (This is basically a greedy algorithm.) This seems to mean that first you should pin down the number mod 2 (by asking one question), then mod 3 (two questions), then mod 5 (four questions), ...<br /><br />Now for the asymptotics of that strategy. For any integer k, let k# be the product of all primes less than or equal to k. Then to distinguish any number between 1 and n, we need to ask ((2-1) + (3-1) + (5-1) + ... + (k-1)) questions, where k is the smallest prime such that k# is at least n. (For example, if n is between 7 and 30, then we'll determine the residue of the target number mod 2, mod 3, and mod 5 to determine the target number. Now, if n is between 7 and 15 then we only need to know two of those residues; I'm ignoring that, since I think that doing so will at worst mean that we look at one more prime than in the optimal strategy.)<br /><br />Now, k# is roughly exp(k), so we'll end up taking k near log n. The sum of the primes up to x is of the order (x^2)/(2 log x), and I'll ignore the 1s getting subtracted off since I'm just trying to get leading-order asymptotics. Letting x = log n there, we find that <br /><br />(log n)^2/(2 log log n)<br /><br />questions are required. I suspect this is asymptotically the number of questions required, as n goes to infinity.Michael Lugohttps://www.blogger.com/profile/01950197848369071260noreply@blogger.com