Prime Sierpinski Problem (prp , Sieve), Решаем задачу Серпинского Налаштування

[nikelong]

Официальный сайт

Официальная статистика по команде Украины:
1. Prime Sierpinski Problem - PRP
2. Prime Sierpinski Problem - Sieve

Расширенная статистиак по команде Украины:
1. Prime Sierpinski Problem - PRP
2. Prime Sierpinski Problem - Sieve

Как присоединится к проекту:

К сожалению, участники команды, которые считают этот проект, думают что присоединиться к нему плевое дело (так и есть). Только вот человеку, который ни разу в жизни не сталкивался с этим проектом трудно не то что присоединиться к проекту - трудно даже найти страницу, с которой нужно качать клиента! Организаторы проекта явно не знают что такое удобный интерфейс.
Потому Вам остается только вооружится Вашими знаниями по английскому и идти на официальный сайт за разъяснениями ...

О чем проект:

The Prime Sierpinski Problem
Проблема Простых чисел Серпинского

We look at a special class of prime numbers called proth numbers which have the general formula k*2^n+1. We further specialize our search by looking at numbers for which k is prime in k*2^n+1. Furthermore it has been proven that there exists an infinite number of prime k's such that k*2^n+1 can never be prime. These k's are called prime sierpinski numbers.

Нас интересует специальный класс простых чисел, которые называются числами Прота и описываются в общем виде формулой k*2^n+1. Конкретнее мы исследуем числа, в которых k простое число в формуле k*2^n+1. Как было доказано, существует бесконечное число простых чисел k, таких, что k*2^n+1 не является простым ни при каких n. Эти k называются простыми числами Серпинского.

The smallest proven prime Sierpinski number is 271129. We are looking at all prime k's below this number and trying to prove that they are not sierpinski numbers. The easiest way to prove that a k is not a prime sierpinski number is to find a prime for that k.

Минимальное доказанное число Серпинского 271129. Мы ищем простые числа для всех простых к меньше этого числа, и пытаемся доказать что они не являются числами Серпинского. Простейший способ доказать что какое либо к не является числом Серпинского, это найти простое число для этого к.

There are currently 12 such candidates remaining for which we need to find a prime. We have already found 17 large primes, several of which made it into the top 100 largest known prime number list.

Сейчас осталось 12 кандидатов, для которых мы должны найти простое число. Мы уже нашли 17 больших простых чисел, некоторые из них попали в ТОП100 простых чисел.

Before testing numbers for primality, we sieve out all those numbers where it is easy to find a factor, so that they cannot be prime. This is called "sieving". We are currently sieving up to n=50 million, which limit was chosen for efficiency reasons.
When a k is proved that it is not a sierpinski number the k is eliminated. This means that we no longer have to test that k for primality nor find factors for this k.

Перед тем, как проверять число не простоту, мы просеиваем все числа, для которых легко найти делитель, и таким образом доказать что они не простые. Это называется СЕЯЛКА. Сейчас мы засеваем %-) до n=50 миллионов, этот предел выбран из соображений эффективности. Когда доказано, что какое-то к не является числом Серпинского, оно вылетает из исследования. Это означает что не проверяем больше это к на простоту и не ищем делители для него.

If you have any questions please ask them on our forum here.

Вопросы?

Что такое PSP и Sieve:

ПСП - тест числа на простоту. Выполняется для какого-то конкретного значения к и н. Занимает МНОГО времени.
Сеялка - быстрый поиск делителей для всех к сразу и для н меньше 50 млн. Несмотря на то, что делитель находится редко, это всё равно быстрее чем проверять на простоту.

Це повідомлення відредагував nikelong: Mar 13 2009, 14:24

[(_KoDAk_)]

О проекте:

(Show/Hide)

The Prime Sierpinski Problem

The Prime Sierpinski project (PSP) is a mathematical project involved in the search of large prime numbers. Prime numbers are numbers,
which are divisible by 1 and by themselves and not by any other numbers. It has been proved that there are an infinite number of prime
numbers but no one has been able to prove anything about the distribution of prime numbers in general. It is a mysterious frontier of mathematics.

We look at a special class of prime numbers called proth numbers which have the general formula k*2^n+1. We further specialize our search
by looking at numbers for which k is prime in k*2^n+1. Further more it has been proven that there exists an infinite number of prime k's such
that k*2^n+1 can never be prime. These k's are called prime sierpinski numbers.

The smallest proven prime sierpinski number is 271129. We are looking at all prime k's below this number and trying to prove that they are not
sierpinski numbers and thus studying the distribution of primes of the forum k*2^n+1. The easiest way to prove that a k is not a prime sierpinski
number is to find a prime for that k.

