Applying the binomial formula to determine prime numbers

Introduction

You are absolutely right! A primality test is an algorithm that determines whether a given natural number is simple or composite.

In this article, I want to talk about a test that is not so common, and about which there is no information in Russian Wikipedia. The name of this test is also unknown to me.

The method says that if the number p simple, then from the equation:

${(x-1)}^p-(x^p-1) = \sum_{k=0}^{p} a_kx^k \\a_k - coefficient\ of\ x^k$

If each ak is a multiple of p, then p is prime.

$∀{p \in \mathbb{N}} ((D(p) → P(x)) ∧ (¬D(p) → ¬P(x))) \\P(p) - number\ is\ prime \\ D(p): (x-1)^p - (x^p-1) = \sum_{k=0}^{p} a_kx^k\ all\ coefficients\ multiples of\ p.$

In this article, I want to test this hypothesis/theorem on the search for all prime numbers from 1 to arbitrary natural n>3.

Let’s look at the ratios.

Oddsak are nothing but binomial coefficients. This is easy to understand using the formula Newton’s binomial:

${(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$

That is, the problem is reduced to checking the multiplicity p all binomial coefficients.

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

Since the binomial coefficients are symmetric, we need only check half of them.

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

Another fact that will allow you to check fewer numbers is that any prime number (other than 2 And 3) can be represented as 6n−1 or 6n+1 for any natural n.

We write the code

The first step is to generate the numbers themselves от 4 до n>3 and combine with numbers 2 And 3 (they cannot be checked by the rule 6n).

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

In Scala expression (a to b) generates a vector of all numbers from a before b.

Then we filter all numbers (except 2 And 3) according to the rule 6n.

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

Now for each of the remaining numbers we will check for simplicity.

.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) – this line generates a vector from 2 before(p+1)/2−1.

Recall the binomial formula:

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

Divide the coefficient at k by the binomial coefficient at k−1.

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

This formula will allow you to calculate the coefficients in the vector much faster,
and you don’t have to calculate factorials for each number separately.

Note also that:

Let’s get back to the code.

.scanLeft(BigInt(p))((left, k) => left * (p - k + 1) / k) – scanLeft it’s the same as foreachwith the only difference that allows you to find out the result of the previous iteration (left) omitting the first value, initializing it at the beginning as BigInt(p). Then in (left, k) => left * (p - k + 1) / k we ourselves calculate the coefficients using a simplified formula.

.map(k => k % p).sum == 0 – in the given one, the modulus is calculated from all coefficients according to pand then the sum of the remainders is calculated, which allows you to determine whether all the coefficients are multiples p.

Now the whole code looks like this:

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}")

}

Throughout the program I use long arithmetic (BigInt), because the Int And Long fail quickly because the factorials grow too fast.

Result/Conclusion:

This code/method does the job pretty well. Below is an example for numbers up to 10000 (after 19 there are a lot of numbers that are problematic to fit in the frame).