mersenneforum.org > Math Peculiar behaviour of prime numbers .....
 Register FAQ Search Today's Posts Mark Forums Read

 2009-07-17, 15:17 #1 spkarra   "Sastry Karra" Jul 2009 Bridgewater, NJ (USA) 338 Posts Peculiar behaviour of prime numbers ..... For the past three months, I am enthusiastically analyzing the known Mersenne’s Prime numbers and trying my best to look for some sort of commonality. During this process, I found out a peculiar characteristic of prime numbers. I am not sure if this is already proved by other mathematicians or not, but I would like to share with all of you. I ran my software program to test my conjucture. Due to my laptop technical restrictions, I could run from integer 1 thru integer 16. For some unknown reasons, when the integer value is 17, my Laptop is getting “Hung-Up”. So, I started testing from integer 18 onwards and after letting my Laptop run for more than 9 hrs, it is still unable to tell me if 19^19 minus 2 is a Prime or not. If this behaviour is not noticed earlier, then I will let my Laptop to run 24X7 for a week and see how far can I verify. ************************************************************************************************************************************* Conjucture: If p & q are positive primes, n is a positive integer and q = (p^p – 2^n), then the number of q’s are limited. ( I found only 8 Primes when ran from 2 thru 16). Example: 2^2 – 2^1 = 2 ; 2^2 – 2^2 = 0 ; - IGNORED SINCE q = ZERO; 3^3 – 2^1 = 25 – Not a Prime; 3^3 – 2^2 = 23 ; 3^3 – 2^3 = 19 ; 3^3 – 2^4 = 11 ; Here is the Screen Printout of all primes between 3 and 16 tested – found only there are 10 primes with this condition being satisfied. ----------------------------------------------------------------------------------------------------------------------------------------------- At Tue Jun 23 20:02:05 EDT 2009 Checking if 2 to power of 2 minus 2 2 is a PRIME.. --> 2 to power of 2 minus 2 = 2 is a PRIME.. FIRST ONE At Tue Jun 23 20:02:05 EDT 2009 Checking if 3 to power of 3 minus 2 = 25 is a PRIME.. At Tue Jun 23 20:02:05 EDT 2009 Checking if 3 to power of 3 minus 4 = 23 is a PRIME.. --> 3 to power of 3 minus 4 = 23 is a PRIME.. SECOND ONE At Tue Jun 23 20:02:05 EDT 2009 Checking if 3 to power of 3 minus 8 = 19 is a PRIME.. --> 3 to power of 3 minus 8 = 19 is a PRIME.. THIRD ONE At Tue Jun 23 20:02:05 EDT 2009 Checking if 3 to power of 3 minus 16 = 11 is a PRIME.. --> 3 to power of 3 minus 16 = 11 is a PRIME.. FOURTH ONE At Tue Jun 23 20:02:05 EDT 2009 Checking if 5 to power of 5 minus 2 = 3123 is a PRIME.. At Tue Jun 23 20:02:05 EDT 2009 Checking if 5 to power of 5 minus 4 = 3121 is a PRIME.. --> 5 to power of 5 minus 4 = 3121 is a PRIME.. FIFTH ONE At Tue Jun 23 20:02:05 EDT 2009 Checking if 5 to power of 5 minus 8 = 3117 is a PRIME.. At Tue Jun 23 20:02:05 EDT 2009 Checking if 5 to power of 5 minus 16 = 3109 is a PRIME.. --> 5 to power of 5 minus 16 = 3109 is a PRIME.. SIXTH ONE At Tue Jun 23 20:02:05 EDT 2009 Checking if 5 to power of 5 minus 32 = 3093 is a PRIME.. At Tue Jun 23 20:02:05 EDT 2009 Checking if 5 to power of 5 minus 64 = 3061 is a PRIME.. --> 5 to power of 5 minus 64 = 3061 is a PRIME.. SEVENTH ONE At Tue Jun 23 20:02:05 EDT 2009 Checking if 5 to power of 5 minus 128 = 2997 is a PRIME.. At Tue Jun 23 20:02:05 EDT 2009 Checking if 5 to power of 5 minus 256 = 2869 is a PRIME.. At Tue Jun 23 20:02:05 EDT 2009 Checking if 7 to power of 7 minus 2 = 823541 is a PRIME.. --> 7 to power of 7 minus 2 = 823541 is a PRIME.. EIGTH ONE At Tue Jun 23 20:02:08 EDT 2009 Checking if 7 to power of 7 minus 4 = 823539 is a PRIME.. At Tue Jun 23 20:02:08 EDT 2009 Checking if 7 to power of 7 minus 8 = 823535 is a PRIME.. At Tue Jun 23 20:02:08 EDT 2009 Checking if 7 to power of 7 minus 16 = 823527 is a PRIME.. At Tue Jun 23 20:02:08 EDT 2009 Checking if 7 to power of 7 minus 32 = 823511 is a PRIME.. At Tue Jun 23 20:02:08 EDT 2009 Checking if 7 to power of 7 minus 64 = 823479 is a PRIME.. At Tue Jun 23 20:02:08 EDT 2009 Checking if 7 to power of 7 minus 128 = 823415 is a PRIME.. At Tue Jun 23 20:02:08 EDT 2009 Checking if 7 to power of 7 minus 256 = 823287 is a PRIME.. At Tue Jun 23 20:02:08 EDT 2009 Checking if 11 to power of 11 minus 2 = 285311670609 is a PRIME.. At Tue Jun 23 20:02:08 EDT 2009 Checking if 11 to power of 11 minus 4 = 285311670607 is a PRIME.. At Tue Jun 23 20:02:10 EDT 2009 Checking if 11 to power of 11 minus 8 = 285311670603 is a PRIME.. At Tue Jun 23 20:02:10 EDT 2009 Checking if 11 to power of 11 minus 16 = 285311670595 is a PRIME.. At Tue Jun 23 20:02:10 EDT 2009 Checking if 11 to power of 11 minus 32 = 285311670579 is a PRIME.. At Tue Jun 23 20:02:10 EDT 2009 Checking if 11 to power of 11 minus 64 = 285311670547 is a PRIME.. At Tue Jun 23 20:02:10 EDT 2009 Checking if 11 to power of 11 minus 128 = 285311670483 is a PRIME.. At Tue Jun 23 20:02:10 EDT 2009 Checking if 11 to power of 11 minus 256 = 285311670355 is a PRIME.. At Tue Jun 23 20:02:10 EDT 2009 Checking if 13 to power of 13 minus 2 = 302875106592251 is a PRIME.. At Tue Jun 23 20:02:10 EDT 2009 Checking if 13 to power of 13 minus 4 = 302875106592249 is a PRIME.. At Tue Jun 23 20:02:10 EDT 2009 Checking if 13 to power of 13 minus 8 = 302875106592245 is a PRIME.. At Tue Jun 23 20:02:10 EDT 2009 Checking if 13 to power of 13 minus 16 = 302875106592237 is a PRIME.. At Tue Jun 23 20:02:10 EDT 2009 Checking if 13 to power of 13 minus 32 = 302875106592221 is a PRIME.. At Tue Jun 23 20:02:10 EDT 2009 Checking if 13 to power of 13 minus 64 = 302875106592189 is a PRIME.. At Tue Jun 23 20:02:10 EDT 2009 Checking if 13 to power of 13 minus 128 = 302875106592125 is a PRIME.. At Tue Jun 23 20:02:10 EDT 2009 Checking if 13 to power of 13 minus 256 = 302875106591997 is a PRIME.. At Thu Jun 25 07:15:28 EDT 2009 Checking if 19 to power of 19 minus 2 = 1978419655660313589123977 is a PRIME.. PROCESS Failed ----------------------------------------------------------------------------------------------------------------------------------------------- -- Thanks, Sastry Karra MS, MBA(MIS) "Good judgement comes from experience and experience comes from Bad judgement"
 2009-07-17, 15:46 #2 Mr. P-1     Jun 2003 7×167 Posts pari/gp confirms that 19^19-2 is prime. The result is instant. if your laptop is taking 9 hours then there is something wrong with your algorithm. Why do you not test past 2^n=256?
 2009-07-17, 16:06 #3 Mr. P-1     Jun 2003 7×167 Posts Incidentally for each $p$ there are about $\frac{p.ln(p)}{ln(2)}$ numbers to test, of which all but one are of the same magnitude as $p^p$. Ignoring that exception, then by the prime number theorem, you would expect about $\frac{2}{ln(2)}p$ primes. (The constant 2 in the numerator comes from the fact that none of these numbers are even). Your results look to be consistent with this distribution, but in truth, you've tested so few that nothing definite can be said. The infinite series for all prime p diverges (rather rapidly, in fact), and so I would expect there to be an infinitude of such primes, contrary to your conjecture. Whether anything can be proven, or whether there are any number-theoretical reasons to doubt my heuristic is beyond by mathematical ability. Last fiddled with by Mr. P-1 on 2009-07-17 at 16:10
 2009-07-17, 18:07 #4 CRGreathouse     Aug 2006 10111010110112 Posts Primes: Code: 2^2 - 2^1 3^3 - 2^2 3^3 - 2^3 3^3 - 2^4 5^5 - 2^2 5^5 - 2^4 5^5 - 2^6 7^7 - 2^1 7^7 - 2^13 17^17 - 2^6 17^17 - 2^20 17^17 - 2^30 17^17 - 2^40 17^17 - 2^64 19^19 - 2^1 19^19 - 2^5 23^23 - 2^66 23^23 - 2^76 31^31 - 2^77 31^31 - 2^97 41^41 - 2^38 41^41 - 2^214 47^47 - 2^60 47^47 - 2^72 53^53 - 2^30 53^53 - 2^50 59^59 - 2^100 61^61 - 2^91 61^61 - 2^327 67^67 - 2^193 73^73 - 2^177 73^73 - 2^189 73^73 - 2^293 83^83 - 2^22 83^83 - 2^116 83^83 - 2^272 83^83 - 2^274 83^83 - 2^290 83^83 - 2^366 83^83 - 2^436 97^97 - 2^407