There are currently 14 such candidates remaining for which we need to find a prime. We have already found 14 large primes, several of which
made it into the top 100 largest known prime number list. Currently in this stage we are searching for primes up to n=50 million and once we
reach there we plan to continue to higher values. There is a $100,000 prize given by the EFF corporation (www.eff.org) for finding
a 10 million-digit prime. A 10 Million digit prime corresponds to n>34 million. We plan to find that 10 Million digit prime and win the prize.
For this we need your help to find several primes and eliminate several more k's so that it becomes easier and easier to find a 10 Million digit prime.

The highest n limit of 50 Million was chosen because of efficiency reasons.
When a k is proved that it is not a sierpinski number the k is eliminated. This means that we no longer have to test that k for primality
or find factors for this k. This makes the process faster (because of fewer numbers to test) and brings our goal of a 10 Million-digit prime
closer to us. We saw no point in testing all the k's up to a higher n when most of them will produce a prime below n=50 million.

You could be next to find a large prime and be famous and rich.

--------------------------------------------------------------------------------------------------------------------------------------------------------
How is the project organized?

To solve the Prime Sierpinski Problem we need to find 14 primes for the k's listed at the end of this thread. 3 of these k's are reserved
by another project who are searching for primes for these 3 k's, the rest of the 11 k's are reserved by us. In order to prove the primality
of a number we need to perform a primality test called PRP. This test takes very long; hence to reduce the time of the project we look
for numbers with small factors and remove these numbers from our primality-testing list. This process is called sieving. The PRP testing
method is not 100 % efficient, that is, it can make errors. On the other hand once a factor is found for a number, we can be 100 % sure
that, that number is not prime. All numbers that are checked by PRP need to be double-checked. Since the probability of finding a prime
is higher than having made an error and missing a prime, we are not currently pursuing the double check of numbers. There is another
method that allows us to find factors for numbers called P-1 ("P minus one"). The running time for this method is similar to PRP. Currently
we are not pursuing this method either, since it is more efficient to use sieving to find these factors. We do plan to use these methods a bit
later in the project.

Some stats for the project are available here: -
http://www.psp-project.de/stats.html (updated every 15 min)
http://www.psp-project.de/llrnetstats.php
----------------------------------------------------------------------------------------------------------------------------------------------------------
What portion of the project to contribute?

The best part depends on your computer type. Pentium-4 computers are the best suited for LLR-tests. 64-bit Linux computers should
definetely sieve. Slow computers could find their happiness in sieve, because the size of the reserved work is adjustable. Other fast
computers can contribu
te in the sieving or the PRP portion; the sieving part is still more efficient, but doesn't find primes.

--------------------------------------------------------------------------------------------------------------------------------------------------------
How to participate?

PRP: Use the automated network client if your computer has an Internet connection and you don't want to deal with installing work and
submitting results. If you are without an Internet connection you can run the manual version of the client, but you will have to then
manually reserve ranges and submit results. You could though reserve ranges from one computer with an Internet connection and then
transfer the files to another computer with no Internet connection and then back to the first computer to submit results and get more work.

Note: - If you are on a LAN and have several machines or you are behind a firewall and cannot connect to the outside world, you can
run your own server or proxy server that distributes numbers to your clients.

An illustrated guide for running the network/server client or the manual client for PRP can be found here.

Sieving: - There is an automated BOINC client available here.

If you want to reserve a range manually, you still can in the sieve reservation thread, you will find the prescribed software here.
It is commandline, and you need to read the Readme file in order to get started.

If you have some computers that can help PSP but you are running into problems, please ask on the forum. There might be a solution
to your problem, such that you would be able to run your machines.

--------------------------------------------------------------------------------------------------------------------------------------------------------
List of k's we are searching currently!

79309
79817
90527
152267
156511
168451
222113
225931
237019
258317

--------------------------------------------------------------------------------------------------------------------------------------------------------
List of Primes already found!

87743*2^212565+1 is prime! (found by Morris Cox on 11/18/03)
224027*2^273967+1 is prime! (found by FootMaster on 12/12/03)
203761*2^384628+1 is prime! (found by FootMaster on 01/05/04)
122149*2^578806+1 is prime! (found by FootMaster on 01/19/04)
247099*2^484190+1 is prime! (found by FootMaster on 02/05/04)
172127*2^448743+1 is prime! (found by Citrix on 02/05/04)
159503*2^540945+1 is prime! (found by FootMaster on 02/07/04)
263927*2^639599+1 is prime! (found by FootMaster on 02/20/04)
261917*2^704227+1 is prime! (found by ltd on 03/08/04)
161957*2^727995 + 1 is prime! (found by FootMaster on 03/22/04)
216751*2^903792+1 is prime ! (found by ltd on 5/10/2004)
241489*2^1365062+1 is prime! (found by Citrix on 1/25/2005)
149183*2^1666957+1 is prime! (found by ltd on 10/7/2005)
214519*2^1929114+1 is prime! (found by ltd on 1/2/2006)
222361*2^2854840+1 is prime! (found by Shy24 on 31/8/2006)
265711*2^4858008+1 is prime! (found by Sloth on 05/04/2008)