mersenneforum.org (https://www.mersenneforum.org/index.php)
-   -   How to create file to test primes automatically (https://www.mersenneforum.org/showthread.php?t=21065)

 PawnProver44 2016-03-05 19:07

How to create file to test primes automatically

I want to easily find primes of the form k*b^n+-c. However, manually testing the variables takes a long time. I am using Pfgw. Can someone please help create a file so I can always find the nearest k, n, or c values. For example, I want to find a prime of the form 43*71^n +300, (for large primes) and I do not want to manually test exponents, so is there a format file that tests primes of the form k*b^n+-c, so all I can do is just plug in the variables. Thanks for helping.

 Batalov 2016-03-05 21:20

[QUOTE=PawnProver44;428176]For example, I want to find a prime of the form 43*71^n +300, (for large primes) [/QUOTE]
...there are no primes of the form 43*71^n+300. 7 divides all of this sequence.

[SPOILER]Take (mod 7) of 43*71^n+300. To do that you can take mod 7 of each coefficient: 1*1^n+6, which is 7 = 0 (mod 7).[/SPOILER]

Anyway, this is just a poor example. The bigger problem is that if you find large enough (say, > 50,000 digits) prime candidates (probable primes), you will not be able to prove that they are prime. If you still want to search for these large PRPs, use [URL="http://www.mersenneforum.org/showthread.php?t=15833"]srsieve[/URL] to sieve. You can submit large PRPs to [URL="http://www.primenumbers.net/prptop/prptop.php"]PRP top[/URL].

 paulunderwood 2016-03-05 21:22

You need this sort of thing in your input file:

[CODE]ABC 43*71^\$a+300
1
2
3
4
5
6
...[/CODE]

Alternatively you can specify it with:

[CODE]ABC2 43*71^\$a+300
a: from 1 to 1000000
[/CODE]

Using the "-f" -- for factor -- flag will greatly improve your speed.

You might find that someone has written a sieve for this form.

A word of warning: To [i]prove[/i] a number prime you need at least 12.5% of the factorisation of N^2-1, where N is the number being proven. See [URL="http://primes.utm.edu/prove/"]this page[/URL]. Otherwise, general purpose proving algorithms, such as ECPP, work up to about 30k digits if you are very patient, whereas numbers that can be proven by BLS N+/-1 can be proved in minutes to hours.

 PawnProver44 2016-03-06 01:45

New Prime Form

And that form 43*71^n+300 is a bad example since it is divisible by 7, so I replaced the form with 24*181^n+229, anyways I created a file called input.txt and here were the following lines:

ABC2 24*181^\$a+229
a: from 1 to 3000
...

I then used the Pfgw (Win64Pfgw.exe) compatible command line and typed in:

input.txt

and gave me;

PFGW Version 3.7.10.32BIT.20150809.Win_Dev [GWNUM 28.6]

Error opening file input.txt

Do you know what went wrong? Please let me know.:smile:

 Batalov 2016-03-06 07:06

43*71^n+c has many [I]c[/I] values that generate all-composite sequences; they have a so-called covering set. But a few [I]c[/I] values are working fine, e.g. c=4.

For kicks and giggles I sieved the c=4 series and ran it for a while. There are a few small primes (43*71^0+4, 43*71^4+4, 43*71^144+4, 43*71^784+4) and then a larger unprovable PRP: [URL="http://factordb.com/index.php?query=71^38292*43%2B4"]43*71^38292+4[/URL] (submitted to PRPtop)
_________________________

[U]Re: "Error opening file input.txt"[/U]
Check where you put the input.txt file. Is it in the same folder as the pfgw executable? If not - provide the full path, or move it in the same folder.
Then put "-f -l input.txt" in the text window of Win64Pfgw.exe.
Works fine here, and quickly finds a few tiny primes
24*181^14+229
24*181^51+229

 PawnProver44 2016-03-07 04:29

Prptop

I am Trying to submit my own PRP, and I came up with the form: 60*79^n+19, known primes are for n = 0, 1, 3, 42, 91, 165, 585, 763, 2472, 3535, 3870, 5088. Do you know how to find the next term in less than 1 hour, if so what is it? (I tested exponents <10000) using pfgw.

:smile::smile::smile:

 Batalov 2016-03-07 20:37

It is not very large. You can find it yourself, if you try hard enough.
[SPOILER]It is already in the PRPtop.[/SPOILER]

 PawnProver44 2016-03-07 21:20

you submitted it, right?

 paulunderwood 2016-03-07 21:43

[QUOTE=PawnProver44;428260]I am Trying to submit my own PRP, and I came up with the form: 60*79^n+19, known primes are for n = 0, 1, 3, 42, 91, 165, 585, 763, 2472, 3535, 3870, 5088. Do you know how to find the next term in less than 1 hour, if so what is it? (I tested exponents <10000) using pfgw.

:smile::smile::smile:[/QUOTE]

Is 60*79^5088+19 really a "known prime" or does it merely have PRP status at the moment? :smile:

 Batalov 2016-03-07 21:52

[QUOTE=PawnProver44;428319]you submitted it, right?[/QUOTE]
Is the Pope Catholic? :rolleyes:

 PawnProver44 2016-03-07 22:03

[QUOTE=paulunderwood;428321]Is 60*79^5088+19 really a "known prime" or does it merely have PRP status at the moment? :smile:[/QUOTE]

Pfgw says it is a PRP-3, but I used other programs to prove the number prime, I am trying to find a larger term however.

 paulunderwood 2016-03-07 22:06

[QUOTE=PawnProver44;428326]Pfgw says it is a PRP-3, but I used other programs to prove the number prime, I am trying to find a larger term however.[/QUOTE]

What "other programs"? :smile:

 PawnProver44 2016-03-07 22:09

[QUOTE=paulunderwood;428327]What "other programs"? :smile:[/QUOTE]
WolframAlpha, PrimeGrid, and used BONIC.

 paulunderwood 2016-03-07 22:12

[URL="http://www.factordb.com/index.php?query=60*79^5088%2B19"]http://www.factordb.com/index.php?query=60*79^5088%2B19[/URL]

shows the number is PRP and will need to be proved with Primo in due course. :smile:

 PawnProver44 2016-03-07 22:45

[QUOTE=paulunderwood;428330][URL="http://www.factordb.com/index.php?query=60*79^5088%2B19"]http://www.factordb.com/index.php?query=60*79^5088%2B19[/URL]

shows the number is PRP and will need to be proved with Primo in due course. :smile:[/QUOTE]

How do we prove 60*79^5088+19 prime?

 paulunderwood 2016-03-07 22:57

With a program called [URL="http://www.ellipsa.eu/index.html"]Primo[/URL] (which only runs under Linux -- not Windoze) and it would take a day or two to do. :smile:

 PawnProver44 2016-03-08 00:06

[QUOTE=Batalov;428322]Is the Pope Catholic? :rolleyes:[/QUOTE]

There is no PRP of the form 60*79^n+19 in the PRPtop. Also, I am curious to find out, how long (approximately how many hours) Would it take to Completely sieve the series 60*79^n+19? (n from 15000 to 45000).

:smile::smile::smile:

 paulunderwood 2016-03-08 00:30

I don't know for sure, but sieving is about 5% of the time taken. You need to time an average PRP test, say (80% of 45000-15000) + 15000 i.e. n=39000 and then sieve until the elimination rate is about this time :smile:

ps. once you have sieved, you will not need the "-f" flag for PFGW.

 PawnProver44 2016-03-08 00:58

[QUOTE=paulunderwood;428343]I don't know for sure, but sieving is about 5% of the time taken. You need to time an average PRP test, say (80% of 45000-15000) + 15000 i.e. n=39000 and then sieve until the elimination rate is about this time :smile:

ps. once you have sieved, you will not need the "-f" flag for PFGW.[/QUOTE]

Wow, I started this from 3:00 p.m. to 4:00 p.m. and only eliminates 700 to 1000 exponents. :smile:

 All times are UTC. The time now is 02:45.