Comments 75
«число 1 формально соответствует определению простого числа, кроме того оно имеет еще ряд дополнительных интересных „свойств“»
Соответствует или нет — зависит только от определения. Если в каких-то случаях (пример в статье про множества с бесконечным количеством обратимых элементов) удобнее считать простыми только необратимые элементы, а во всех остальных это не играет роли, то почему бы не использовать одинаковое определение везде? Собственно, я так понимаю, что современное определение простого числа как раз учитывает эту особенность и единица из множества простых исключается.
Ну да, можно сказать что причина практическая, но ведь в этом и есть суть определения — им должно быть удобно пользоваться.
Пи — это просто обозначение (не определение), оно здесь ни при чём. Хотя и утверждение про «мы же не округляем» тоже неверно само по себе, потому что во многих случаях всё-таки округляем.
потому что во многих случаях всё-таки округляем.А в каких не округляем?
"Для гренландского кита число Пи равно трём"?
Читал на просторах интернета:
(Приписывается этому товарищу: vk.com/kknop
типа копирайт соблюдён)
В незапамятные времена участвовал в конкурсах работ МАН (Малой Академии Наук). Сам по математике, но однажды оказался зрителем на докладе в секции биологии. Работа была посвящена изумительному наблюдению, подкреплённому большим числом замеров: окружность любого муравейника примерно втрое длиннее его диаметра.
В этом плане нет субъективности, названия определений придуманы людьми, математических противоречий они не создают.
Складывается ощущение, что практическая причина, как раз единственная и есть
А разве нужны ещё какие-то причины? В математике очень многое делается просто для удобства и для консистентности рассуждений.
Если хочется с кем-то похоливарить, можно, например, вспомнить споры насчёт того, чему равно 0ⁿ при n=0. :) И таких примеров достаточно много.
чему равно 0ⁿ при n=0Вероятно, чаще это можно определить как равное нулю, а x^0 = 1 при х = 0 (ну почти -_-).
Остаётся решить, к чему относится 0^0 (или запретить такое совсем).
А вообще, это интересная тема:
https://ru.wikipedia.org/wiki/Ноль_в_нулевой_степени
Например, является ли 0 четным числом
Опередили
Путаница начинается с определения, которое дают простому числу: это положительное целое число, которое делится только на 1 и само на себя.
Сами определение выдумали? Википедия, конечно, не самый авторитетный источник, но все же:
A prime number (or a prime) is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers
Просто́е число́ — натуральное (целое положительное) число, имеющее ровно два различных натуральных делителя — единицу и самого себя[
math.wikia:
Просто́е число́ — это натуральное число, больше единицы, имеющее ровно два натуральных делителя: 1 и само себя
Кажется, вы взяли за основу неверное определение и на его основе начали что-то выдумывать…
"… каждое число может быть записано как произведение простых чисел ровно одним способом. Если бы 1 было простым, мы бы потеряли эту уникальность. Мы могли бы записать 2 как 1×2, или 1×1×2, или 1594827×2. Исключение 1 из простых чисел устраняет это"
А тогда произведением каких простых чисел записать любое простое число?
2, 3, 11, 29?
SUM(1)=1 в SQL.В математике такое практикуется?
Первый раз слышу.
Да, вполне себе практикуется, когда надо перемножить произвольное число членов. С суммой аналогично, например, сумма квадратов чисел от 1 до n:
Тут вполне разумно считать, что для n=1 эта сумма равна своему единственному члену
Если он пуст, возвращают "нейтральный элемент" этой операции.
Это, кстати, отвечает на вопрос, произведением каких простых чисел является единица: никаких (пустой список).
every integer greater than 1 either is a prime number itself or can be represented as the product of prime numbers
Попробуем определить простые числа так:
Простые числа это натуральные числа которые не делятся на другие простые числа.
Единица как минимальное натуральное не делится на другие числа, значит оно простое, а дальше, раз все другие числа делятся на единицу, то других простых чисел, кроме единицы, нет. Приехали.
Наша попытка дать определение провалилась. Ведь это не определение, а свойство простого числа. Если взять второе свойство — не быть единицей, то определение будет в том, что у простого числа два представленных свойства. И тогда все нормально. 2, 3, 5, 7, ...
То есть, свойство простого числа не быть единицей обязательно.
Просто нужно ввести 2 типажа:
trait Prime {}иtrait One : Prime {}.
Или даже 3:
trait PrimeBase {}trait One : PrimeBase {}trait Prime : PrimeBase {}— для определений, которые к единице неприменимы. В общем-то сейчас так и сделали, просто почему-то не сказали об этой явно, и в разных контекстах возможно под словосочетанием "простое число" имеют ввиду один из этих 3-х типов.
в разных контекстах возможно под словосочетанием «простое число» имеют ввиду один из этих 3-х типов.Насколько мне известно, нет. Честно говоря, я не могу сходу придумать естественных примеров, когда включение единицы в простые числа сделает что-то проще. Ну, кроме определения простых чисел.
Откуда тогда споры если все сходятся в определении?
Какие-то теоремы чуть проще формулировать, если единицу простым числом не считать. Например, основная теорема арифметики, которая упоминается в статье.
Какие-то теоремы про простые числа тогда также хорошо обобщаются на более общие структуры вроде целых чисел (а не натуральных) и гауссовых целых чисел. Получаем одно общее определение — удобнее работать.
Дело, казалось бы, за малым: убрать из ряда квазипростые числа — произведение простых чисел. Например, 5 * 7 = 35 — не простое число.
Интересно, будет в ближайшее время найдена формула простых чисел? Какие прогнозы?
Определить "формулу" мы можем либо очень узко (вроде "можно использовать только арифметические операции", тогда там вообще ничего разумного не сделать), либо так, что получается выражать произвольные алгоритмы. А написать программу для вычисления простых чисел, конечно же, можно. Про это есть прекрасный ответ на английском от Alon Amit на Quora.
Например, вот формула, которая выдаёт 1, если число простое, и 0 иначе (взята из ответа выше):
Как работает: надо проверить, что для каждого числа от 2 до n-1 выражение n%d не равно нулю. Другими словами, все выражения вида d-(n%d) равны нулю. А деление на d с округлением вниз — это как раз такой "if". То есть внутренняя сумма — это количество делителей числа n от 2 до n-1.
Если захотим выразить простое число под номером n, это тоже легко делается через P(n):
Тут мы просто нашли минимальное m такое, что от 2 до m встречается ровно n простых чисел.
Каким-то аналогичным образом можно, например, закодировать любой алгоритм в виде многочлена, в том числе для простых чисел.
Каким-то аналогичным образом можно, например, закодировать любой алгоритм в виде многочлена, в том числе для простых чисел.
Понятно — любое простое число можно записать с помощью полинома. На сегодня — это полином, содержащий 26(!) переменных и имеющий степень 25(!).
А есть уверенность в том, что с увеличением вычислительных возможностей компьютеров не придется, например, добавлять в полином 27-ю переменную?
Разные теоремы, например, теорема Ферма помогают отсеять множество псевдопростых чисел.
Тест на простоту
Полином Матиясевича — habr.com/ru/news/t/406485/#comment_18361061.
Разные теоремы, например, теорема Ферма помогают отсеять множество псевдопростых чисел.
Тест на простотуЯ не о полиномах и тестах на простоту, которые, кстати, носят вероятностный характер.
В той же Википедии встречается мысль, что ряд простых чисел нельзя отобразить формулой с одной переменной. Если это доказано, то кем и когда?
Есть и детерминированный (не вероятностный) тест на простоту.
В той же Википедии встречается мысль, что ряд простых чисел нельзя отобразить формулой с одной переменной. Если это доказано, то кем и когда?
Там не про формулы сказано, а про очень специфичное существование многочленов: не существует неконстантного многочлена (т.е. принимающего хотя бы два различных значения) от одной переменной, который при всех целых значениях своего аргумента выдаёт только простые числа.
Доказательство есть в английской Википедии: пусть есть многочлен P(x), который принимает только простые значения. Тогда, в частности, P(1) простое, обозначим его p. Тогда P(1) сравнимо с 0 по модулю p. Однако тогда для произвольного целого k P(1+kp) тоже сравнимо с 0 по модулю p, то есть тоже делится на p. Но если P(1+kp) простое, что P(1+k*p)=p. То есть многочлен в бесконечном количестве точек равен p, следовательно, многочлен — константа.
То есть многочлен в бесконечном количестве точек равен p, следовательно, многочлен — константа.
На практике такое «доказательство» проверить невозможно, поскольку проверка бесконечного количества точек требует бесконечного количества времени.
Что для вас значит «проверить доказательство»? Для меня это может означать, допустим, «перевести его на язык формальной логики, а затем, последовательно применяя правило обобщения и modus ponens, свести его к некоторому подмножеству принятой нами аксиоматики». Очевидно, у вас какое-то другое понимание этого. Пожалуйста, поделитесь им.
Но, повторюсь, на практике от такого доказательства — ни холодно, ни жарко. Это определение простого числа не дает ответа ни на одну из многочисленных открытых проблем по теории чисел, которые перечислены там же.
Успехов!
Интересно, будет в ближайшее время найдена формула простых чисел? Какие прогнозы?У Джона Дербишира есть неплохая книга на эту тему — «Простая одержимость»
У Джона Дербишира есть неплохая книга на эту тему — «Простая одержимость»
Спасибо! Ваша ссылка — подтверждение моей смутной догадки, что проблема поиска закономерности простых чисел на сегодня не закрыта.
А многотысячные призы за очередное новое простое число от разных фирм и фондов — это еще один аргумент: проблема есть!
Когда я был юн, я, как любой нормальный ребёнок, пытался найти формулу простых чисел. Потому что школьная математика приучила меня: для всего есть простые формулы.
Затем я окунулся в дебри высшей математики. Я познакомился с невычислимыми функциями, неберущимися интегралами, нерешаемыми в квадратурах диффурами и прочим. И я обнаружил удивительную вещь: отсутствие явной, «школьной» формулы — это, в общем-то, норма. Настоящая математика полна т.н. «специальных функций», которыми пользуются как обычными. И простые числа — просто очередная специальная функция из ℕ в ℕ. Может, у них есть какая-то «формула», которая вас устроит. Скорее всего, её нет. И в этом не будет совершенно ничего необычного.
Сами по себе простые числа математике, разумеется, интересны. И если бы «формула» была, это было бы круто. Но надежда на её наличие следует лишь из интуиции школьника, переобученной на нерепрезентативной выборке.
И простые числа — просто очередная специальная функция из ℕ в ℕ. Может, у них есть какая-то «формула», которая вас устроит. Скорее всего, её нет. И в этом не будет совершенно ничего необычного.
Вы упрощаете мое понимание задачи.
Моя позиция заключается в том, что данная задача будет решена тогда, когда это признает научное сообщество. И неважно — это будет зависимость с одной переменной, полином или что-то принципиально другое. Решение этой задачи даст ответы на многие частные вопросы. Например, конечное или бесконечное множество простых чисел?
И, наконец, приведу историческую аналогию:
Большая теорема Ферма, сформулированная в средневековье, была доказана лишь в конце прошлого века.
Я оптимист и верю, что рано или поздно это событие состоится и в теории простых чисел.
Успехов!
это положительное целое число, которое делится только на 1 и само на себяЕсли честно, никогда не слышал определения простого числа без упоминания «больше единицы».
1-ца простое число. KISS.
Тогда и ноль, почему нет? :) Тоже ж делится на себя и 1.
KISS.«Everything Should Be Made as Simple as Possible, But Not Simpler.»
Простые числа имеют ровно 2 делителя: 1 и само число — это просто.
1 имеет только один делитель — это слишком просто, поэтому оно не простое.
Два делителя простого числа имеют разные определения:
- точно определенная константа: "1"
- самореференция: "само число"
Делители 1-цы тоже два и соответствуют этим определениям:
- точно определенная константа "1"
- само число: "1"
То что эти два делителя совпадают несущественная случайность, так как они выведены из разных независимых определениях.
Если хотим исключить 1-ца из простых, то эти две определения надо усложнять и делать зависимыми. Например "2. само число, но не 1-ца". Для этого надо иметь очень веские основания.
Кстати, мне кажется, что "проблемы" с основной теоремой арифметики иллюзорны и устраняются простым уточнением определения.
Тождество Эйлера для дзета-функции представляет собой произведение, берущееся по всем простым числам. Единица в это произведение не входит, следовательно…
Почему единицу не относят к простым числам, и когда её вообще начали считать числом