Известно что n натуральное число является ли четным числом

Известно что n натуральное число является ли четным числом

Пусть S(n) и K(n) обозначают сумму всех цифр и сумму квадратов всех цифр натурального числа n соответственно.

а) Существует ли такое натуральное число n, что K(n) = 2S(n) + 23?

б) Существует ли такое натуральное число n, что K(n) = 3S(n) + 23?

в) Для какого наименьшего натурального числа n выполнено равенство K(n) = 8S(n) + 83?

а) Такое число существует. Например, при n = 16 имеем S(n) = 7 и K(n) = 37 = 2 ∙ 7 + 23.

б) Предположим, что такое число существует. Тогда если число S(n) чётное, то число K(n) = 3S(n) + 23 нечётное. Если же число S(n) нечётное, то число K(n) = 3S(n) + 23 чётное. С другой стороны, любая цифра и её квадрат имеют одинаковую чётность (то есть чётны или нечётны одновременно). Значит, S(n) и K(n) также имеют одинаковую чётность. Пришли к противоречию.

в) Пусть n — искомое число, m — количество всех девяток в десятичной записи числа n. Тогда сумма всех отличных от девятки цифр числа n равна S(n) – 9m, а сумма их квадратов не более 8(S(n) – 9m). Значит, 8S(n) + 83 = K(n) ≤ 81m + 8(S(n) – 9m) = 8S(n) + 9m. Следовательно, m ≥ 10.

Поскольку искомое число n является наименьшим натуральным из удовлетворяющих равенству K(n) = 8S(n) + 83, среди его цифр нет нулей (иначе их можно было бы вычеркнуть) и все его цифры расположены по возрастанию (иначе перестановкой цифр n можно было бы уменьшить). Значит, все девятки в десятичной записи числа n стоят в конце.

Из равенства K(n) = 8S(n) + 83 следует, что либо S(n), либо K(n) не делится на 9 и в числе n есть отличные от девяток цифры. Поэтому n ≥ 19 999 999 999. При этом K(19 999 999 999) = 811 = 8 ∙ 91 + 83 = 8S(19 999 999 999) + 83. Значит, число n = 19 999 999 999 и есть искомое.

Ответ: а) да; б) нет; в) 19 999 999 999.

Аналоги к заданию № 520501: 520521 520664 520705 Все

Источник

Известно что n натуральное число является ли четным числом

а) Существует ли такое натуральное число n, что числа n 2 и (n + 17) 2 имеют одинаковые остатки при делении на 69?

б) Существует ли такое натуральное число n, что числа n 2 и (n + 17) 2 имеют одинаковые остатки при делении на 68?

в) Пусть k(m) — количество трехзначных натуральных чисел n, таких, что числа n 2 и (n + m) 2 имеют одинаковые остатки при делении на 68, причем m — двузначное натуральное число. Определите наименьшее значение k, отличное от нуля.

а) Разность этих чисел равна

Если выбрать n так, чтобы (то есть ), то полученное число будет кратно 69, а изначальные два будут давать одинаковые остатки от деления на 68.

б) Одно из этих чисел четно, а другое нечетно. Значит, они не могут давать одинаковые остатки от деления на четное число.

в) Как и в пункте а) получим, что кратно 68. Если m нечетно, то это произведение двух нечетных чисел и оно не кратно 68. Пусть тогда

кратно 68. То есть кратно 17. Если x кратно 17, то все такие числа кратны 17, что нам невыгодно. Значит, кратно 17. Подходящие n попадаются через каждые 17 чисел. В качестве x можно выбирать числа от 5 до 49 (поскольку 2x — двузначное число).

Среди чисел от 100 до 984 ровно 52 числа с каждым остатком от деления на 17. А среди чисел от 985 до 999 нет, например, числа с остатком 14 (таким числом было бы 1000). Поэтому если выбрать (то есть ), то будет 52 подходящих числа.

Источник

Известно что n натуральное число является ли четным числом

