Question

Найдите сумму всех положительных несократимых дробей видаn/1001, не превосходящих 2

Answer 1

По условию, нужно найти сумму несократимых дробей вида $\dfrac{n}{1001}$, это означает, что числа $n$ и 1001 - взаимно простые.

$S=\left\sum\dfrac{n}{1001}\right|0$

Разложим число 1001 на простые множители:

$1001=7\cdot11\cdot13$

Рассмотрим искомую сумму, без учета условия о несократимости дроби $\dfrac{n}{1001}$. Тогда получим:

$S^*=\dfrac{1}{1001} +\dfrac{2}{1001} +\dfrac{3}{1001} +\ldots+2$

$S^*=\dfrac{1}{1001} +\dfrac{2}{1001} +\dfrac{3}{1001} +\ldots+\dfrac{2002}{1001}$

$S^*=\dfrac{1+2+3+\ldots+2002}{1001}$

Задача сводится к нахождению суммы $1+2+3+\ldots+2002$. Но мы помним, что на самом деле нас интересует сумма только тех чисел от 1 до 2002, которые являются взаимно простыми с числом 1001.

Найдем количество чисел от 1 до 2002, которые не являются взаимно простыми с числом 1001. По отношению к делимости на делители числа 1001, то есть на 7, 11, 13 все такие числа можно разделить на несколько групп:

- делятся на 7, но не делятся на 11, 13;

- делятся на 11, но не делятся на 7, 13;

- делятся на 13, но не делятся на 7, 11;

- делятся на 7, 11, но не делятся на 13;

- делятся на 7, 13, но не делятся на 11;

- делятся на 11, 13, но не делятся на 7;

- делятся на 7, 11, 13.

Количества таких чисел соответственно равно:

$D_7=\dfrac{2002}{7} =286$

$D_{11}=\dfrac{2002}{11} =182$

$D_{13}=\dfrac{2002}{13} =154$

$D_{7,11}=\dfrac{2002}{7\cdot11} =26$

$D_{7,13}=\dfrac{2002}{7\cdot13} =22$

$D_{11,13}=\dfrac{2002}{11\cdot13} =14$

$D_{7,11,13}=\dfrac{2002}{7\cdot11\cdot13} =2$

Найти итоговое количество чисел, не взаимно простых с 1001 можно по формуле включений-исключений, которая запишется в виде:

$D=(D_7+D_{11}+D_{13})-(D_{7,11}+D_{7,13}+D_{11,13})+D_{7,11,13}$

Формула подразумевает, что числа, имеющие два делителя из набора (7, 11, 13) были посчитаны среди первых трех слагаемых дважды, поэтому их необходимо один раз отнять. В свою очередь числа, делящиеся на каждое число набора (7, 11, 13) были посчитаны 3 раза со знаком "плюс" и 3 раза со знаком "минус", поэтому их необходимо отдельно прибавить.

$D=(286+182+154)-(26+22+14)+2=562$

Тогда, количество чисел, взаимно простых с 1001:

$\overline{D}=2002-D$

$\overline{D}=2002-562=1440$

Составим следующую конструкцию. запишем числа от 1 до 2002 в столбик, а точнее для дальнейшего удобства - от 0 до 2002:

$\begin{array}{ccc}0\\1\\2\\3\\\ldots\\2002\end{array}$

Во второй столбик запишем те же самые числа в обратном порядке:

$\begin{array}{ccc}0&2002\\1&2001\\2&2000\\3&1999\\\ldots&\ldots\\2002&0\end{array}$

Заметим, что сумма чисел в каждой строчке равна 2002.

Нетрудно понять, что два числа в одной строчке либо оба делятся на 7 (аналогично, на 11, на 13), либо оба не делятся. Поскольку 2002 делится на 7, то делимость первого числа в строчке гарантирует делимость второго числа и наоборот.

Тогда, вычеркнем из нашей таблицы 562 строчки, в которых первое число (а значит и второе тоже) не является взаимно простым с числом 1001. Вычеркнем также первую вспомогательную строчку (0-2002).

В таблице останется как было определено ранее 1440 чисел в каждом из столбцов. Поскольку мы знаем суммы чисел в каждой строчке, то легко определяется сумма всех чисел в таблице:

$S_t=1440\cdot2002$

Заметим, что в таблице записан двойной набор тех чисел, что нам нужно сложить в числителе искомой величины.

Тогда:

$S=\dfrac{1440\cdot2002}{2\cdot1001} =1440$

Ответ: 1440

Answer 2

Для нахождения суммы всех положительных несократимых дробей вида n/1001, не превосходящих 2, мы можем следовать следующему алгоритму:

1. Рассмотрим все числа n от 1 до 1000 (так как 1001 = 7 * 11 * 13, и несократимые дроби не могут иметь делителей, кроме 1 и самих себя).

2. Для каждого числа n проверим, является ли оно взаимно простым с 1001 (то есть, не имеет общих делителей с 1001, кроме 1).

3. Если число n взаимно просто с 1001, то оно может быть использовано в несократимой дроби n/1001. Проверим также, что n/1001 не превосходит 2.

4. Если условия выполняются, добавим n/1001 к сумме.

Вот код на Python, который выполняет этот алгоритм:

pythonCopy code
import math

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# Инициализация суммы
sum_of_fractions = 0

# Проходим по числам от 1 до 1000
for n in range(1, 1001):
    # Проверяем, является ли n взаимно простым с 1001
    if gcd(n, 1001) == 1:
        # Вычисляем дробь n/1001
        fraction = n / 1001
        # Проверяем, что дробь не превосходит 2
        if fraction <= 2:
            # Добавляем дробь к сумме
            sum_of_fractions += fraction

print(sum_of_fractions)

Этот код вычислит сумму всех положительных несократимых дробей вида n/1001, не превосходящих 2.