Question

If you start at 1, can you get to every number by only following these rules?

Answer 1

You can multiply your number by 2 any time. And if your number is congruent to 4 in mod 6, then you're allowed to subtract by 1 and and divide by 3.

Answer 2

For example, if you want to get to 5, we start at 1 and multiply by 2 until we get to 16, which is 4 mod 6, so we're allowed to do our special rule, subtract 1 and divide by 3 to get 5.

Answer 3

on cursory reading this looks like inverse of collatz conjecture

Answer 4

every number? i guess you mean N

Answer 5

so 1 thing i guess. we have (6x+4)-1/3=2x+1 so odd number and 2x as even number so
we have whole N

Answer 6

Ok, @rational is right. This is equivalent to the collatz conjecture, which says if you pick any number and follow an algorithm, you will always end in 1 eventually. The algorithm is this:

If you number is even, divide by 2. If your number is odd, multiply by 3 and then add one.

---

So the way I figured out how to reverse it was by thinking about how to insure that it could be effectively followed backwards, since I realized this would give us choices. For example there are two ways to get to 10 in the collatz conjecture, we can either start at 3 which is odd so we multiply by 3 and add 1 to get 10 or we start at 20 and divide by 2. So from the perspective of standing at 10 we can look backwards and think, "Do I want to go to 3 or 20?"

We can always multiply by 2, there's no restriction on this, which is convenient. However for the other one we need to make sure our number is always going to give an odd number. In other words:

\[3(2n+1)+1=x\]
This represents putting in an odd number to the rule:

\[6n+4=x\]

So ALL numbers we get out of doing this in the collatz conjecture end up giving us a number that's congruent to 4 mod 6. So that's how I determined the reverse rule.

Answer 7

The fun stuff I'm beginning to explore now is the multiplication table in mod 6 arithmetic. Specifically:

\[2*2\equiv 4 \mod 6\]\[2*4\equiv 2 \mod 6\]\[2*5\equiv 4 \mod 6\]

But of course the whole multiplication table is important since we are expecting to hit every number, but these involve 4, which seems to be the central number here. I don't really have much more to say aout this for the time being, just a new way to look at this problem.

Answer 8

Nice! im still reading the first reply
when n=6t+4, we get an integer by doing (n-1)/3 and this step is somehow equivalent to the inverse of doing 3n+1 when n is odd hmm

Answer 9

gotcha! looks pretty cool xD

Answer 10

Yep, the thing that I'm working on next is understanding what pattern if any there is to the distribution of our answers after this step. Since in mod 6 we have
\(3*1 \equiv 4-1 \mod 6\)
\(3*3 \equiv 4-1 \mod 6\)
\(3*5 \equiv 4-1 \mod 6\)

The numbers we get out of this step will be either 1, 3, or 5 in mod 6 which can either be a good or bad thing since it gives us a nice spread of numbers from which we can do the multiply by 2 rule:

\(1*2\equiv 2 \mod 6\)
\(3*2\equiv 0 \mod 6\)
\(5*2\equiv 4 \mod 6\)

So there's definitely some thinking to be done on this, although I like the feel that I have a choice of where to go. Kinda feels more free haha.

Answer 11

Barring some error in my code, Mathematica tells me that for the first 100,000 natural numbers, the algorithm doesn't give you \(8\)... I'll plug in some more numbers.

Answer 12

That's not to say you get all the other possible numbers, the resulting sorted sequence seems to be skipping around quite a bit.

Answer 13

Which 8 numbers is it not able to get to?

Answer 14

Looking back, I doubt the code is right, as it only does one pass of the algorithm.

Also, I meant the actual number \(8\) doesn't appear in the list (but again, just from one pass). I'm not sure how to make it recursive...

Answer 15

Well 8 is one of the easiest to get since starting from 1 we can multiply that by 2 as many times as we like, so 1 -> 2 -> 4 -> 8 is how I would get to 8. Maybe I wasn't clear in how I described the algorithm?

Answer 16

No, it was clear, I just didn't account for the fact that you'd repeat the process.