17.07.2023 18:18
PicoPicoRobotWoman 23 1700 Источник

Введение

Вы абсолютно правы! Тест на простоту — это алгоритм, который определяет, является ли данное натуральное число простым или составным.

В данной статье я хочу рассказать о тесте, который не так распространен, и о котором нет информации на русской Википедии. Название этого теста мне также неизвестно.

Метод гласит, что если число p простое, то из уравнения:

{(x-1)}^p-(x^p-1) = \sum_{k=0}^{p} a_kx^k \\a_k - коэфициент\ при\ x^k

Если каждое ak​ кратно p, то p — простое число.

∀{p \in \mathbb{N}} ((D(p) → P(x)) ∧ (¬D(p) → ¬P(x))) \\P(p) - число\ являяется\ простым \\ D(p): (x-1)^p - (x^p-1) = \sum_{k=0}^{p} a_kx^k\ все\ коэффициенты\, кратные\ p.

В данной статье я хочу протестировать данную гипотезу/теорему на поиске всех простых чисел от 1 до произвольного натурального n>3.

Разберемся с коэффициентами

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

{(x-1)}^p-(x^p-1) = \sum_{k=0}^{p} (-1)^{p - k}C_p^kx^k -(x^p -1 ) = \sum_{k=1}^{p - 1} (-1)^{p - k} C_p^kx^k

То есть задача сводится к проверке кратности p всем биномиальным коэффициентам.

C_p^k \ ⋮ \ \ p, k = \overline{1,k - 1}

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

C_p^k \ ⋮ \ \ p, k = \overline{1,(p +1)/ 2 }

Еще один факт, который позволит проверять меньше чисел, заключается в том, что любое простое число (кроме 2 и 3) можно представить в виде 6n−1 или 6n+1 для любого натурального n.

Пишем код

Первым делом необходимо сгенерировать сами числа от 4 до n>3 и объединить с числами 2 и 3 (их нельзя проверить по правилу 6n). 

(BigInt(2) to BigInt(3)).union((4 to StdIn.readInt()) ... )

В Scala выражение (a to b) генерирует вектор из всех чисел от a до b.

Затем отфильтруем все числа (кроме 2 и 3) по правилу 6n.

  val simples = (BigInt(2) to BigInt(3)).union((4 to StdIn.readInt())
    .filter(p => (p - 1) % 6 == 0 || (p + 1) % 6 == 0) //фильтрация по правилу 6n
  )

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

.filter(p =>
  (2 until (p + 1) / 2)
  .scanLeft(BigInt(p))((left, k) => left * (p - k + 1) / k)
  .map(k => k % p).sum == 0)

(2 until (p + 1) / 2) - данная строчка генерирует вектор от 2 до(p+1)/2−1.

Вспомним формулу бинома:

C_p^k = \frac{p!}{k!(p - k)!}

Разделим коэффициент при k на биномиальный коэффициент при k−1.

\frac{C_p^{k}}{C_p^{k - 1}} = \frac{p!}{(k)!(p - k)!}/ \frac{p!}{(k - 1)!(p - k + 1)!} = \frac{p-k + 1}{k}

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

Заметим также, что:

С_p^1 = p

Давайте вернемся к коду.

.scanLeft(BigInt(p))((left, k) => left * (p - k + 1) / k) - scanLeft это то же самое, что и foreach, с той лишь разницей, что позволяет узнать результат предыдущей итерации (left) с пропуском первого значения, инициализируя его в начале как BigInt(p). Затем в (left, k) => left * (p - k + 1) / k уже сами считаем коэффициенты по упрощенной формуле.

.map(k => k % p).sum == 0 - в данном от всех коэффициентов вычисляется модуль по p, и затем считается сумма остатков, что позволяет определить, все ли коэффициенты кратны p.

Теперь весь код целиком выглядит так:

import scala.io.StdIn

object UniversePolinomeTest extends App {

  print("введите натуральное число (n) больше 3: ")

  val primes = (BigInt(2) to BigInt(3)).union((4 to StdIn.readInt())
    .filter(p => (p - 1) % 6 == 0 || (p + 1) % 6 == 0)
    .filter(p =>
      (2 until (p + 1) / 2)
      .scanLeft(BigInt(p))((left, k) => left * (p - k + 1) / k)
      .map(k => k % p).sum == 0)
    )

    println(s"все просты числа до n : $primes")
    println(s"найдено простых чисел: ${primes.size}")

}

Во всей программе я использую длинную арифметику (BigInt), поскольку Int и Long быстро перестают справляться, так как факториалы слишком быстро растут.

Результат/Заключение

Данный код/метод справляется достаточно точно. Ниже приведен пример для чисел до 10000 (после 19 идет много чисел, которые проблематично уместить в кадре).

Хотя код/метод и справляется с достаточно большим количеством чисел, я не стану утверждать, что он работает на 100% случаев.

P.S.

Код можно посмотреть на GitHub

