A number-theory problem

[coldtortuga]

Let n be an odd number. For what values of k is 2kn-1 divisible by 3?
Edited to add: Of course, this post is inspired by the recent xkcd #710 on the Collatz Problem :-)
Suppose that we find a counterexample: a number C1 such that the Collatz iterates {Ck}k>0 starting from C1 does not include 1. Note that the iterates must have a minimum value

Comments

[jon_leonard]

Kind of interesting. I presume that n is odd to avoid negative values of k?

Also, did you want an induction proof of the answer?

[coldtortuga]

I edited the post to add more details, and hopefully thus I answer your questions indirectly :-)

[jon_leonard]

Ah, I'd missed the connection, and considered the problem in isolation.

Because 2 is -1 mod 3, multiplying by 2 alternates between two congruence classes. If n is 1 mod 3, then n*2^k-1 will be divisible by 3 for even (nonnegative) k. If n is 2 mod 3, it'll be divisible for odd (nonnegative) k. If n is 0 mod 3, then it'll never be divisible by 3.

The Collatz problem only becomes hard because the operation is iterated an unbounded number of times.

[leech]

If n is divisible by 3, no k will work.

If n is 1 mod 3, 2^k must be 1 mod 3, so k must be even.

If n is 2 mod 3, 2^k must be 2 mod 3, so k must be odd.

Thus for each odd number n, we are interested in an equivalence class that contains all numbers of the form 2kn = 3*o+1 for an odd number o. ... I think this is the same as all values of k>0 such that 2k n ≅ 1 (mod 3) but I haven't convinced myself.

It is indeed the same. If 2^k * n == 1 mod 3, then 2^k * n = 3a + 1 for some integer a, and by parity a must be odd.