mersenneforum.org Primes of the form ((p^p)%p#)/p
 Register FAQ Search Today's Posts Mark Forums Read

 2022-04-30, 16:12 #1 kijinSeija   Mar 2021 France 2·17 Posts Primes of the form ((p^p)%p#)/p Have these kinds of prime numbers been studied ? I found nothing on factordb and OEIS. I use the % for the modulo operation and # for the primorial numbers. I used PFGW and I found these primes and PRP : Code: (((3^3)%3#)/3) is Unity (1) (((5^5)%5#)/5) is Unity (1) (((7^7)%7#)/7) is trivially prime!: 19 (((11^11)%11#)/11) is trivially prime!: 151 (((13^13)%13#)/13) is trivially prime!: 631 (((29^29)%29#)/29) is trivially prime!: 21946681 Switching to Exponentiating using GMP (((41^41)%41#)/41) is 3-PRP! (0.0000s+0.0129s) (((43^43)%43#)/43) is 3-PRP! (0.0000s+0.0012s) (((47^47)%47#)/47) is 3-PRP! (0.0000s+0.0006s) (((71^71)%71#)/71) is 3-PRP! (0.0000s+0.0002s) (((167^167)%167#)/167) is 3-PRP! (0.0000s+0.0001s) (((241^241)%241#)/241) is 3-PRP! (0.0000s+0.0001s) (((257^257)%257#)/257) is 3-PRP! (0.0001s+0.0003s) (((367^367)%367#)/367) is 3-PRP! (0.0001s+0.0002s) Switching to Exponentiating using Woltman FFT's (((769^769)%769#)/769) is 3-PRP! (0.0015s+0.0001s) (((1031^1031)%1031#)/1031) is 3-PRP! (((1459^1459)%1459#)/1459) is 3-PRP! (((3533^3533)%3533#)/3533) is 3-PRP! (((4219^4219)%4219#)/4219) is 3-PRP! (((8933^8933)%8933#)/8933) is 3-PRP! (((14843^14843)%14843#)/14843) is 3-PRP!
 2022-04-30, 19:39 #2 kijinSeija   Mar 2021 France 2×17 Posts Code: (((30809^30809)%30809#)/30809) is 3-PRP! (((42017^42017)%42017#)/42017) is 3-PRP! Last fiddled with by kijinSeija on 2022-04-30 at 19:40
 2022-04-30, 20:39 #3 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 226610 Posts If I am not mistaking: An equivalent format would be p^(p-1) - n*p# where n is an integer which is not divisible by p. The result will always be divisible by p and never by any primes less than p. While results (after division by p) are less than p^2, they are guaranteed to be 1 or prime. Just above p^2 they have a good chance of being prime. As the results get exponentially larger than p^2 their likeliness of being prime approaches any other random integer of the same size range. AFAIK, they are not generally of a format that can be easily proven to be prime. Just my 2 cents && FWIW. :) Last fiddled with by a1call on 2022-04-30 at 20:47
 2022-04-30, 21:03 #4 Cybertronic     Jan 2007 Germany 49110 Posts Hello kijnSeija, this kind of numbers is me unknown. Problem is , a PRP number is hard to prove it. The only address for PRP numbers is http://www.primenumbers.net/prptop/prptop.php otherwise the numbers enqueue in hundreds of other formulas, but interesting ! best
 2022-04-30, 21:23 #5 kijinSeija   Mar 2021 France 2216 Posts thanks for your help and for the address Last fiddled with by kijinSeija on 2022-04-30 at 21:26
 2022-04-30, 23:45 #6 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 8DA16 Posts You can improve the probability of the numbers being Prime by replacing p^p with p^m for m>1 (the exponent being equal to p does not serve any purpose here). This will have the same mechanics but will over all yield smaller numbers (for the right m) which will be closer to p^2. In other words choose m such that it gives the smallest reminder (greater than p). Some results may be negative (if you add the n multiplier to the primorial and use subtraction rather than %) which you would have to change their sign. Last fiddled with by a1call on 2022-05-01 at 00:20
 2022-05-01, 14:14 #7 Dr Sardonicus     Feb 2017 Nowhere 134128 Posts In taking the remainder pk^m % pk-1# , you want pk^m > pk-1#. Thus m > log(pk-1#)/log(p). For p > 3, pk < pk-1#, so you get a remainder of p for m = 1. The number of possible remainders of pk^m modulo pk-1# is the multiplicative order h of pk modulo pk-1# and this is the lcm of the multiplicative orders of pk modulo pk-1, pk-2,... 2. I wrote a simple script to find the remainders of pk^m % pk-1# from the smallest m for which pk^m > pk-1# up to m = p-1. Code: ? lpr=log(2);pr=2;v=[];forprime(p=3,20,n=1+floor(lpr/log(p));v=vector(p-n,i,(p^(i+n-1))%pr);print(p" "pr" "v);pr*=p;lpr+=log(p);) 3 2 [1, 1] 5 6 [1, 5, 1] 7 30 [19, 13, 1, 7, 19] 11 210 [71, 151, 191, 1, 11, 121, 71, 151] 13 2310 [841, 1693, 1219, 1987, 421, 853, 1849, 937, 631] 17 30030 [23461, 8447, 23479, 8753, 28681, 7097, 529, 8993, 2731, 16397, 8479, 24023, 18001] 19 510510 [434059, 78961, 479239, 426871, 452899, 436921, 133339, 491401, 147439, 248791, 132439, 474301, 333049, 201811] ?

 Similar Threads Thread Thread Starter Forum Replies Last Post enzocreti enzocreti 0 2019-07-15 13:12 enzocreti enzocreti 7 2019-05-05 13:19 a1call Miscellaneous Math 6 2018-12-11 03:34 YuL Math 21 2012-10-23 11:06 Dougy Math 8 2009-09-03 02:44

All times are UTC. The time now is 09:48.

Sun Aug 14 09:48:30 UTC 2022 up 38 days, 4:35, 2 users, load averages: 1.28, 1.23, 1.11