Для любого натурального числа n (n ≥ 1) обозначим через O(n) количество нечётных цифр в десятичной записи этого числа. Например, O(123) = 2, а O(2048) = 0.

а) Существует ли такое натуральное число n, что O(4 · n) = O(n) + 2?

б) Существует ли такое натуральное число n, что O(5 n + 2 n + 1 − 2) > n?

в) Для какого наименьшего натурального числа n выполнено равенство O(11 · n) = O(n) + 2?

а) Да. Например, при n = 44 имеем

б) Для любого натурального n имеем так как

Значит, в числе не более n цифр. Следовательно, и искомого значения n не существует.

Если 10 ≤ n ≤ 19 и n чётно, то O(n) = 1, а число 11 · n чётное и трёхзначное. Отсюда получаем, что в этом случае

Если 10 ≤ n ≤ 19 и n нечётно, O(n) = 2, а число 11 · n трёхзначное. Отсюда получаем, что в этом случае

Если 20 ≤ n ≤ 27 и n чётно, то все цифры чисел n и 11 · n также чётные. Отсюда получаем, что в этом случае

Если 20 ≤ n ≤ 27 и n нечётно, то 200

Значит, искомое наименьшее значение n равно 29.

Источник

Закономерности в распределении простых чисел

Введение

Простое число — это натуральное число, имеющее ровно два различных натуральных делителя — единицу и самого себя. Такие числа представляют огромный интерес. Дело в том, что никто так и не смог полностью понять и описать закономерность по которой простые числа располагаются в ряду натуральных чисел.

Ещё до нашей эры Евклид сформулировал и доказал первые теоремы о простых числах. С тех пор математики, среди них Гаусс, Ферма, Риман, Эйлер, продолжали исследования и надо отдать им должное заметно продвинулись. Было обнаружено много интересных свойств простых чисел, выдвинуто много предположений, некоторые из которых были доказаны. Однако много гипотез связанных с простыми числами до сих пор остаются необоснованными.

Распределение простых чисел

Первостепенная задача, решение которой автоматически привело бы к решению большинства вопросов связанных с простыми числами заключается в следующем:

Получить рекуррентную формулу для очередного простого числа

Существует родственная ей задача о количестве простых чисел, не превосходящих заданной величины:

Найти функцию p(x), значение которой в точке x равно числу простых чисел на отрезке [1, x]. Где x – любое действительное число не меньшее единицы.

Функция называется функцией распределения простых чисел.

К решению вышеуказанных задач существует множество подходов. Рассмотрим некоторые из них.

Основная теорема арифметики гласит, что любое натуральное число большее единицы может быть представлено в виде произведения простых множителей (причём единственным образом, с точностью до порядка множителей).

Отсюда и из определения простого числа следует, что натуральное число, большее двух, является простым тогда и только тогда, когда оно не делится ни на одно из простых чисел меньших самого себя.

Первое простое число p₁ =2. Значит все последующие простые числа должны не делится на 2, то есть иметь вид 2k+1, где k – натуральное. То есть все простые числа начиная со второго — нечётные.

Второе простое число p₂ = 3. Значит все последующие простые числа должны иметь вид 3m+1, либо 3m+2, где m – целое. Это равносильно утверждению о том, что все простые числа начиная с третьего не делятся на три. Однако при этом числа ещё должны не делится на два, то есть иметь вид 2k+1.

Решая диофантовы уравнения

найдём k и m и получим, что все простые числа начиная с p₃ обязательно представимы в виде , либо в виде , где t – целое.

И правда, какое бы простое число мы ни взяли оно представимо таким образом:

Однако обратное неверно, то есть любое натуральное число вида 6t+1 или 6t+5 не обязательно простое. Например, .

Третье простое число p₃ = 5. И если по аналогии учесть, что любое простое число, начиная с четвёртого не делится на 5, также не делится на p₁ = 2 и на p₂ = 3, то получим, что все простые числа начиная с p₄ обязательно имеют одно из представлений

