mersenneforum.org The "one billion minus 999,994,000" digits prime number
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2015-11-11, 02:30   #166
LaurV
Romulan Interpreter

Jun 2011
Thailand

22·7·11·29 Posts

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

2015-11-11, 03:10   #167
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

36328 Posts

Quote:
 Originally Posted by LaurV CRG means:
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.

 2015-11-11, 04:02 #168 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 36328 Posts 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: Link Last fiddled with by a1call on 2015-11-11 at 04:40
2015-11-11, 07:48   #169
schickel

"Frank <^>"
Dec 2004
CDP Janesville

2×1,049 Posts

Quote:
 Originally Posted by Batalov .... (and now Frank has another prime to prove, as he seems to enjoy doing them... ;-)
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 it's currently occupying all my cores.

 2015-11-11, 15:08 #170 CRGreathouse     Aug 2006 2·2,969 Posts 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. Last fiddled with by CRGreathouse on 2015-11-11 at 15:11
2015-11-11, 15:13   #171
CRGreathouse

Aug 2006

173216 Posts

Quote:
 Originally Posted by a1call 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.
I'll believe it when I see it. The code you posted generated 48 composites before it hit on a prime.

2015-11-11, 16:50   #172
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

111100110102 Posts

Quote:
 Originally Posted by CRGreathouse 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.
This is true if you consider the fact the the code tries values for k from 1 up Pn. 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 Pn#) 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.

2015-11-11, 16:54   #173
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

2·7·139 Posts

Quote:
 Originally Posted by CRGreathouse I'll believe it when I see it. The code you posted generated 48 composites before it hit on a prime.
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.

2015-11-11, 17:07   #174
danaj

"Dana Jacobsen"
Feb 2011
Bangkok, TH

2×3×151 Posts

Quote:
 Originally Posted by CRGreathouse 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.
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.

Last fiddled with by danaj on 2015-11-11 at 17:09

2015-11-11, 17:20   #175
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts

Quote:
 Originally Posted by a1call 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.
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.

Last fiddled with by science_man_88 on 2015-11-11 at 17:20

2015-11-11, 17:34   #176
CRGreathouse

Aug 2006

2·2,969 Posts

Quote:
 Originally Posted by a1call I gave a 4! example already.
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.

 Similar Threads Thread Thread Starter Forum Replies Last Post CRGreathouse Number Theory Discussion Group 51 2018-12-16 21:55 wildrabbitt Miscellaneous Math 11 2015-03-06 08:17 RobertS Aliquot Sequences 9 2011-05-07 15:30 nitai1999 Software 7 2004-08-26 18:12 juergen Math 2 2004-07-10 23:01

All times are UTC. The time now is 03:05.

Sat Nov 28 03:05:23 UTC 2020 up 79 days, 16 mins, 3 users, load averages: 1.05, 1.13, 1.11