20220417, 18:13  #1 
Aug 2010
2·5·67 Posts 
The triplinghalving reduction game
While trying to fall asleep last night, I thought up of the following game/problem. It inevitably made me stay awake even longer while trying to solve it, but in the end, I fell asleep before finding a solution.
Anyway, here's the game. You start with the number 1, and you have to get to a target number through any combination of the following three options. Not all of them have to be used, and a target number can be any nonnegative integer. 1.) Triple the number you currently have 2.) Reduce the number you have by adding 1 and then dividing by 2 3.) Reduce the number you have by subtracting 1 and then dividing by 2 For example, to get to a target number of 6, you could triple (1>3), triple (3>9), triple (9>27), reduce (27>13), and reduce (13>6). To get to a target number of 7, you could triple (1>3), triple (3>9), reduce (9>5), triple (5>15), and reduce (15>7). What is the smallest target number that cannot be reached? Alternatively, if such a number does not exist, prove that all nonnegative integers can be reached. 
20220417, 18:40  #2 
"Vincent"
Apr 2010
Over the rainbow
5×569 Posts 
isn't that a slightly modified collatz conjecture?
Last fiddled with by firejuggler on 20220417 at 18:44 
20220417, 20:33  #3  
"Robert Gerbicz"
Oct 2005
Hungary
11000100101_{2} Posts 
Quote:
All nonnegative integers are reachable! consider the following 9 ways of reductions, the first number is always the starter, then we show each following numbers in the routine: 8*N+1 > 24*N+3 > 12*N+1 > 36*N+3 > 18*N+1 > 9*N 8*N+1 > 24*N+3 > 72*N+9 > 36*N+5 > 18*N+3 > 9*N+1 8*N+1 > 24*N+3 > 72*N+9 > 36*N+5 > 18*N+3 > 9*N+2 8*N+3 > 24*N+9 > 72*N+27 > 36*N+13 > 18*N+7 > 9*N+3 8*N+3 > 24*N+9 > 72*N+27 > 36*N+13 > 18*N+7 > 9*N+4 8*N+3 > 24*N+9 > 12*N+5 > 6*N+3 > 18*N+9 > 9*N+5 8*N+7 > 4*N+3 > 12*N+9 > 36*N+27 > 18*N+13 > 9*N+6 8*N+7 > 24*N+21 > 12*N+11 > 6*N+5 > 18*N+15 > 9*N+7 8*N+7 > 24*N+21 > 12*N+11 > 6*N+5 > 18*N+15 > 9*N+8 that is, if we can reach all numbers<=8*N+7 then we can reach a complete residue system (mod 9), that is starting at 9*N. But 8*N+7<=9*N1 is true for N>=8, that is if we can reach only all integers M<9*8=72 then with induction you can reach all nonnegative integers. A simply code is showing that this is the case [you can restrict to the search that all intermediate numbers<1000]. Easily you can get also that the minimal number of steps for all N>0 is at most const * log(N), and of course this is sharp up to const. 

20220514, 03:28  #4 
Romulan Interpreter
"name field"
Jun 2011
Thailand
3·3,331 Posts 
+1. You were faster. Except, I proved immediately by descent (assume there was a "smallest" number that can not be reached, this can not be 3k, because then k is smaller and unreachable, and it can not be 3k+/1 because in that case 2k+/1 is smaller and unreachable.)
Last fiddled with by LaurV on 20220514 at 03:46 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Another factor algorithm using lattice reduction  Till  Factoring  1  20210824 14:03 
Computing Power Reduction?  Zhangrc  Marin's Mersennearies  3  20210815 13:36 
Efficient modular reduction with SSE  fivemack  Computer Science & Computational Number Theory  15  20090219 06:32 
CPU stats reduction  Prime95  PrimeNet  3  20081117 19:57 
Lattice Reduction  R.D. Silverman  Factoring  2  20050803 13:55 