Затем учтём p₄, p₅ и т.д. Проблема в том, что на каждом шаге нам придётся решать всё большую систему диофантовых уравнений, поэтому такой прямолинейный подход оказывается весьма сложным.

На самом деле, при различных попытках решения поставленной нами задачи в большом количестве случаев появляются одни и те же конструкции. Например, произведение Эйлера. Рассмотрим, как это происходит, на следующем примере.

Итак, как же найти функцию F(x)? Сначала рассмотрим множество всех натуральных чисел. Какова доля чисел, которые не делятся ни на одно из простых p₁, p₂, …, p_n?

Каждое второе число делится на p₁ = 2. Значит, часть всех чисел делится на p₁.

Каждое третье число делится на 3. Значит, всех чисел делится на p₂. При этом надо учесть, что каждое шестое число делится и на 2 и на 3 одновременно.

Значит, доля чисел не делящихся ни на 2, ни на 3 равна

Если преобразовать выражение, то оно примет вид:

Опять же можно представить выражение в виде

Будем обозначать такое произведение P(n). Кстати, если учесть все простые числа (n→∞), то мы получим обратную величину от так называемого произведения Эйлера.

Почему так происходит? Когда мы получали формулу (1), мы пользовались рассуждениями, что среди всех натуральных чисел доля, делящихся на p_n, равна . Но нельзя сделать такое утверждение о конечном наборе последовательных натуральных чисел. Например, возьмём набор 1,2, 3,4,5,6,7,8,9. Здесь 4 числа из 9 делятся на два. И несложно заметить, что отличается от . То есть, при применении к конечному набору чисел, данный метод даёт результат с некоторой погрешностью.

Это будет мешать далее получать точные формулы. Но если оценить эту погрешность, то можно (например, приняв и используя приведённые выше рассуждения) получить оценку для p_n+1-го простого числа. Однако, получение таких оценок — это тема отдельной работы. И поэтому здесь я не буду на этом останавливаться, а приведу лишь некоторые результаты, полученные математиками.

Одна из оценок для простого числа с номером n:

оценка верна для всех n, начиная с 6.

А вот формула для функции распределения простых чисел:

Для функции Риман получил приближение, используя интегральный логарифм и нетривиальные нули дзета-функции Римана. Однако, это приближение верно, только если верна гипотеза Римана. Причём если гипотеза Римана верна, то оно является наилучшим.

Гипотеза Римана до сих пор не доказана и не опровергнута. Она, как мы могли видеть, тесно связана с простыми числами и, вообще, имеет огромное значение для теории чисел. Из-за своей важной роли в математике, гипотеза Римана была объявлена одной из семи задач тысячелетия.

Проблемы Ландау

Насчёт простых чисел выдвинуто очень много интересных гипотез. Среди них видное место занимают гипотезы Ландау (проблемы Ландау). Формулируются они так:

1. Гипотеза Гольдбаха

Можно ли любое целое чётное число, большее 2, записать в виде суммы двух простых?

2. Гипотеза о числах-близнецах

Бесконечно ли число простых p таких, что p + 2 тоже простое?

3. Гипотеза Лежандра

Всегда ли существует по меньшей мере одно простое число, лежащее между двумя последовательными полными квадратами?

4. Гипотеза о почти квадратных простых числах

Существует ли бесконечно много простых чисел p вида .

Проблемы Ландау ни доказаны, ни опровергнуты по состоянию на 2020 год. Далее кратко расскажу про каждую из них.

1. Гипотеза Гольдбаха

Существуют две гипотезы Гольдбаха: слабая (тернарная) и сильная (бинарная).

Слабая гипотеза Гольдбаха: Каждое нечётное число, большее 5, можно представить в виде суммы трёх простых чисел.

Эту гипотезу доказал Харольд Гельфготт в 2013 году используя так называемые большие дуги. Финальная часть доказательства заняла 133 страницы.

Сильная гипотеза Гольдбаха: Каждое чётное число, большее двух, можно представить в виде суммы двух простых чисел.

Надо заметить, что в обоих случаях гипотезы Гольдбаха простые числа не обязательно должны быть различными.

