View Single Post
Old 2021-08-08, 19:49   #2
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

2A2F16 Posts
Default

Quote:
Originally Posted by ThomasK View Post
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
Uncwilly is offline   Reply With Quote