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

Будем последовательно перебирать числа, начиная с $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$.

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

Будем перебирать числа, начиная с $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$.

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

Для каждого числа найдём его минимальный делитель $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$.

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

Для каждого числа найдём все его делители. Достаточно перебирать делители до $\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$ ровно один раз.

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

Если число представимо в виде произведения двух простых множителей $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 встречается ровно один раз, функция возвращает меньший множитель.

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

Если исходное число нечётное, то его минимальный и максимальный простые делители нечётные. Их сумма $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 встречается в каждом множителе ровно один раз.

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

Для каждого числа найдём его минимальный делитель $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 = 800001
k = 0

while k < 5:
    m = f(n)

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

    n += 1

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

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

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

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

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

from math import isqrt

def f(n):
    a = []

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

            k = n // d
            if k % 10 == 8 and k != 8 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$, который оканчивается на цифру $8$, но не равен $8$ и самому числу.

Если подходящих делителей нет, функция возвращает $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 = 900001
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$.

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

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

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

from math import isqrt

def f(n):
    s = 0

    for d in range(2, isqrt(n) + 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 == 9:
        print(n, r)
        k += 1

    n += 1

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

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

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

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

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

from math import isqrt

def f(n):
    s = 0

    for d in range(2, isqrt(n) + 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 == 1:
        print(n, r)
        k += 1

    n += 1

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

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

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