Заметьте, что в сильной гипотезе речь идёт только о чётных числах. Давайте покажем, что нечётное число не обязано быть представимо в виде суммы двух простых чисел. Просто приведём пример. Число 11 не представимо в виде суммы двух простых. Вроде бы несложно.

Но переформулируем проблему так: существует ли такое число, что любое нечётное, большее этого числа, представимо в виде суммы двух простых чисел? Давайте проверим. Пусть существует некоторое нечётное натуральное число N, такое, что любое нечётное число представимо в виде суммы двух простых чисел.

Возьмём произвольное нечётное . По предположению существуют такие простые p₁ и p₂, что . Если сумма двух натуральных чисел нечётна, то это значит, что одно из слагаемых чётно, а другое нет. Пусть для определённости p₁ – чётное. Единственное чётное простое число — это 2. Значит, . То есть, K-2 (предыдущее перед K нечётное число) является простым. Поскольку всё вышесказанное верно для любого нечётного большего N, то получается, что все нечётные числа, начиная с N-2, являются простыми. Это неверно. Если бы это было так, то при n→ ∞. Однако, как говорилось выше при n→ ∞.

Итак, не существует такого числа, начиная с которого все нечётные числа могут быть представлены в виде суммы двух простых.

А что же насчёт чётных? Гипотеза не была опровергнута, не было найдено ни одного контрпримера. Но это не значит, что их не существует. Доказать же гипотезу полностью пока никому не удалось.

2. Гипотеза о числах-близнецах

Бесконечно ли число простых чисел близнецов?

Для начала сформулируем определение. Два простых числа называются близнецами если отличаются друг от друга на 2.

Так же доказано, что существует бесконечно много простых чисел, разница между которыми составляет 246. Это наилучшая из обоснованных на данный момент оценок. Если же использовать некоторые недоказанные гипотезы о простых числах, то оценку можно улучшить.

3. Гипотеза Лежандра

Всегда ли существует, по меньшей мере, одно простое число, лежащее между двумя последовательными полными квадратами?

Аналогичная гипотеза доказана для кубов, начиная с некоторого n. То есть, существует, по меньшей мере, одно простое число, лежащее между и для достаточно большого n. Для квадратов же, гипотеза Лежандра пока не доказана.

4. Почти квадратные простые числа

Заключение

Как мы видим, в этой области теории чисел существует очень много пробелов, а также недоказанных гипотез. Отдельно хочется сказать про численную проверку утверждений. Например, ни для одной из гипотез Ландау не был найден контрпример, даже с использованием значительных вычислительных мощностей в течение большого времени. Однако, в истории математики 20-го и 21-го века были случаи, когда контрпример, опровергающий гипотезу, был настолько огромным числом, что его не удавалось найти с помощью вычислительных машин.

Также, постоянный интерес к простым числам обусловлен их обширным применением в криптографии. Итак, как мы убедились, исследование простых чисел — это, действительно, важная и очень интересная задача.

Источник

Простая математическая задача, которую мы все еще не в состоянии решить

А мы традиционно делимся с вами переводом интересного материала.

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

Эта статья идет вместе с предупреждением: не пытайтесь решить эту математическую задачу.

Вы будете испытывать соблазн попробовать сделать это. Эта проблема достаточно просто сформулирована, понятна и слишком заманчива. Просто выберите число, любое число: если число четное, разделите его пополам; если оно нечетные, умножьте его на 3 и прибавьте 1. Возьмите получившееся новое число и повторяйте этот процесс снова и снова. Если вы будете продолжать выполнять эти итерации достаточное количество раз, в конечном итоге вы застрянете в бесконечном цикле. По крайней мере, мы так думаем.

