[Ruby] Whether the sum of the first n primes plus 1 is prime

3 minute read

1

The infinite number of prime numbers was already known in ancient Greece. It seems that the proof of the following feeling is written in “Original theory Stoichia</ruby>” compiled in BC

Suppose there are only 3 prime numbers. Let this be $p$, $q$, $r$. If $pqr+1$ is divided by $p$, $q$, or $r$, $1$ will be left. This violates the assumption that the prime numbers are only $p$, $q$, $r$. (This reasoning is the same for 4 or 5 primes. In other words, assuming that the number of primes is finite, a contradiction is always introduced.)

It uses the absurd method (a logic that derives contradiction from Assumption A and proves the negation of A). When I met this proof in middle school, I was a little moved. The absurdity method was cool, and I think it was wonderful that the contradiction was really easily drawn from the simple formula “total product of all prime numbers plus 1.”

2

Around the same time, I learned that there was a theme of “searching for large prime numbers”. With the advance of electronic computers, I found that a huge number of prime numbers that could not be found by hand calculation were found one after another, and a table was created such as who found what prime number in which year. ..

3

An amateur like me remembers the proof of the “Principle” and thinks of such a wrong thing.

You can easily get a huge prime number by multiplying all found prime numbers and adding 1!

Of course not. The assumption that there is a finite number simply leads to the situation where the total product plus 1 cannot be divided. In reality, the number of primes is infinite, and just because a finite number of primes are taken out and multiplied by 1 and added to 1, that does not mean that they are primes.

Four

But right? The sum of the sum of $n$ primes plus one is at least indivisible by those primes. Therefore, in a sense, it can be said that it is a “divisible number”. In other words, there are quite a few prime numbers in them, right?

Considering Eratosthenes’s sieves sieves</ruby>, it seems efficient to eliminate multiples of small prime numbers to eliminate composite numbers.

Therefore, it would be good to arrange the prime numbers in ascending order, take the first $n$, and add 1 to the total product of them to try.

Five

First, take the first prime number $2$. Add $1$ to this, $3$ is a prime number.

Next. $2\cdot3+1=7$ is a prime number. How nice.

$2\cdot3\cdot5+1=31$ is also a prime number. Well, it’s in good shape.

How about $2\cdot3\cdot5\cdot7+1=211$? It’s easy to see that it’s not divisible by $11$ or $13$. You don’t have to try $17^2$ because it exceeds $211$. It turned out to be a prime number. Hmm, isn’t the story too good? Up to this point, I did my best by hand calculation.

How about $2\cdot3\cdot5\cdot7\cdot11+1=2311$? I gave up hand calculations. It’s not that difficult, but I’m not confident that I won’t make a mistake.

Here at the terminal

irb -r prime

Hit. Now, the Ruby interactive environment is started and the prime number library prime is loaded.

And

irb(main):001:0> 2311.prime?
=> true

Oh, this is also a prime number! (You can confirm that an integer is a prime number with Integer#prime?)

I didn’t expect to see only so many prime numbers.

6

Let’s examine it programmatically. Write the following in Ruby.

require "prime"

1.step do |n|
  m = Prime.take(n).inject(:*) + 1
  puts "%3d %s %d" %[n, (m.prime?? "o" :"x"), m]
end

This program is not written to stop. It is designed to continue to infinitely investigate.

You can get an array of the first n prime numbers with Prime.take(n).

You can get the total product with inject(:*).

And

  • the value of n
  • Whether it is a prime number (o if prime number, x otherwise)
  • Value of “total product plus 1”

Just display and side by side.

7

The results were as follows.

  1 o 3
  2 o 7
  3 o 31
  4 o 211
  5 o 2311
  6 x 30031
  7 x 510511
  8 x 9699691
  9 x 223092871
 10 x 6469693231
 11 o 200560490131
 12 x 7420738134811
 13 x 304250263527211
 14 x 13082761331670031
 15 x 614889782588491411
 16 x 32589158477190044731
 17 x 1922760350154212639071
 18 x 117288381359406970983271

It goes all the way to $n = 18$, but it doesn’t go on forever.

It was a prime number up to $n = 5$, but then a composite number follows. Hmm sorry.

When I think that the prime number finally appears at $n = 11$, the composite number continues again.

Was it an illusion that I thought, “I think prime numbers are included in a good proportion?”