25. Обработка целочисленной информации: все задания

Так как нужны только числа, делящиеся на $2023$, будем перебирать не все числа до $10^8$, а только кратные $2023$.

Для проверки соответствия маске удобно использовать функцию fnmatch.

from fnmatch import fnmatch

for x in range(2023, 10**8 + 1, 2023):
    if fnmatch(str(x), '1*23?9'):
        print(x, x // 2023)

Функция fnmatch проверяет, соответствует ли запись числа заданной маске:

? — одна произвольная цифра;
* — любое количество цифр, в том числе $0$.

Программа выведет:

В маске $1234?57?8$ находятся два символа ?, каждый из которых обозначает одну произвольную цифру. Поэтому достаточно перебрать по $10$ вариантов для каждой неизвестной цифры, то есть всего $100$ чисел.

for a in range(10):
    for b in range(10):
        x = int(f'1234{a}57{b}8')
        if x % 19 == 0:
            print(x, x // 19)

Переменные a и b принимают значения от $0$ до $9$ и подставляются вместо символов ?. Для каждого полученного числа проверяем делимость на $19$.

Программа выведет:

Так как нужны только числа, делящиеся на $1917$, будем перебирать не все числа до $10^{10}$, а только кратные $1917$.

Для проверки соответствия маске удобно использовать функцию fnmatch.

from fnmatch import fnmatch

for x in range(1917, 10**10 + 1, 1917):
    if fnmatch(str(x), '3?12?14*5'):
        print(x, x // 1917)

Функция fnmatch проверяет, соответствует ли запись числа заданной маске:

? — одна произвольная цифра;
* — любое количество цифр, в том числе $0$.

Программа выведет:

Будем последовательно перебирать числа, начиная с $500,001$. Для каждого числа найдём все делители, кроме $1$ и самого числа, и вычислим их сумму $R$.

Делители достаточно искать до $\sqrt n$: если $d$ является делителем числа $n$, то вторым делителем пары будет $\dfrac{n}{d}$.

def f(n):
    s = 0
    d = 2

    while d * d <= n:
        if n % d == 0:
            s += d
            if d != n // d:
                s += n // d
        d += 1

    return s


n = 500001
k = 0

while k < 5:
    r = f(n)

    if r % 10 == 7:
        print(n, r)
        k += 1

    n += 1

Функция f(n) вычисляет сумму $R$ всех различных делителей числа $n$, кроме $1$ и самого числа.

Условие r % 10 == 7 проверяет, что значение $R$ оканчивается на цифру $7$.

Программа выведет:

В маске $12345?7?8$ находятся два символа ?, каждый из которых обозначает одну произвольную цифру. Поэтому переберём все возможные значения этих двух цифр и проверим полученные числа на делимость на $23$.

for a in range(10):
    for b in range(10):
        x = int(f'12345{a}7{b}8')
        if x % 23 == 0:
            print(x, x // 23)

Переменные a и b принимают значения от $0$ до $9$ и подставляются вместо символов ?.

Условие x % 23 == 0 проверяет, делится ли полученное число на $23$ без остатка.

Программа выведет:

Будем перебирать числа, начиная с $500,001$. Для каждого числа найдём сумму всех его натуральных делителей.

Делители достаточно искать до $\sqrt n$: если $d$ является делителем числа $n$, то вместе с ним существует парный делитель $\dfrac{n}{d}$.

def f(n):
    s = 0

    for d in range(1, int(n ** 0.5) + 1):
        if n % d == 0:
            s += d

            if d != n // d:
                s += n // d

    return s


n = 500001
k = 0

while k < 5:
    r = f(n)

    if r % 10 == 6:
        print(n, r)
        k += 1

    n += 1

Функция f(n) вычисляет сумму $R$ всех различных натуральных делителей числа $n$.

Условие r % 10 == 6 проверяет, что значение $R$ оканчивается на цифру $6$.

Программа выведет:

Так как нужны только числа, делящиеся на $1991$, будем перебирать не все числа до $10^8$, а только кратные $1991$.

Для проверки соответствия маске удобно использовать функцию fnmatch.

from fnmatch import fnmatch

for x in range(1991, 10**8 + 1, 1991):
    if fnmatch(str(x), '2*1?71'):
        print(x, x // 1991)

Функция fnmatch проверяет, соответствует ли запись числа заданной маске:

? — одна произвольная цифра;
* — любое количество цифр, в том числе $0$.

Программа выведет:

Для каждого числа найдём его минимальный делитель $d$, не равный $1$. Тогда максимальный делитель, не равный самому числу, равен $\dfrac{n}{d}$.

Поэтому: $M=d+\dfrac{n}{d}$. Если делителей нет, число простое и $M=0$.

from math import isqrt

def f(n):
    for d in range(2, isqrt(n) + 1):
        if n % d == 0:
            return d + n // d
    return 0


n = 452022
k = 0

while k < 5:
    m = f(n)

    if m % 7 == 3:
        print(n, m)
        k += 1

    n += 1

Функция f(n) находит минимальный делитель числа $n$. Парный ему делитель $n//d$ будет максимальным собственным делителем числа.

Условие m % 7 == 3 проверяет, что значение $M$ при делении на $7$ даёт остаток $3$.

Программа выведет:

Для каждого числа найдём его минимальный делитель $d$, не равный $1$. Тогда максимальный делитель, не равный самому числу, равен $\dfrac{n}{d}$.

Поэтому: $M=d+\dfrac{n}{d}$. Если делителей нет, число простое и $M=0$.

from math import isqrt

def f(n):
    for d in range(2, isqrt(n) + 1):
        if n % d == 0:
            return d + n // d
    return 0


n = 700001
k = 0

while k < 5:
    m = f(n)

    if m % 10 == 8:
        print(n, m)
        k += 1

    n += 1

Функция f(n) находит минимальный делитель числа $n$. Парный ему делитель n // d будет максимальным собственным делителем числа.

Условие m % 10 == 8 проверяет, что значение $M$ оканчивается на цифру $8$.

Программа выведет:

Так как нужны только числа, делящиеся на $273$, будем перебирать не все числа до $10^8$, а только кратные $273$.

Для проверки соответствия маске удобно использовать функцию fnmatch.

from fnmatch import fnmatch

for x in range(273, 10**8 + 1, 273):
    if fnmatch(str(x), '12??15*6'):
        print(x, x // 273)

Функция fnmatch проверяет, соответствует ли запись числа заданной маске:

? — одна произвольная цифра;
* — любое количество цифр, в том числе $0$.

Программа выведет:

Для каждого числа найдём все его делители. Достаточно перебирать делители до $\sqrt n$: если $d$ является делителем числа $n$, то вторым делителем пары будет $\dfrac{n}{d}$.

Среди подходящих делителей выбираем минимальный, который оканчивается на $9$, не равен $9$ и не равен самому числу.

from math import isqrt

def f(n):
    a = []

    for d in range(1, isqrt(n) + 1):
        if n % d == 0:
            if d % 10 == 9 and d != 9 and d != n:
                a.append(d)

            k = n // d
            if k % 10 == 9 and k != 9 and k != n:
                a.append(k)

    if a:
        return min(a)
    return 0


n = 500001
k = 0

while k < 5:
    d = f(n)

    if d != 0:
        print(n, d)
        k += 1

    n += 1

Функция f(n) находит минимальный натуральный делитель числа $n$, который оканчивается на цифру $9$, но не равен $9$ и самому числу.

Если подходящих делителей нет, функция возвращает $0$.

Программа выведет:

Так как $M$ должно быть простым числом больше $110,000$, оно нечётное. Если исходное число нечётное, его минимальный и максимальный простые делители также нечётные, поэтому их сумма будет чётной. Значит, подходящее число обязательно чётное.

Следовательно, минимальный простой делитель равен $2$, и $M=2+\text{максимальный простой делитель}$.

Будем перебирать только чётные числа и находить их максимальный простой делитель.

def prime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2

    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d += 2

    return True


def max_div(n):
    m = 0

    while n % 2 == 0:
        m = 2
        n //= 2

    d = 3
    while d * d <= n:
        while n % d == 0:
            m = d
            n //= d
        d += 2

    if n > 1:
        m = max(m, n)

    return m


n = 8007524670
k = 0

while k < 5:
    d = max_div(n)
    M = 2 + d

    if M > 110000 and prime(M) and str(M).count('991') == 1:
        print(n, M)
        k += 1

    n += 2

Функция max_div(n) находит максимальный простой делитель числа $n$.

Условие str(M).count(‘991’) == 1 проверяет, что последовательность цифр $991$ встречается в записи числа $M$ ровно один раз.

Программа выведет:

Так как нужны только числа, делящиеся на $1927$, будем перебирать не все числа до $10^8$, а только кратные $1927$.

Для проверки соответствия маске удобно использовать функцию fnmatch.

from fnmatch import fnmatch

for x in range(1927, 10**8 + 1, 1927):
    if fnmatch(str(x), '1?3*4?9'):
        print(x, x // 1927)

Функция fnmatch проверяет, соответствует ли запись числа заданной маске:

? — одна произвольная цифра;
* — любое количество цифр, в том числе $0$.

Программа выведет:

Если число представимо в виде произведения двух простых множителей $p\cdot q$, то достаточно найти его первый делитель $p$. Он будет простым. После этого проверяем, что $q=\dfrac{n}{p}$ тоже является простым числом и оба множителя содержат последовательность 67 ровно один раз.

from math import isqrt

def prime(n):
    if n < 2:
        return False
    for d in range(2, isqrt(n) + 1):
        if n % d == 0:
            return False
    return True


def f(n):
    for d in range(2, isqrt(n) + 1):
        if n % d == 0:
            q = n // d

            if (prime(q) and
                str(d).count('67') == 1 and
                str(q).count('67') == 1):
                return d

            return 0

    return 0


n = 2626695892
k = 0

while k < 5:
    d = f(n)

    if d != 0:
        print(n, d)
        k += 1

    n += 1

Функция f(n) находит первый делитель числа $n$. Если второй множитель тоже прост и в записи каждого множителя последовательность 67 встречается ровно один раз, функция возвращает меньший множитель.

Программа выведет:

В маске $12345?7?8$ находятся два символа ?, каждый из которых обозначает одну произвольную цифру. Поэтому переберём все возможные значения этих двух цифр и проверим полученные числа на делимость на $37$.

for a in range(10):
    for b in range(10):
        x = int(f'12345{a}7{b}8')
        if x % 37 == 0:
            print(x, x // 37)

Переменные a и b принимают значения от $0$ до $9$ и подставляются вместо символов ?.

Условие x % 37 == 0 проверяет, делится ли полученное число на $37$ без остатка.

Программа выведет:

Так как нужны только числа, делящиеся на $9874$, будем перебирать не все числа до $10^{10}$, а только кратные $9874$.

Для проверки соответствия маске удобно использовать функцию fnmatch.

from fnmatch import fnmatch

for x in range(9874, 10**10 + 1, 9874):
    if fnmatch(str(x), '89*6?7?9?'):
        print(x, x // 9874)

Функция fnmatch проверяет, соответствует ли запись числа заданной маске:

? — одна произвольная цифра;
* — любое количество цифр, в том числе $0$.

Программа выведет:

Если исходное число нечётное, то его минимальный и максимальный простые делители нечётные. Их сумма $M$ будет чётной. Так как $M>80,000$ и должно быть простым, такие числа нам не подходят.

Значит, перебираем только чётные числа. Для них минимальный простой делитель равен $2$, поэтому $M=2+\text{максимальный простой делитель}$.

from math import isqrt

def prime(n):
    if n < 2:
        return False
    for d in range(2, isqrt(n) + 1):
        if n % d == 0:
            return False
    return True


def max_div(n):
    m = 2

    while n % 2 == 0:
        n //= 2

    d = 3
    while d * d <= n:
        if n % d == 0:
            m = d
            while n % d == 0:
                n //= d
        d += 2

    if n > 1:
        m = max(m, n)

    return m


n = 8007494156
k = 0

while k < 5:
    M = 2 + max_div(n)

    if M > 80000 and str(M).count('567') == 1 and prime(M):
        print(n, M)
        k += 1

    n += 2

Функция max_div(n) находит максимальный простой делитель числа $n$.

Условие str(M).count(‘567’) == 1 проверяет, что последовательность цифр $567$ встречается в записи $M$ ровно один раз.

Программа выведет:

Для каждого числа найдём все пары делителей. Достаточно перебирать делители до $\sqrt n$: если $d$ делит число $n$, то второй делитель пары равен $\dfrac{n}{d}$.

Среди всех подходящих делителей выбираем минимальный, который оканчивается на цифру $9$ и не равен $9$ и самому числу.

from math import isqrt

def f(n):
    a = []

    for d in range(1, isqrt(n) + 1):
        if n % d == 0:
            if d % 10 == 9 and d != 9 and d != n:
                a.append(d)

            k = n // d
            if k % 10 == 9 and k != 9 and k != n:
                a.append(k)

    if a:
        return min(a)
    return 0


n = 600001
k = 0

while k < 5:
    d = f(n)

    if d != 0:
        print(n, d)
        k += 1

    n += 1

Функция f(n) находит минимальный натуральный делитель числа $n$, который оканчивается на цифру $9$, но не равен $9$ и самому числу.

Если подходящих делителей нет, функция возвращает $0$.

Программа выведет:

Если число имеет вид $n=p\cdot q$, где $p$ и $q$ — простые числа, то достаточно найти наименьший делитель $p$. После этого проверяем, что второй множитель $q=\dfrac{n}{p}$ тоже является простым числом и каждый из множителей содержит 43 ровно один раз.

from math import isqrt

def prime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2

    for d in range(3, isqrt(n) + 1, 2):
        if n % d == 0:
            return False

    return True


def f(n):
    if n % 2 == 0:
        p = 2
    else:
        p = 0

        for d in range(3, isqrt(n) + 1, 2):
            if n % d == 0:
                p = d
                break

        if p == 0:
            return 0

    q = n // p

    if (str(p).count('43') == 1 and
        str(q).count('43') == 1 and
        prime(q)):
        return p

    return 0


n = 2018974448
k = 0

while k < 5:
    d = f(n)

    if d != 0:
        print(n, d)
        k += 1

    n += 1

Функция f(n) находит наименьший простой множитель числа $n$. Затем проверяется, что второй множитель тоже простой и последовательность 43 встречается в каждом множителе ровно один раз.

Программа выведет:

Так как нужны только числа, делящиеся на $1921$, будем перебирать не все числа до $10^8$, а только кратные $1921$.

Для проверки соответствия маске удобно использовать функцию fnmatch.

from fnmatch import fnmatch

for x in range(1921, 10**8 + 1, 1921):
    if fnmatch(str(x), '2*1?5?1'):
        print(x, x // 1921)

Функция fnmatch проверяет, соответствует ли запись числа заданной маске:

? — одна произвольная цифра;
* — любое количество цифр, в том числе $0$.

Программа выведет: