Thread: Minimum (Number Theory Game) View Single Post
2021-08-08, 19:49   #2
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

2A2F16 Posts

Quote:
 Originally Posted by ThomasK Rules of the game Minimum 1. At the beginning of the game, any natural number > = 2 is drawn. The number of decimal digits of n is determined in advance and should be between 10 and 60.
So for the example you gave you gave a number smaller than 10 digits.
Quote:
 2. Each player tries to get from the number n to the number 2
So 2 is always your goal and has nothing to do with the 2 in rule 1.
Quote:
 3. In a calculation step, the player replaces n with n + 1 (addition step), with n - 1 (subtraction step) or with n / d, where d is a divisor of n and at the same time d <= (n ^ 0.5) . If a player has reached the number 2, his game is over. The player has to record all calculation steps in full.
I can choose to subtract n-2 from n and go right to the final in a single step. Or I can divide n by n (no cost division) and then add 1, thus a single step.
Quote:
 An example: The number 13356 was drawn.
This is less than the 10 to 60 digits in your suggestion.

Quote:
 If you analyze the number 13356 you will find out that with an infinitely good game you don't need a move to get to the number 2. 13356 : 53 252 : 7 36 : 3 12 : 3 4 : 2 2
This shows that the actual strategy is to go the other direction. Factor out excess powers of 2, then 3 or 5, then 5 or 3, then 7, etc. There are tricks for many of the low primes to check for divisiblity. Since divides are free we get:

13356 / 2
6678 / 3
2226 / 3
742 / 7 [checked via 7 divisibility trick (74 - (2 * 2) = 70, a multiple of 7)
106 / 53 [a quick check against 2 shows it to be 53]
2