Multiply with three, add one, and remove the evenness!!

Number Theory Level 5

Jack defines a function as $f_1 (x) = \dfrac{3x+1}{2^n},$ where $n$ is the largest non-negative integer such that $\dfrac{3x+1}{2^n}$ is an integer. He also defines $f_{k+1} (x)= f _1\big(f_k(x)\big).$

Trying various numbers in this function, he somehow ends up finding a positive integer $p < 100$ such that $f_p\big(2^{111} - 1\big) = 3^q \cdot 2^r - 1.$ He also notes that $q$ and $r$ are positive integers such that $q > r$ and $\gcd(q,r) > 8.$

What is the value of $q - r ?$

Inspired by a Collatz problem

The answer is 37.

1 solution

Afkar Aulia
Aug 28, 2018

Note that f1 (3^a . 2^b - 1) = (3(3^a . 2^b - 1) + 1)/(2^n) = (3^(a+1) . 2^b - 2) / (2^n)

As long as b > 1, we know that (3^(a+1) . 2^b - 2) is even and (3^(a+1) . 2^b - 2) / 2 is odd.

Thus, we can see that f1 (3^a . 2^b - 1) = (3^(a+1) . 2^b - 2) / 2 = 3^(a+1) . 2^(b - 1) - 1.

If we apply it to the problem, we can see that q+r = 111.

Now that we know that gcd(q,r) > 8 and gcd (q,r) divides 111, we know that gcd (q,r) can only be 1, 3, or 37.

Multiply with three, add one, and remove the evenness!!

The answer is 37.

1 solution

0 pending reports