mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   The "one billion minus 999,994,000" digits prime number (https://www.mersenneforum.org/showthread.php?t=20568)

 LaurV 2015-11-11 02:30

CRG means:
[QUOTE]Do you mean that you expect [TEX](a\cdot p\sharp+b)^c+d\ \ [/TEX] to be less than [TEX]p^2[/TEX] for judicious choices of [TEX]a[/TEX], [TEX]b[/TEX], [TEX]c[/TEX], and [TEX]d[/TEX]?[/QUOTE]

 a1call 2015-11-11 03:10

[QUOTE=LaurV;415762]CRG means:[/QUOTE]
There are infinite forms of sums possible, but in your example it seems that you would need to know what p the largest prime is, which is not necessary.
There is a small numeric example in my post 39 of what I mean. It is a small number but the concept applies to any size. There again you need a list of primes which is in fact not necessary.

for example you can use the form:
p=15!/(7^2) -7^x
and solve for x where p < 15^2 which will end up being p<13^2.
But you don't need to know that or the fact the largest prime factor is13. That is a very simple example.

A more improved form is the number format that i have given for the large primes I have listed, which is basically the sum of a multifactorial and a small primorial and the mutifactorial's number of "!" is equal to the primorial which gurantees co-prime-ness of the addends. It is no coincidence it yields a lot of primes. In fact try making the 2nd input in my WDP code a few times larger than the 1st and you are likely to run into composites very rarely in multi-k digits.Optimize the code/sums by some prime powers and converge to less than the square of the largest factor (not prime) and you are guaranteed primality. No other proof needed.

 a1call 2015-11-11 04:02

This is probably a better example/description for optimization of a simple example for small numbers:
p=2^y x 15!/(7^2) -7^x
and solve for x and y, where p < 15^2

ETA I myself can only solve for a much smaller, 4! of the format:

 schickel 2015-11-11 07:48

[QUOTE=Batalov;415674] ....

(and now Frank has another prime to prove, as he seems to enjoy doing them... ;-)[/QUOTE]Yeah, darn, you know funny how that works out. I just now started a GNFS job on a c152 that I've been putting off for far too long, and [i]it's[/i] currently occupying all my cores.

 CRGreathouse 2015-11-11 15:08

In any case the code you provided is just repeatedly testing numbers until it finds a prime. This doesn't take any special thought to derive, and it can be done much more efficiently by existing programs which sieve much further than your effective sieve.

The number in your sample code, for example, was the 49th that you tested.

 CRGreathouse 2015-11-11 15:13

[QUOTE=a1call;415767]Optimize the code/sums by some prime powers and converge to less than the square of the largest factor (not prime) and you are guaranteed primality. No other proof needed.[/QUOTE]

I'll believe it when I see it. The code you posted generated 48 composites before it hit on a prime.

 a1call 2015-11-11 16:50

[QUOTE=CRGreathouse;415806]In any case the code you provided is just repeatedly testing numbers until it finds a prime. This doesn't take any special thought to derive, and it can be done much more efficiently by existing programs which sieve much further than your effective sieve.

The number in your sample code, for example, was the 49th that you tested.[/QUOTE]
This is true if you consider the fact the the code tries values for k from 1 up P[SUB]n[/SUB]. k is the multiple of primonial. I was referring to the variables m (number of factors in the multifactorial) and n (number n in the P[SUB]n[/SUB]#) only when I said it results in more primes than composites given n is a small factor larger than m (say 8 times) for integers in the 2k digits range and less.

 a1call 2015-11-11 16:54

[QUOTE=CRGreathouse;415808]I'll believe it when I see it. The code you posted generated 48 composites before it hit on a prime.[/QUOTE]
I gave a 4! example already. I can guarantee you that there are more examples of the form that can be obtained programmatically for higher factorials with more primes factored out and multiplied to the the other addend.
It does not really make a difference if you believe this or not.

 danaj 2015-11-11 17:07

[QUOTE=CRGreathouse;415806]In any case the code you provided is just repeatedly testing numbers until it finds a prime. This doesn't take any special thought to derive, and it can be done much more efficiently by existing programs which sieve much further than your effective sieve.[/QUOTE]That was why I suggested nextprime, but maybe I should have made it clear I meant one that did sieving. You can tune the amount of sieving done to get good performance on average. I see now that it wasn't clear and people inferred I was talking about the naive algorithm (or naive + small wheel).

This is all way too complicated, with too many things floating around (e.g. are we still talking about 1000M digit primes? Is PrimeQ expected to be used? What is theorem 2?). The method being shown, using a PRP test (e.g. PrimeQ) is a terrible distraction. I don't think it's particularly interesting to people. I think a1call (OP) is saying this is related to his theorem 1 method, but not really it. We need to see it properly working then, with a single PrimeQ at the end that asserts "I have failed, something has gone terribly wrong, do not use this code!" if it ever fails.

On success we should get the number followed by some sort of container holding everything we need to prove it prime by theorem 1 (post 39, page 4): P_n, b_sign, c_sign, V. Let V be a vector of length n holding the exponents used by b and c, using their sign to denote B vs. C. That should let us reconstruct b and c and verify everything including d < (P_n)^2. This is just an example -- some other structure is fine as long as we can recover everything needed to show the result must be prime.

I know it isn't theorem 2, and the method isn't efficient enough to be a big deal, but at least it would stop the discussions of probability and probable prime tests.

 science_man_88 2015-11-11 17:20

[QUOTE=a1call;415826]I gave a 4! example already. I can guarantee you that there are more examples of the form that can be obtained programmatically for higher factorials with more primes factored out and multiplied to the the other addend.
It does not really make a difference if you believe this or not.[/QUOTE]

the problem is that most people typically don't care for just one example ( especially in numerical form for the more mathematical people on here). for example when proving there are infinitely many primes you wouldn't convince people with 2,3,5,..... 37 I guess there's an infinite amount. the proof by contradiction that numberphile on youtube presents is assume there's a complete list {p1,p2,...,pn} now multiply all the primes together and add 1. the result is either prime ( in which case it's not on the list) or composite in which case doesn't fully divide by any primes on the "complete" list so there must be a prime factor that's not already on the complete list which is a contradiction to it being complete.

 CRGreathouse 2015-11-11 17:34

[QUOTE=a1call;415826]I gave a 4! example already.[/QUOTE]

Every example you have posted is of the same general form: B + sk with a big number B and a small number s, with B + s, B + 2s, ..., B + (k-1)s all composite and B + sk prime. It looks exactly like what it is: a crude form of sieving with lots of primality tests.

All times are UTC. The time now is 11:35.