[RUBY] Whether the total product of the first n prime numbers plus 1 is a prime number

It was already known in ancient Greece that there are an infinite number of prime numbers. The proof of the following feeling is written in " Principles Stoikeia </ ruby>" compiled in BC.

Let's say you have only three prime numbers. Let this be $ p $, $ q $, $ r $. When $ pqr + 1 $ is divided by $ p $, $ q $, or $ r $, $ 1 $ is left over. This violates the assumption that the prime numbers are only $ p $, $ q $, $ r $. (This reasoning is the same whether there are 4 or 5 prime numbers. That is, assuming a finite number of prime numbers always leads to a contradiction.)

It uses reductio ad absurdum (a reasoning that derives a contradiction from assumption A and proves A's negation). When I met this proof in junior high school, I was a little moved. The reductio ad absurdum was cool, and I thought it was wonderful to draw a contradiction from the simple formula "total product of all prime numbers plus 1".

Around the same time, I learned that there was a theme of "searching for large prime numbers." With the progress of electronic computers, huge prime numbers that could never be found by hand calculation were found one after another, and I saw for some reason that a list was created such as who found what prime number in what year. ..

An amateur like me remembers the proof of the "elementary theory" and comes up with such a wrong thing.

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

Of course not. The assumption of a finite number only led to the situation that the total product plus 1 was not divisible by any. In reality, there are an infinite number of prime numbers, and just because a finite number of prime numbers are taken out, multiplied, and added to 1 does not mean that they become prime numbers.

But is it? The sum of $ n $ prime numbers plus one is not divisible by at least those prime numbers. Therefore, in a sense, it can be said that it is a “number that is difficult to divide”. For that matter, aren't there quite a few prime numbers in them?

Considering the sieve sieve </ ruby> of Eratosthenes, it seems to be efficient to eliminate multiples of small prime numbers in order to eliminate composite numbers.

Therefore, it seems better to arrange the prime numbers in ascending order, take the first $ n $ pieces, and add 1 to their total product to try.

First, let's take the first prime number $ 2 $. $ 3 $, which is the sum of this and $ 1 $, 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 neither $ 11 $ nor $ 13 $ is divisible. $ 17 ^ 2 $ will exceed $ 211 $ so you don't have to try it. It turned out to be a prime number. Hmmm, isn't the story too good? So far, I have done my best by hand calculation.

How about $ 2 \ cdot3 \ cdot5 \ cdot7 \ cdot11 + 1 = 2311 $? I gave up the manual calculation. It's not that difficult, but I'm not confident that I won't make a calculation error.

Here to the terminal

irb -r prime

Hit. This will start the Ruby interactive environment, and the prime number library prime will be loaded.

And

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

Oh, is this also a prime number? (You can check that an integer is a prime number at Integer # prime?)

I never thought that only prime numbers would come out so well.

Let's examine it systematically in the program. Write as follows 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. Formally, it keeps searching indefinitely.

Prime.take (n) gives the first n array of prime numbers.

ʻInject (: *)` gives the total product.

And

Value of n
Whether it is a prime number (ʻoif it is a prime number,x` if not)
Value of "total product plus 1"

Just display and side by side.

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 up to $ n = 18 $ at a stretch, but it doesn't go on forever.

It was a prime number up to $ n = 5 $, but then a composite number follows. Hmmm 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 fair proportion?"