# Background

The famous Collatz Sequence is generated with the following rules:

* Start with a positive integer `a[0] = n`.
* If `a[i]` is even, `a[i+1] = a[i] / 2`.
* Otherwise, `a[i+1] = a[i] * 3 + 1`.

However, for the purpose of this Kata, I give a **slightly modified definition**:

* If `a[i]` is even, `a[i+1] = a[i] / 2`. This step is a step-down, or `D`.
* Otherwise, `a[i+1] = (a[i] * 3 + 1) / 2`. This step is a step-up, or `U`.

Also, for any starting number, the sequence is generated indefinitely, not ending at 1.

# Problem Description

For any given starting number, we can record the types of steps(`D` or `U`) from it.
For example, if we start with the number 11, the Collatz steps look like this:
```
a[0] = 11
a[1] = (11 * 3 + 1) / 2 = 17 -> U
a[2] = (17 * 3 + 1) / 2 = 26 -> U
a[3] = 26 / 2 = 13           -> D
a[4] = (13 * 3 + 1) / 2 = 20 -> U
a[5] = 20 / 2 = 10           -> D
a[6] = 10 / 2 = 5            -> D
a[7] = (5 * 3 + 1) / 2 = 8   -> U
a[8] = 8 / 2 = 4             -> D
a[9] = 4 / 2 = 2             -> D
a[10] = 2 / 2 = 1            -> D
a[11] = (1 * 3 + 1) / 2 = 2  -> U
a[12] = 2 / 2 = 1            -> D
...
```

```
11 -> 17 -> 26 -> 13 -> 20 -> 10 -> 5 -> 8 -> 4 -> 2 -> 1 -> 2 -> 1 -> ...
   U     U     D     U     D     D    U    D    D    D    U    D
```

Based on the steps shown above, the first four Collatz steps of 11 is `UUDU`.
Also, 107 is the smallest number over 100 whose Collatz steps start with `UUDU`, and
1003 is the smallest number over 1000 with the property.

A special example is the number 1, which can generate any number of `UD`.

Find the smallest integer exceeding or equal to `n` whose Collatz steps start with the given string `steps`.

# Constraints

`1 <= n <= 10 ** 9`

`n` is always a valid integer.

`1 <= length(steps) <= 25`

The string `steps` will entirely consist of `U`s and `D`s.

# Examples

```python
collatz_steps(1, 'UUDU') == 11
collatz_steps(100, 'UUDU') == 107
collatz_steps(1000, 'UUDU') == 1003

collatz_steps(1, 'UD') == 1
collatz_steps(1, 'UDUD') == 1
collatz_steps(1, 'UDUDUD') == 1
```

# Hint

If you are completely lost, start by answering the following question:

* After applying the given steps (e.g. `UUDU`) to an initial number `x`,
  what fraction do you get?
  
After that, you might want to study about [modular inverse](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse).

# Acknowledgement