2009-07-17, 18:37   #5
CRGreathouse

Aug 2006

3·1,993 Posts

Quote:
 Originally Posted by Mr. P-1 Incidentally for each $p$ there are about $\frac{p.ln(p)}{ln(2)}$ numbers to test, of which all but one are of the same magnitude as $p^p$. Ignoring that exception, then by the prime number theorem, you would expect about $\frac{2}{ln(2)}p$ primes. (The constant 2 in the numerator comes from the fact that none of these numbers are even). Your results look to be consistent with this distribution, but in truth, you've tested so few that nothing definite can be said.
You'd expect 2/log 2 primes per p, so $\frac{2p}{\log 2\log p}$ through p.

You can get a better estimate by considering their behavior mod 3, 5, ..., making the expectation
$\frac{2p}{\log 2\log p}\prod_{q\le p}1-\frac1q\approx\frac{2p}{e^\gamma\log2\log^2p},$
if I haven't made a mistake. Anyone want to test this against the numbers I've generated so far?
Code:
101^101 - 2^666
103^103 - 2^107
103^103 - 2^159
103^103 - 2^639
103^103 - 2^659
107^107 - 2^6
107^107 - 2^72
107^107 - 2^322
107^107 - 2^352
107^107 - 2^594
109^109 - 2^159
109^109 - 2^679
113^113 - 2^142
113^113 - 2^206
113^113 - 2^488
127^127 - 2^169
127^127 - 2^337
131^131 - 2^70
131^131 - 2^610
131^131 - 2^658
137^137 - 2^134
137^137 - 2^342
137^137 - 2^582
139^139 - 2^227
139^139 - 2^387
139^139 - 2^529
149^149 - 2^304
149^149 - 2^1036
151^151 - 2^181
157^157 - 2^11
157^157 - 2^655
163^163 - 2^263
163^163 - 2^315
163^163 - 2^1011
167^167 - 2^66
167^167 - 2^822
173^173 - 2^8
173^173 - 2^242
173^173 - 2^264
173^173 - 2^452
173^173 - 2^472
173^173 - 2^580
173^173 - 2^710

