mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2022-04-17, 18:13   #1
MooMoo2
 
MooMoo2's Avatar
 
Aug 2010

10100111112 Posts
Default 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.
MooMoo2 is offline   Reply With Quote
Old 2022-04-17, 18:40   #2
firejuggler
 
firejuggler's Avatar
 
"Vincent"
Apr 2010
Over the rainbow

2×1,429 Posts
Default

isn't that a slightly modified collatz conjecture?

Last fiddled with by firejuggler on 2022-04-17 at 18:44
firejuggler is offline   Reply With Quote
Old 2022-04-17, 20:33   #3
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

19·83 Posts
Default

Quote:
Originally Posted by MooMoo2 View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2022-05-14, 03:28   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

24·3·211 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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
LaurV is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Another factor algorithm using lattice reduction Till Factoring 1 2021-08-24 14:03
Computing Power Reduction? Zhangrc Marin's Mersenne-aries 3 2021-08-15 13:36
Efficient modular reduction with SSE fivemack Computer Science & Computational Number Theory 15 2009-02-19 06:32
CPU stats reduction Prime95 PrimeNet 3 2008-11-17 19:57
Lattice Reduction R.D. Silverman Factoring 2 2005-08-03 13:55

All times are UTC. The time now is 10:01.


Tue Oct 4 10:01:52 UTC 2022 up 47 days, 7:30, 0 users, load averages: 1.10, 1.03, 0.96

Powered by vBulletin® Version 3.8.11
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.

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