Или давайте попробуем 11: это нечетное число, поэтому мы утроим его и прибавим 1. Теперь мы получили 34, что является четным числом, поэтому мы делим его пополам и получаем 17, утраиваем и прибавляем 1, чтобы получить 52, уменьшаем вдвое, чтобы получить 26, и снова, чтобы получить 13, устраиваем его и добавляем 1, чтобы получить 40, уменьшите его вдвое, чтобы получить 20, затем 10, затем 5, утраиваем и добавляем 1, чтобы получить 16, делим пополам, чтобы получить 8, затем 4, 2 и 1. И мы снова застряли в бесконечном цикле.

Печально известная гипотеза Коллатца гласит, что если вы начнете с любого положительного целого числа, вы всегда окажетесь в этом бесконечном цикле. И вы, вероятно, проигнорируете мое предупреждение о попытке решить эту проблему: она кажется слишком простой и слишком складной, чтобы сопротивляться пониманию. На самом деле, было бы трудно найти математика, который бы не пытался найти подход к этой проблеме.

И я не смог проигнорировать ее, когда впервые узнал о ней в школе. Мы с друзьями целыми днями обменивались захватывающими идеями, которые в итоге никак не приближали нас к ответу. Но гипотеза Коллатца печально известна не просто так: даже если каждое число, которое когда-либо было опробовано, в конечном итоге попадает в этот цикл, мы все еще не можем быть уверены, что это утверждение справедливо всегда. Несмотря на все внимание, это до сих пор всего лишь предположение.

Тем не менее некоторый прогресс все же был достигнут. Один из величайших математиков в мире проигнорировал все предупреждения и взялся за дело, в итоге достигнув крупнейшего за последние десятилетия успеха в решении этой проблемы. Давайте посмотрим, что делает эту простую проблему такой сложной.

Чтобы понять гипотезу Коллатца, мы начнем со следующей функции:

Удобно представлять орбиту в виде последовательности со стрелками. Вот орбита 10 для f:

10 → 5 → 16 → 8 → 4 → 2 → 1 → 4 → 2 → 1 → …

В конце мы видим, что застряли в бесконечном цикле 1 → 4 → 2 → 1 →….

Аналогично, орбита 11 для f может быть представлена ​​как

11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 → 4 → ….

Мы снова попадаем в тот же цикл. Попробуйте еще несколько примеров, и вы увидите, что орбита всегда стабилизируется в этом цикле 4 → 2 → 1 →…. Начальные значения 9 и 19 забавны, а если у вас есть несколько свободных минут, попробуйте 27. Если ваша арифметика будет верна, вы окажетесь в цикле после 111 шагов.

Гипотеза Коллатца утверждает, что орбита каждого числа для f в конечном итоге достигает 1. И хотя никто не доказал эту гипотезу, она была проверена для каждого числа меньше 26⁸. Так что, если вы ищете контрпример, вы можете начать с 300 квинтиллионов. (Вы были предупреждены!)

Легко проверить, что гипотеза Коллатца верна для любого конкретного числа: просто вычисляйте орбиту, пока не дойдете до 1. Но чтобы понять, почему так трудно доказать ее для каждого числа, давайте исследуем немного более простую функцию ℊ.

Функция ℊ похожа на f, но для нечетных чисел она просто добавляет 1 вместо того, чтобы сначала утроить их. Так ℊ и f разные функции, числа имеют разные орбиты. Например, вот орбиты 10 и 11 для ℊ:

10 → 5 → 6 → 3 → 4 → 2 → 1 → 2 → 1 → 2 → …

11 → 12 → 6 → 3 → 4 → 2 → 1 → 2 → 1→ 2 → …

Обратите внимание, что орбита числа 11 достигает 1 быстрее для ℊ, чем для f. Орбита 27 также достигает 1 намного быстрее для ℊ.

27 → 28 → 14 → 7 → 8 → 4 → 2 → 1 → 2 → …

В этих примерах орбиты ℊ тоже выглядят стабилизирующимися, так же как орбиты f, но в немного более простой цикл:

Во-первых, мы знаем, что половина положительного целого числа всегда меньше самого целого числа. Итак, если n четное и положительное, то ℊ(n) = n/ 2 . Другими словами, когда орбита достигает четного числа, следующее число всегда будет меньше.

