mersenneforum.org The tripling-halving reduction game
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2022-04-17, 18:13 #1 MooMoo2     Aug 2010 23×83 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 17×167 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

25·72 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

2·17·293 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:13.

Mon May 23 23:13:49 UTC 2022 up 39 days, 21:15, 0 users, load averages: 1.63, 1.51, 1.47

Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