mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Closed Thread
 
Thread Tools
Old 2015-11-11, 02:30   #166
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22·7·11·29 Posts
Default

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?
LaurV is offline  
Old 2015-11-11, 03:10   #167
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

36328 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
a1call is offline  
Old 2015-11-11, 04:02   #168
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

111100110102 Posts
Default

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
a1call is offline  
Old 2015-11-11, 07:48   #169
schickel
 
schickel's Avatar
 
"Frank <^>"
Dec 2004
CDP Janesville

40628 Posts
Default

Quote:
Originally Posted by Batalov View Post
....

(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.
schickel is offline  
Old 2015-11-11, 15:08   #170
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·2,969 Posts
Default

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
CRGreathouse is offline  
Old 2015-11-11, 15:13   #171
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

593810 Posts
Default

Quote:
Originally Posted by a1call View Post
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.
CRGreathouse is offline  
Old 2015-11-11, 16:50   #172
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·7·139 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
a1call is offline  
Old 2015-11-11, 16:54   #173
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2×7×139 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
a1call is offline  
Old 2015-11-11, 17:07   #174
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2×3×151 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
danaj is offline  
Old 2015-11-11, 17:20   #175
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

202618 Posts
Default

Quote:
Originally Posted by a1call View Post
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
science_man_88 is offline  
Old 2015-11-11, 17:34   #176
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

593810 Posts
Default

Quote:
Originally Posted by a1call View Post
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.
CRGreathouse is offline  
Closed Thread

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Is CEMPLLA 1.5 "the only software in the world capable of discovering" something? Not really. CRGreathouse Number Theory Discussion Group 51 2018-12-16 21:55
Aouessare-El Haddouchi-Essaaidi "test": "if Mp has no factor, it is prime!" wildrabbitt Miscellaneous Math 11 2015-03-06 08:17
"Subproject" #10: 200k-300k to 110 digits RobertS Aliquot Sequences 9 2011-05-07 15:30
Would Minimizing "iterations between results file" may reveal "is not prime" earlier? nitai1999 Software 7 2004-08-26 18:12
Search for a number theoretic function related to "prime divisor sums" juergen Math 2 2004-07-10 23:01

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

Sat Nov 28 02:57:41 UTC 2020 up 79 days, 8 mins, 3 users, load averages: 0.70, 0.95, 1.05

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.