Натуральный ряд Ограничение по времени: 1 1 секунда Ограничение по памяти: 256 256 мегабайт В научно‑исследовательском институте, где работает Тимофей, продолжается успешное исследование ряда натуральных чисел. Каждый день его коллеги открывают всё новые и новые свойства этой последовательности, и Тимофей старается от них не отставать. Сегодня Тимофей, как обычно, выписал на доске в ряд натуральные числа. Потом пришёл начальник отдела и стёр все числа, делящиеся на 2 2 . Потом пришёл начальник другого отдела и стёр все числа из оставшихся, делящиеся на 3 3 . Какое число теперь стоит на n � -м месте в списке? Формат входных данных Единственная строка входных данных содержит натуральное число n � (1≤n≤109 1 ≤ � ≤ 10 9 ). Формат выходных данных Выведите одно натуральное число — — ответ на вопрос задачи. Обратите внимание, что при заданных ограничениях для хранения входных данных и ответа может понадобиться 64 64 ‑битный тип данных, например, long long в C++, int64 64 в Free Pascal, long в Java. Система оценки Решения, верно работающие при 1≤n≤105 1 ≤ � ≤ 10 5 , получат не менее 40 40 баллов. Замечание В примере дано n=5 � = 5 . Из исходного ряда натуральных чисел 1 1 , 2 2 , 3 3 , 4 4 , 5 5 , 6 6 , 7 7 , 8 8 , 9 9 , 10 10 , 11 11 , 12 12 , 13 13 , 14 14 , 15 15 , … … сначала были удалены числа 2 2 , 4 4 , 6 6 , 8 8 , … … (как делящиеся на 2 2 ). Остался ряд 1 1 , 3 3 , 5 5 , 7 7 , 9 9 , 11 11 , 13 13 , 15 15 , … … Потом из него были удалены числа 3 3 , 9 9 , 15 15 , … … (как делящиеся на 3 3 ). Остался ряд 1 1 , 5 5 , 7 7 , 11 11 , 13 13 , … … На пятом месте число 13 13 . Ввод Вывод 5 13 Код Python 3 keyboard_arrow_down Код из файла

Чтобы решить эту задачу, нам нужно понять, как формируется новый ряд натуральных чисел после удаления чисел, делящихся на 2 и 3.

Прежде всего, давайте разберемся, как происходит отбор чисел. Исходный ряд натуральных чисел выглядит так: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 и т.д.

1. Удаление чисел, делящихся на 2: После этого удаления остаются только нечетные числа:

   • 1, 3, 5, 7, 9, 11, 13, ...

2. Удаление чисел, делящихся на 3: Из оставшихся чисел удаляются также те, которые делятся на 3:

   • 1, 5, 7, 11, 13, ...

Теперь, чтобы найти n-е число в этом новом ряде, можно воспользоваться тем, что оставшиеся числа — это все нечетные числа, не делящиеся на 3.

Для нахождения n-го числа в этом ряду, давайте проанализируем, как они расположены.

Нечетные числа располагаются по формуле \(2k + 1\), где \(k\) — это неотрицательное целое число (0, 1, 2, ...).

Затем нам нужно определить, делится ли \(2k + 1\) на 3. Если число \(2k + 1\) делится на 3, то мы его пропускаем.

В итоге:

• Для каждого \(k\), если \(2k + 1\) делится на 3, это число не должно быть включено.
• Если \(2k + 1\) не делится на 3, оно добавляется в ряд.

Нам необходимо знать, сколько чисел мы пропускаем. Для любого числа \(x\):

• Общее количество нечетных чисел от 1 до \(x\) равно \(\left\lfloor \frac{x+1}{2} \right\rfloor\).
• Количество нечетных чисел от 1 до \(x\), которые делятся на 3, равно \(\left\lfloor \frac{x}{6} \right\rfloor\) (поскольку каждый шестой элемент среди натуральных чисел — это нечетное число, делящееся на 3).

Таким образом, количество чисел в последовательности до \(x\) будет: \[ \text{count} = \left\lfloor \frac{x + 1}{2} \right\rfloor - \left\lfloor \frac{x}{6} \right\rfloor \] Нам нужно найти такое \(x\), чтобы количество нечетных чисел, не делящихся на 3, равно \(n\).

Алгоритм

1. Инициализируем переменную \(x\) с некоторым значением и устанавливаем переменную для хранения текущего счетчика.
2. Последовательно проверяем каждое нечетное число, увеличивая счетчик для тех, которые не делятся на 3, пока не дойдём до \(n\).

Вот реализация этого алгоритма на Python:

n = int(input())

# Ищем n-е нечетное число, не делящееся на 3
count = 0
x = 0

while True:
    x += 1
    if x % 2 == 1 and x % 3 != 0:  # x - нечетное и не делится на 3
        count += 1
    if count == n:
        print(x)
        break

Запустив этот код, мы сможем найти n-е число в искомом ряду.