Game of Scientists (Version 1)

Core observation

For any base $b$, if the answer is not -1, it is the digit sum $s_b(x)$. Since $b\equiv 1\pmod{b-1}$, every power of $b$ is also $1\pmod{b-1}$, so

$x \equiv s_b(x) \pmod{b-1}.$

So every useful query gives us a modular equation. The exact digit sum may contain more information too, but the congruence is the dependable part.

Also, if the answer is -1, then $x<b$. That means every query is both a modulus grabber and a threshold test. Pretty generous for an interactive problem, honestly.

The large-number branch

Ask base $71874$ first.

If the answer is not -1, then $x\ge 71874$. Now ask three more bases:

$71868,\quad 71862,\quad 71850.$

The moduli are:

$71873,\quad 71867,\quad 71861,\quad 71849.$

They are pairwise coprime, and their product is

$26669156098276365199 > 4\cdot 10^{18}.$

Since $x\le 4\cdot 10^{18}$, the four congruences determine exactly one possible $x$. Use CRT and we are done. No guessing, no vibes, no nonsense.

The small-number branch

If the first query returned -1, then $x<71874$. Now we only need to solve $1\le x\le 71873$ with three remaining queries.

Use this decision tree:

71874
  if x < 71874:
    33
      if x < 33:
        4
          if x < 4: query 2, interval [1, 3]
          else:     query 8, interval [4, 7] or [8, 32]
      else:
        2178
          if x < 2178: query 66, interval [33, 65] or [66, 2177]
          else:        query 66, interval [2178, 71873]

The queried base itself tells us which interval we are in, because -1 means below that base and non--1 means at least that base.

How do we recover inside an interval?

Keep the full transcript: every pair (base, answer). For every non--1 answer, add the congruence

$x\equiv answer \pmod{base-1}.$

Combine those congruences with CRT. That gives all possible candidates in the interval as

$r,\ r+M,\ r+2M,\ldots$

where $M$ is the CRT modulus product. Then test each candidate by recomputing the exact answers for all queried bases. The correct $x$ is the one whose simulated transcript matches.

This is not brute force over $4\cdot 10^{18}$, obviously. The candidate lists are tiny:

| final interval | useful moduli | candidates | |---|---:|---:| | $[1,3]$ | exact base $2$ check | at most $3$ | | $[4,7]$ | $3$ plus exact check | at most $2$ | | $[8,32]$ | $3\cdot 7=21$ plus exact check | at most $2$ | | $[33,65]$ | $32$ plus exact check | at most $2$ | | $[66,2177]$ | $32\cdot 65=2080$ plus exact check | at most $2$ | | $[2178,71873]$ | $32\cdot 2177\cdot 65$ | exactly $1$ |

The exact transcript check is the clean way to avoid fragile casework. If two numbers share the same CRT residue in a tiny interval, their actual digit sums in one of the queried bases split them apart.

Correctness proof

First, every non--1 answer gives a true congruence $x\equiv a\pmod{b-1}$, by the digit-sum identity above. Therefore the hidden number always satisfies the CRT system built from the transcript.

Second, every -1 answer gives a true inequality $x<b$, while every non--1 answer gives $x\ge b$. So the decision tree always places $x$ into the correct final interval.

Third, in the large branch, the product of the four pairwise-coprime moduli is greater than $c=4\cdot 10^{18}$. Thus there is at most one integer in $[1,c]$ satisfying all four congruences. Since the hidden $x$ satisfies them, CRT recovers exactly $x$.

Fourth, in the small branch, after CRT we enumerate only candidates inside the final interval that satisfy all modular constraints, then keep the one whose exact digit-sum answers match the full transcript. The hidden $x$ is included, and the construction above leaves no second matching candidate. So the recovered number is exactly $x$.

We use at most four queries in every branch, so the strategy fits $k=4$.

Complexity

Per game, the program makes at most $4$ queries and does constant-size CRT/candidate checking. The local computation is basically $O(\log c)$ because digit sums divide by the base repeatedly. The interaction dominates everything.