Что нужно сделать, чтобы выводилось число кратное сгенерированному?

Есть задание ЕГЭ по информатике, у него одно условие, но разные значения:

Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1.  Строится двоичная запись числа N. 2.  Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется та цифра, которая встречается реже. 3.  Шаг 2 повторяется ещё два раза 4.  Результат переводится в десятичную систему.

Пример. Дано число N  =  19. Алгоритм работает следующим образом: 1.  Двоичная запись числа N: 10011. 2.  В полученной записи нулей меньше, чем единиц, в конец записи добавляется 0. Новая запись: 100110. 3.  В текущей записи нулей и единиц поровну, в конец записывается последняя цифра, это 0. Получается 1001100. В этой записи единиц меньше, в конец добавляется 1: 10011001. 4.  Результат работы алгоритма R  =  153. При каком наименьшем числе N > "x" в результате работы алгоритма получится число, кратное "k"?

Вот мой недоделанный код:

import random

x = random.randint(40, 100)
k = random.randint(2, 5)


print("Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:")
print("1. Строится двоичная запись числа N.")
print("2. Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется та цифра, которая встречается реже.")
print("3. Шаг 2 повторяется ещё два раза")
print("4. Результат переводится в десятичную систему.")
print("Пример. Дано число N = 19. Алгоритм работает следующим образом:")
print("1. Двоичная запись числа N: 10011.")
print("2. В полученной записи нулей меньше, чем единиц, в конец записи добавляется 0. Новая запись: 100110.")
print("3. В текущей записи нулей и единиц поровну, в конец записывается последняя цифра, это 0. Получается 1001100. В этой записи единиц меньше, в конец добавляется 1: 10011001.")
print("4. Результат работы алгоритма R = 153.")
print("\nПри каком наименьшем числе N > {} в результате работы алгоритма получится число, кратное {}?".format(x, k))

for n in range(x + 1, 1000):
    s = bin(n)[2:]  # перевод в двоичную систему
    zeroes = s.count("0")
    ones = s.count("1")
    if zeroes == ones:
        s += s[-1]
    elif zeroes > ones:
        s += "1"  # добавляем 1 в конец записи, если нулей больше единиц
    else:
        s += "0"  # добавляем 0 в конец записи, если единиц больше нулей
    r = int(s, 2)  # перевод в десятичную систему
    if r % k == 0:
        print(n)
        break

Проблема заключается в том, что при генерации чисел x и k, программа выводит число n, не кратное k, например: При каком наименьшем числе N > 49 в результате работы алгоритма получится число, кратное 4? 50

Что нужно исправить, чтобы генерация была нормальной и вывод был кратный сгенерированному k?

Изменено: Добавил ещё один цикл, совершающий второй шаг трижды(т.к. в 3-м пункте нужно повторить 2-й пункт), но выводит всё равно не кратное число:

import random

x = random.randint(40, 100)
k = random.randint(2, 5)

print("Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:")
print("1. Строится двоичная запись числа N.")
print("2. Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется та цифра, которая встречается реже.")
print("3. Шаг 2 повторяется ещё два раза")
print("4. Результат переводится в десятичную систему.")
print("Пример. Дано число N = 19. Алгоритм работает следующим образом:")
print("1. Двоичная запись числа N: 10011.")
print("2. В полученной записи нулей меньше, чем единиц, в конец записи добавляется 0. Новая запись: 100110.")
print("3. В текущей записи нулей и единиц поровну, в конец записывается последняя цифра, это 0. Получается 1001100. В этой записи единиц меньше, в конец добавляется 1: 10011001.")
print("4. Результат работы алгоритма R = 153.")
print("\nПри каком наименьшем числе N > {} в результате работы алгоритма получится число, кратное {}?".format(x, k))

def count_digits(s):
    zeroes = s.count("0")
    ones = s.count("1")
    return zeroes, ones

def add_digit(s, digit):
    s += digit
    return s

def binary_to_decimal(s):
    decimal = int(s, 2)
    return decimal

for n in range(x + 1, 1000):
    s = bin(n)[2:]  # перевод в двоичную систему
    
    for _ in range(3):    
        zeroes, ones = count_digits(s)
        
        if zeroes == ones:
            s = add_digit(s, s[-1])
        elif zeroes > ones:
            s = add_digit(s, "1")
        else:
            s = add_digit(s, "0")
    
    r = binary_to_decimal(s)  # перевод в десятичную систему
    if r % k == 0:
        print(n)
        break