# The game of Shafiqa and Habibi

Shafiqa chose a positive integer number $X\le100$, and Habibi is trying to guess the number. Habibi can select two natural numbers $M$ and $N$ less than $100$ and ask about the greatest common divisor $\gcd(X+M,N)$ of $x+M$ and $N$.

Can Habibi always determine Shafiqa's number with at most seven questions?

Yes.

Why:

He first asks the values from $gcd(X+0,30)$ to $gcd(X+3,30)$. Two of $X,X+1,X+2,X+3$ are bound to be divisible by 2, and at least one is a multiple of 3. If none of them are divisible by 5, $X+4$ is, but whether it's the case or not he can then determine the $mod 2,3$ and $5$ values of $X$. Thus, there are 3 or 4 possible $X$ solutions in the form of $n, n+30, n+60$, with $n+90$ in the mix if possible. If he asks the GCDs of $X$ and these values starting from the last, he can either find the solution directly (the first answer equal to the number he picked) or by eliminating the rest after 3 more questions at most.

An alternative solution:

He first asks the values from $gcd(X+0,70)$ to $gcd(X+5,70)$, which allows him to determine the $mod 2,5$ and $7$ values of $X$. Thus, there are 1 or 2 possible $X$ solutions in the form of $n$ and $n+70$ if possible. If $n>29$, there's only one solution. Otherwise he asks the GCD of $X$ and $n+70$, after which he can either find the solution directly or by eliminating the rest.

• $M$ is a natural number and hence can't be 0. – Paul Evans Feb 22 '16 at 10:49
• 0 is also a natural number. – Nautilus Feb 22 '16 at 12:59
• – Paul Evans Feb 22 '16 at 13:43

Even I like the answer of Nautilus, I have a different approach.

In the very first round M isn't important, because you can swap M and X.

So I set M to 1 and want to get the most possible information out of the GCD-Answer. Like Nautilus I came to N = 30 (because of 2*3*5) to "filter" these prime numbers. But this is improvable. I can get out more information if I choose a number beyond 50. (50 because 1+50*z is at maximum 2 times a number from 1 to 100)

If I choose 30 I get 8 possible results for GCD(1+x, 30). For example N = 60 (2*2*3*5) or 72 (2*2*2*3*3) or 96 (2*2*2*2*2*3) would give me 12 different values.

This means: If I can build a binary search for the problem, I will find an answer within 6 rounds. This is a little bit complicated to explain (for me), but there are only 32 different possibilities where the GCD-answer is 1. And Sqrt(32) = 5.6568. This all counts only for the first round. Because if you can eliminate so much branches here, you can maybe get more information in the next rounds.

So first I think about an AI for this, but I don't want to overengineer and just bruteforced it with an algorithm to find a fingerprint in 6 rounds for all 100 X.

6 rounds: (M=1,N=40), (M=2,N=30), (M=3,N=40), (M=4,N=80), (M=5,N=27), (M=6,N=48) gives a fingerprint

This is not all. Because you can eliminate more numbers per round than only 50%, you can build a shorter fingerprint.

5 rounds: (M=1,N=40), (M=2,N=30), (M=3,N=40), (M=4,N=80), (M=6,N=48)

• Didn't read your answer before coding mine, but yeah that last sequence works in 5 (as well) and i like it here's a fiddle for your solution – DrunkWolf Feb 22 '16 at 9:55
• @DrunkWolf: Thanks. A very nice code! – Varon Feb 22 '16 at 9:59
• You're welcome, it was very close to the code i used for my solution so figured i might as well test your sequence :) – DrunkWolf Feb 22 '16 at 10:04
• Another question is: Can you do it in only 4 rounds, if you choose the next M and N depending on the answers before? – Varon Feb 22 '16 at 12:54