This problem was inspired by [Project Euler #277: A Modified Collatz sequence](https://projecteuler.net/problem=277).

If you enjoyed this Kata, please also have a look at [my other Katas](https://www.codewars.com/users/Bubbler/authored)!

Source: codewars | Difficulty: MEDIUM_HARD
Tags: Mathematics

Ad-hoc

Starter code: def collatz_steps(n, steps):
	

Solutions:
def collatz_steps(n, steps):
	while True:
		str = ''
		result = n
		while bool(str != steps) ^ bool(str != steps[:len(str)]):
			if result % 2 == 0:
				result = result / 2
				str += 'D'
			else:
				result = (3 * result + 1) / 2
				str += 'U'
		if str != steps:
			n += 2 ** (len(str) - 1)
		else:
			return n


def collatz_steps(n, steps):
	(a, b, m) = (1, 0, 1)
	for c in steps:
		if 'U' == c:
			b = 3 * b + m
			a *= 3
		m *= 2
	ret = -b * pow(a, m // 2 - 1, m)
	ret += (n + m - 1 - ret) // m * m
	return ret


def ModInv(a, m):
	return pow(a, (m >> 1) - 1, m)

def Ext_Euclid_Alg(a, m):
	(old_r, r) = (a, m)
	(old_s, s) = (1, 0)
	while r:
		q = old_r // r
		(old_r, r) = (r, old_r - q * r)
		(old_s, s) = (s, old_s - q * s)
	return old_s if old_s > 0 else old_s + m

def collatz_steps(n, steps):
	(a, b, m) = (1, 0, 1)
	for (i, s) in enumerate(steps):
		m *= 2
		if s == 'U':
			a *= 3
			b = 3 * b + 2 ** i
	x = -b * ModInv(a, m) % m
	x += m * (n // m)
	return x + m if x < n else x


def collatz_steps(n, steps):
	i = 0
	(exp_2, exp_3) = (1, 1)
	(ind, flag) = (0, 0)
	for i in range(0, len(steps)):
		if i == 0 and steps[0] == 'U':
			exp_3 = exp_3 * 3
			ind = 1
			exp_2 = exp_2 * 2
		elif steps[i] == 'U':
			exp_3 = exp_3 * 3
			ind = ind * 3 + exp_2
			exp_2 = exp_2 * 2
		elif steps[i] == 'D':
			exp_2 = exp_2 * 2
	i = (exp_3 * n + ind) // exp_2
	while flag == 0:
		if (exp_2 * i - ind) % exp_3 == 0:
			flag = 1
		else:
			i = i + 1
	return (exp_2 * i - ind) // exp_3


def modinv(a, m):
	return pow(a, (m >> 1) - 1, m)

def c(string):
	(x, y, z) = (1, 0, 1)
	for char in string:
		(x, y, z) = (x + (x << 1), y + (y << 1) + z, z << 1) if char == 'U' else (x, y, z << 1)
	return (x, y, z)

def collatz_steps(n, steps):
	(x, y, z) = c(steps)
	p = modinv(x, z) * -y % z
	p += (n - p) // z * z
	while p < n:
		p += z
	return p


import math

def ModularInverse(a, b):
	coeffs = []
	while b > 0:
		coeffs.append(math.floor(a / b))
		(a, b) = (b, a % b)
	c1 = 1
	c2 = 0
	for co in coeffs[::-1]:
		(c1, c2) = (c2, c1 - co * c2)
	return c2

def collatz_steps(n, steps):
	a = 1
	b = 0
	m = 1
	for i in range(len(steps)):
		m = m * 2
		if steps[i] == 'U':
			a = a * 3
			b = 3 * b + 2 ** i
	x = -b * ModularInverse(m, a) % m + m * math.floor(n / m)
	if x < n:
		x = x + m
	return x


import math

def collatz_steps(n, steps):
	a = 1
	b = 0
	m = 1
	for i in range(len(steps)):
		m = m * 2
		if steps[i] == 'U':
			a = a * 3
			b = 3 * b + 2 ** i
	b = m - b % m
	a = a % m
	coeffs = []
	ae = m
	be = a
	while be > 0:
		coeffs.append(math.floor(ae / be))
		(ae, be) = (be, ae % be)
	xe = 0
	ye = 1
	for co in coeffs[::-1]:
		(xe, ye) = (ye - co * xe, xe)
	ai = xe % m
	x = b * ai % m
	x = x + m * math.floor(n / m)
	if x < n:
		x = x + m
	return x


from math import ceil

def collatz_steps(min_number, steps):
	(start, interval) = start_and_interval(steps)
	n_intervals = ceil((min_number - start) / interval)
	return start + n_intervals * interval

def start_and_interval(steps):
	start = 1
	interval_start = 1
	end = 1
	interval_end = 1
	for step in steps:
		if end % 2 == 0:
			expected_next = 'D'
		else:
			expected_next = 'U'
		if step != expected_next:
			start += interval_start
			end += interval_end
		if step == 'D':
			end //= 2
		else:
			end = (end * 3 + 1) // 2
			interval_end *= 3
		interval_start *= 2
	return (start, interval_start)


def collatz_steps(n, s):
	while True:
		x = n
		ans = ''
		flag = True
		for j in range(len(s)):
			if x % 2 == 0:
				x = x // 2
				ans += 'D'
			else:
				x = (x * 3 + 1) // 2
				ans += 'U'
			if ans[j] != s[j]:
				flag = False
				break
		if flag == True:
			return n
		else:
			n += 2 ** (len(ans) - 1)