2009-07-17, 19:22   #6
Mr. P-1

Jun 2003

22218 Posts

Quote:
 Originally Posted by CRGreathouse You'd expect 2/log 2 primes per p
Why that number, and not p times it?

2009-07-17, 19:26   #7
CRGreathouse

Aug 2006

3·1,993 Posts

Quote:
 Originally Posted by Mr. P-1 Why that number, and not p times it?
log(p^p) = p log p, so you expect one in p log p to be prime (or two, because of their parity). There are log_2 p^p = p log p / log 2 per p, so 2 * (p log p / log 2) / (p log p) = 2/log 2.

For other 'small enough' primes there are only q-1 ways of being divisible by q, since q doesn't divide p^p and q doesn't divide 2^n. That's what the correction term is trying to do. It's actually not quite right, since I'm not sure how far to take 'small enough'. Maybe if I do an integral rather than a sum...?

2009-07-17, 19:41   #8
Mr. P-1

Jun 2003

7×167 Posts

Quote:
 Originally Posted by CRGreathouse log(p^p) = p log p, so you expect one in p log p to be prime (or two, because of their parity). There are log_2 p^p = p log p / log 2 per p, so 2 * (p log p / log 2) / (p log p) = 2/log 2.
You're right. I think I forgot to exponentiate p at some point.

 2009-07-20, 22:47 #9 spkarra   "Sastry Karra" Jul 2009 Bridgewater, NJ (USA) 33 Posts Thanks a lot .... In my conjecture, I mentioned that "the number of q’s are limited. ". Now, I found that there are more than I found.....

 Similar Threads Thread Thread Starter Forum Replies Last Post fivemack Factoring 3 2011-09-02 21:04 petrw1 PrimeNet 5 2011-01-14 18:01 Raman Puzzles 13 2010-02-13 05:25 jasong jasong 7 2009-01-01 00:50 fivemack Puzzles 7 2008-11-14 07:56

All times are UTC. The time now is 10:49.

Fri Jan 21 10:49:30 UTC 2022 up 182 days, 5:18, 0 users, load averages: 0.97, 1.23, 1.31