mersenneforum.org The tripling-halving reduction game
 Register FAQ Search Today's Posts Mark Forums Read

 2022-04-17, 18:13 #1 MooMoo2     Aug 2010 22×167 Posts The tripling-halving 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 non-negative 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 non-negative integers can be reached.
 2022-04-17, 18:40 #2 firejuggler     "Vincent" Apr 2010 Over the rainbow 5×569 Posts isn't that a slightly modified collatz conjecture? Last fiddled with by firejuggler on 2022-04-17 at 18:44
2022-04-17, 20:33   #3
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

112·13 Posts

Quote:
 Originally Posted by MooMoo2 What is the smallest target number that cannot be reached? Alternatively, if such a number does not exist, prove that all non-negative integers can be reached.

All non-negative 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*N-1 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 non-negative 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.

2022-05-14, 03:28   #4
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

9,973 Posts

Quote:
 Originally Posted by R. Gerbicz All non-negative integers are reachable!
+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 2022-05-14 at 03:46

 Similar Threads Thread Thread Starter Forum Replies Last Post Till Factoring 1 2021-08-24 14:03 Zhangrc Marin's Mersenne-aries 3 2021-08-15 13:36 fivemack Computer Science & Computational Number Theory 15 2009-02-19 06:32 Prime95 PrimeNet 3 2008-11-17 19:57 R.D. Silverman Factoring 2 2005-08-03 13:55

All times are UTC. The time now is 23:34.

Thu Jun 30 23:34:29 UTC 2022 up 77 days, 21:35, 0 users, load averages: 1.67, 1.36, 1.24