# 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)!

Difficulty: interview

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


# both approaches work because a and m are relatively prime:
# a is a power of 3 while m is a power of 2

# Since a and m are coprime, a^(phi(m)) = 1 (mod m), where phi(m) is the Euler totient function
# if m is a power of 2, phi(m) = m/2
# then, diving the above equation by a we get: a^(-1) = a^(phi(m)-1) (mod m),
# which is our multiplicative inverse
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):
    # The fraction we get after applying all the steps is of the form
    # (a*x + b)/m, where x is a number such that the later division results in
    # an integer, a = 3^(#'U'), m = 2^(len(steps)) and b[i] = b[i-1] if 'D' else 3*b[i-1] + 2^i
    a, b, m = 1, 0, 1
    for i, s in enumerate(steps):
        m *= 2
        if s == 'U':
            a *= 3
            b = 3*b + 2**i
    
    # a*x + b = 0 (mod m) (=) a*x = -b (mod m) (=) x = a^(-1)*(-b) (mod m)
    # a^(-1) is the modular multiplicative inverse of a mod m: it is the number y such that
    # a*y = 1 (mod m)
    # It will be calculated using the Extend Euclid's Algorithm
    x = (-b * ModInv(a, m)) % m
    # So the number is between n-m and n+m:
    x += m * (n//m)
    # So the number is greater than n:
    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
        else:
            if(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


def egcd(a, b):
    if a == 0:
        return 0, 1
    y, x = egcd(b % a, a)
    return x - (b//a) * y, y
    

def modinv(a, m):
    x, y = egcd(a, m)
    return x & (m-1)


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
    while p < n:
        p += z
    return p


import math

def ModularInverse(a, b):
  #Use Euclidean algorithm, storing coefficients of each step
  coeffs = []
  while b > 0:
    coeffs.append(math.floor(a/b))
    a, b = b, a % b
  #Iterate back through all coefficients to construct coefficients for initial a and b
  c1 = 1
  c2 = 0
  for co in coeffs[::-1]:
    c1, c2 = c2, c1-co*c2
  return c2

def collatz_steps(n, steps):
  # Applying all U/D steps and simplifying results in...
  # (ax + b)/m is an integer, where 
  # a = 3 ^ (# of U in steps)
  # b = f(#steps-1) where
  #   f(-1) = 0
  #   f(i)=3f(i-1)+2^i when steps[i]==U
  #   f(i)=f(i-1)      when steps[i]==D
  # m = 2 ^ (#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
  # Thus,
  # ax = -b mod m
  #  x = -ba^-1 mod m
  #  x = -ba^-1 + mC
  # Choose C such that n-m < x < n+m
  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):
  # ax = b mod m
  # a = 3 ^ (# of U in steps)
  # b = -f(#steps-1) where
  #   f(-1) = 0
  #   f(i)=3f(i-1)+2^i when steps[i]==U
  #   f(i)=f(i-1)      when steps[i]==D
  # m = 2 ^ (#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)
  # ax = b mod m
  a = a % m
  #  x = ba^-1 mod 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 = ba^-1 + mC
  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):    
    """
    The numbers of the kind N = start + k * interval_start are the numbers N which generate the
    sequence :steps: when used as start for the collatz sequence.    
    The numbers of the kind N = end + K * interval_end are the numbers N which result of applying
    the collatz sequence after some steps of :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)