Prime forms involving Repunits, R_n.

[Pfoertner, Hugo]

-----Original Message-----
From: Don Reble [mailto:djr at nk.ca] 
Sent: Friday, October 15, 2004 03:13
To: Seqfan
Subject: Re: Prime forms involving Repunits, R_n.



> we should ... get to exponents 10000. ...
> [Only a few sequences] have been searched to that limit.

Yeah, most likely. Let's include the search limit with the sequence.

> Personally I can get to >6500 by letting my computer run over night
> and that is on a 1.2GHz Athlon chip.
> Bob.

In such a search, one might have to prove primality of a number having
thousands of digits. Which technique do you recommend, Bob?
(Perhaps this
    %C A098088 ... n = 1600, 2175, 2978 and 3649 are only probable primes.
 is good enough.)

--
Don Reble  djr at nk.ca

SeqFans, Bob, Don, 

the current record for _proving_ primality of a number that hasn't one of
the special forms (Mersenne etc.) using PRIMO is a 7760 digit prime. The
computation takes 6 months CPU on a 2.8GHz machine.
http://www.ellipsa.net/primo/record.html#01
See also:
http://mathworld.wolfram.com/PrimalityTest.html

If we are realistic, there is no way to run deterministic primality tests
for all large primes of general form in the OEIS (probably some 1000). I
also think that the fact that primes exceeding a few 1000 digits usually are
only strong probable primes is well known to the interested community and
that there is no need to mention this in every sequence addressing such big
primes. A corresponding remark/warning would be a candidate for the OEIS FAQ
or even the Welcome page.

On the other hand the probability that we actually get non-primes in
sequences generated with one of the state-of-the-art tools like PFGW or
Mathematica's or Maple's built-in probabilistic primality checks is by many
orders of magnitudes lower than the obviously present error-rate of the
OEIS, resulting from mouse-click-errors during cut and paste, line-feeds in
long numbers,  "don't remember from which of the 30 open windows I actually
grabbed the sequence", "can't read my own hand-written notes 1 hr after
midnight",  etc. From an efficiency point of view (reduce the overall error
rate of the OEIS) it is much more beneficial to browse through the OEIS with
open eyes and open mind and identify obvious bugs instead of trying to find
a hidden 1 in 10^20 chance hole in probable prime checking.

Finding such a hole in one of the production releases, e.g. of Proth or
PFGWPrimeForm would be a sensation and would cause a world-wide repair
campaign to fix the holes in all similar probabilistic primality checking
programs.

It might help if a remark identifying the tool that was used to find very
large primes is included in the comment of a sequence of such primes
(actually a parameter n such that some f(n) is prime). For me, alarm bells
would ring if someone not well known in the community would say "Found with
my revolutionary home-made super efficient prime checker"  Others can then
check the sequence using different tools. As far as I know submissions to
the "Largest Known Primes" list
http://www.utm.edu/research/primes/largest.html and
http://primes.utm.edu/primes/submit.php
are always cross-checked before being accepted. This list includes only
provable primes~>=10^50000, which currently ar all of the special form
(something that can easily be factored) +-1. There even is a rather
deterrent "Warning note: If it is discovered that you have submitted one or
more numbers that are not proven primes, you may lose the right to continue
submitting and/or have your credit for your primes reduced by sharing it
with those running our verification programs.  Please respect the integrity
of this database and the students / researchers that rely on it."

However I have serious doubts if we should install a similar mechanism for
the OEIS. It would contradict the very permissive policy of Neil to accept
sequences that is probably one of the key factors for the unparalleled
success of the OEIS.

In the special case of the repunit-related primes I can offer to X-check the
extended sequence terms (not the whole sequence!) with PFGW, if different
programs are used to create the extensions. This would not eliminate
omissions or gaps, but at least typos or the very,very unlikely case of a
non-prime passing a probable-prime check would be found with high
probability.

One additional remark: If one of us finds primes of general form exceeding
10^10000 he might consider to also submit the result to Henri & Renaud
Lifchitz's "Probable Primes Top 10000" at
http://www.primenumbers.net/prptop/prptop.php
Would be an interminable effort to harvest this page for extensions of OEIS
sequences.

Hugo