Комментарии (23)


  1. Actaeon
    17.07.2023 18:23
    #25761694
    +2

    В первой формуле у вас верхний предел суммирования неправильно записан.


    1. PicoPicoRobotWoman Автор
      17.07.2023 18:23
      #25761700
      +1

      често сказать, не вижу ошибки


      1. Actaeon
        17.07.2023 18:23
        #25761708
        +1

        КОНТРПРИМЕР p=29,n=3,x=10


        1. PicoPicoRobotWoman Автор
          17.07.2023 18:23
          #25761724
          +2

          спасибо, уже поправила, x тут не число а переменная, мы ее ни к чему не приравневаем, нас интересуют только коэфициенты при x^k


      1. wataru
        17.07.2023 18:23
        #25761722
        +1

        Там должно быть p а не n.


        1. Actaeon
          17.07.2023 18:23
          #25761936

          p-1 если совсем правильно. Но ,поскольку нулевые коэффициенты a_k считаются кратными p ...


  1. sci_nov
    17.07.2023 18:23
    #25761726
    +2

    Теорему Вильсона чем-то напоминает


  1. sci_nov
    17.07.2023 18:23
    #25761732

    А чему равно x в Вашем методе?


    1. Actaeon
      17.07.2023 18:23
      #25761740

      Там еще квантор всеобщности по x не дописан, да


      1. PicoPicoRobotWoman Автор
        17.07.2023 18:23
        #25761764

        нет, x - просто переменная, она ни к чему не приравневается


    1. PicoPicoRobotWoman Автор
      17.07.2023 18:23
      #25761744

      ничему, это переменная, нас интересуют только коэфициенты при ней


      1. sci_nov
        17.07.2023 18:23
        #25761782
        +2

        А, понял. По ходу, если число p - простое, то оно должно делить все биномиальные коэффициенты, кроме, естественно, единичных. А вот верно или нет обратное - не знаю:)


        1. wataru
          17.07.2023 18:23
          #25761834
          +1

          А вот верно или нет обратное — не знаю:)

          Верно. Alexandroppolus чуть ниже привел доказательство. Но наверняка


  1. Alexandroppolus
    17.07.2023 18:23
    #25761788
    +2

    Хотя код/метод и справляется с достаточно большим количеством чисел, я не стану утверждать, что он работает на 100% случаев.

    Да вроде это тривиально доказывается. А именно, что если m не простое, то найдется такое 0 < n < m, что C(m, n) не делится на m. Пусть в m есть простой делитель p в степени k. Тогда берем n = p, и получаем C(m, n) = m! / (p! * (m - p)!) = m * (m-1) * (m-2) * ... *(m-p+1) / p!. В этой дроби числитель равен (p^k * a), знаменатель равен (p * b), где a и b не делятся на p, итог будет (p^(k-1) * с), т.е. не делится на m

    Ну а для простого m всё очевидно


  1. wataru
    17.07.2023 18:23
    #25761800
    +5

    Похоже на очень наивную реализацию метода AKS. Основано на той же теореме, только вместо проверки в поле по модулю X^r-1 тут брутфорсом проверяются все коэффициенты (ну ладно, половина — все равно плохо).


    В итоге, получилось вообще бесполезное упражнение. Этот метод проверяет число N за O(N) операций с BigInt. Очень сложных операций. Наивная же проверка на делимость с одной единственной оптимизацией (проверять делители до корня) работает на порядки быстрее — за O(sqrt(N)).


    Более того, поскольку тут считаются сами коэффициенты бинома, то в процессе вычисления получаются числа длины O(N). Т.е. на самом деле тут сложность даже не линейная от числа, а квадратичная! Более медленный и бесполезный метод проверки числа на простоту придумать довольно сложно.


    1. sci_nov
      17.07.2023 18:23
      #25761844

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


      1. wataru
        17.07.2023 18:23
        #25761860

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


        1. sci_nov
          17.07.2023 18:23
          #25762308

          Интересно, откуда автор взял метод. Возможно, это студенческая работа, а метод предложил научный руководитель :)


          1. PicoPicoRobotWoman Автор
            17.07.2023 18:23
            #25763114

            неверная догатка)


    1. PicoPicoRobotWoman Автор
      17.07.2023 18:23
      #25761892
      -1

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


      1. ermouth
        17.07.2023 18:23
        #25762166
        +2

        и не заявлялось что он "быстрый"

        Простите, но вы прямо в лиде заявляете, что он «эффективный и надёжный», а он ни то, ни другое.


      1. wataru
        17.07.2023 18:23
        #25763332

        поскольку ничего о практической применимости не говорилось

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


  1. uchitel
    17.07.2023 18:23
    #25764532

    Такие алгоритмы являются предметом любопытства, а не практического применения. А что такое любопытство? Оно вообще нужно?

    Вы движетесь в правильном направлении. Попробуйте делать все это на питоне. Кстати для питона есть хорошая либа gmpy2.

    Завидую тому, что у вас есть время на такие занятия.