| sweety439 |
2021-06-28 09:24 |
[URL="https://raw.githubusercontent.com/xayahrainie4793/text-file-stored/main/k%3E%3D2%20such%20that%20Phi(n%2Ck)%20is%20prime"]this[/URL] is a list for all 2<=k<=4096 such that Phi(n,k) is prime. We noticed that there are 13 numbers 2<=k<=4096 such that Phi(1270,k) is prime, but for n=1271, there are only two numbers 2<=k<=4096 such that Phi(n,k) is prime, while for n=1272, there are 21 such numbers, and for n=1273, there are five such numbers.
The expected number of 2<=k<=N such that Phi(n,k) is prime is (N^(1/eulerphi(n)))/ln(N) (reference: [URL="https://oeis.org/wiki/User:Charles_R_Greathouse_IV/Tables_of_special_primes"]https://oeis.org/wiki/User:Charles_R_Greathouse_IV/Tables_of_special_primes[/URL]), however, this formula is only dependent to eulerphi(n), but if n makes n+1 prime, then the expected number should be less, since there is a large possibility (when znorder(k,n+1) = n, i.e. n+1 has 1st order cyclic number in base k) that n+1 divides Phi(n,k), and if n makes 2*n+1 is prime, there is a possibility (when znorder(k,2*n+1) = n, i.e. 2*n+1 has 2nd order cyclic number in base k) that 2*n+1 divides Phi(n,k), and if n makes 3*n+1 is prime, there is a possibility (when znorder(k,3*n+1) = n, i.e. 3*n+1 has 3rd order cyclic number in base k) that 3*n+1 divides Phi(n,k), ..., and if n makes r*n+1 is prime, there is a possibility (when znorder(k,r*n+1) = n, i.e. r*n+1 has rth order cyclic number in base k) that r*n+1 divides Phi(n,k), and the possibility become smaller when r become larger, and the possibility is largest when r=1, then r=2, then r=3, ..., thus, for n=61, 77, 93, and 99 (all these n has eulerphi(n)=60), (the true excepted number)/((N^(1/eulerphi(n)))/ln(N)) should be largest when r=61, then 93, then 77, and smallest for 99, since the smallest r such that 61*r+1 is 6, while for 77 and 93 this r is 4, and for 77, r=6 also makes prime, but for 93, r=6 does not make prime, and for 99 this r is only 2 (Phi(99,k) has large possibility to divisible by 2*99+1 = 199, when integer k>=2 is random, thus has less possibility to be prime then Phi(n,k) for n=61, 77, 93), also, for some values of n, there is a possibility that gpf(n) (greatest prime factor of n) divides Phi(n,k), i.e. gcd(Phi(n,k),n) is not 1, thus, what is the more accurate formula of the expected number of 2<=k<=N such that Phi(n,k) is prime? Also, what is the expected smallest k>=2 such that Phi(n,k) is prime?
|
