Infinitely many primes.

Here is a game.

I've picked a number between 0 and N and your goal is to find out what the number is by asking me yes/no questions.

(1) There are N+1 possible numbers i could have picked, so any plan that you devise will require you to ask at least lg(N + 1) questions in the worst case.
(2) There is a plan that you can follow that will require at most ceiling(lg(N + 1)) questions -- a binary search will do.


Assume (to reach a contradiction) that there are finitely many primes p_1, ..., p_M.

(3) N = p_1^k_1 * ... * p_M^k_M for some choice of non-negative integers k_1, ..., k_M.

(4) Since the smallest prime is 2, we have k_i <= lg(N) for all i. Consider the following plan.

Use (2) to determine k_1 in at most ceiling(lg(k_1)) <= ceiling(lg(lg(N))) questions.
Use (2) to determine k_2 in at most ceiling(lg(k_2)) <= ceiling(lg(lg(N))) questions
. . . .

We have determined k_1, ..., k_M in at most M * ceiling(lg(lg(N))) questions. But this determines N completely! So we have determined N in at most M * ceiling(lg(lg(N))) <= M * (1 + lg(lg(N))) = M * (lg(2) + lg(lg(N))) = M * (lg(2 * lg(N))) = lg((2 * lg(N))^M) questions.


(5) You can win the game in at most lg((2 * lg(N))^M) questions for any N. By (5) and (1), for all N we have lg((2 * lg(N))^M) >= lg(N + 1), killing the lg's gives

(2 * lg(N))^M >= N + 1

This holds for all N, so in particular for N >= 2^(2^(2^(2^M - 1) / M) / 2). This gives

(2 * lg(2^(2^(2^(2^M - 1) / M) / 2)))^M >= 2^(2^(2^(2^M - 1) / M) / 2) + 1
(2 * 2^(2^(2^M - 1) / M) / 2)^M >= 2^(2^(2^(2^M - 1) / M) / 2) + 1
(2^(2^(2^M - 1) / M))^M >= 2^(2^(2^(2^M - 1) / M) / 2) + 1
2^(2^(2^M - 1)) >= 2^(2^(2^(2^M - 1) / M) / 2) + 1
2^(2^(2^M - 1)) > 2^(2^(2^(2^M - 1) / M) / 2)
2^(2^M - 1) > 2^(2^(2^M - 1) / M) / 2
2^((2^M - 1) + 1) > 2^(2^(2^M - 1) / M)
2^(2^M) > 2^(2^(2^M - 1) / M)
2^M > 2^(2^M - 1) / M

M > 2^(2^M - M - 1)

Which is false for all positive integers. This contradiction completes the proof.


solkkj


uaugw


boiagmz