Обратите внимание, что

вероятно, тоже меньше n. И в самом деле, несложно доказать, что покуда n> 1, то всегда выполняется

Может ли аналогичное доказательство сработать с гипотезой Коллатца? Вернемся к исходной функции.

Как и в случае с ℊ, подстановка в f четного числа уменьшает его. Как и в случае с ℊ, подстановка в f нечетного числа возвращает нам четное число, что означает, что мы знаем, что произойдет дальше: f сократит новое число вдвое. Вот как выглядит орбита f, когда n нечетное:

Но здесь наше доказательство начинает разваливаться. В отличие от примера выше, это число больше n:

, что всегда больше n. Ключом к доказательству гипотезы Ноллатца было то, что нечетное число через два шага должно стать меньше, но это неверно в случае Коллатца. Наше доказательство не работает.

Если у вас есть что-то общее со мной и моими школьными друзьями, вы, возможно, захотите попробовать доказать, что гипотеза Коллатца ложна: в конце концов, если орбита продолжает увеличиваться, то как она может опуститься до 1? Но это доказательство требует понимания того, что происходит дальше, а что происходит дальше, проливает свет на то, почему гипотеза Коллатца настолько скользкая: мы не можем быть уверены, четное ли

Мы знаем, что 3n + 1 четное. Если 3n + 1 также делится на 4, то

тоже четное, и орбита будет уменьшаться. Но если 3n + 1 не делится на 4, то

нечетное, и орбита увеличивается. Как правило, мы не можем предсказать, что из этого окажется правдой, поэтому наше доказательство несостоятельно.

Но этот подход не совсем бесполезен. Поскольку половина всех положительных целых чисел четные, с вероятностью в 50%

четное, что делает следующий шаг по орбите равным

. Для n > 1 это уже меньше, чем n, поэтому в половине случаев нечетное число должно уменьшаться после двух шагов. Также существует 50%-ная вероятность, что

это четное число, что означает, что существует 25%-ная вероятность того, что нечетное число станет меньше более чем в два раза после трех шагов. И так далее. Конечный результат состоит в том, что в некотором среднестатистическом случае орбиты Коллатца уменьшаются, когда они сталкиваются с нечетным числом. А поскольку орбиты Коллатца всегда уменьшаются для четных чисел, это наталкивает на вывод, что все последовательности Коллатца в долгосрочной перспективе должны уменьшаться. Это доказательство на основе вероятностей широко известно, но еще никому не удалось довести его до полного доказательства гипотезы.

А в 2019 году Теренс Тао, один из величайших математиков мира, улучшил этот результат. Если Террас доказал, что почти для всех чисел последовательность Коллатца для n в итоге приходит к числу меньшему, чем n, Тао доказал, что почти для всех чисел последовательность Коллатца для n заканчивается намного ниже: ниже

Даже в этом случае гипотеза будет продолжать привлекать математиков и энтузиастов. Так что выберите число, любое число и вперед. Просто помните, вас предупреждали: не зацикливайтесь бесконечно.

Упражнения

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

3. В недавнем разговоре о гипотезе Коллатца Терренс Тао упомянул следующую функцию Коллатца:

Тао указывает, что в дополнение к петле 1 → 2 → 1 → 2 → 1… появляются еще две петли. Вы можете их найти?

Ответы

Нажмите, чтобы раскрыть ответ 1:

Обратите внимание, что каждая степень двойки имеет простой орбитальный путь к 1. Например,

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

Обратите внимание что 2^5 имеет время остановки 5, так как

…. А поскольку 2^4 имеет время остановки 4, любое число, которое на один шаг отстает от 2^4, имеет время остановки 5. Например, 5 → 16 → 8 → 4 → 2 → 1. Могут ли быть и другие?

5 → 14 → 7 → 20 → 10 → 5 → …

17 → 50 → 25 → 74 → 37 → 110 → 55 → 164 → 82 → 41 → 122 → 61 → 182 → 91 → 272 → 136 → 68 → 34 → 17 → …

Источник