Primes of the form n+phi(n)
Is there a way for finding all the primes < 1000 (or greater bound) which have the form n+phi(n) (Just a reminder that phi is [URL="https://en.wikipedia.org/wiki/Euler's_totient_function"]Euler's Phi Function[/URL].) The first such primes of these forms are 15phi(15) = 7 and 15+phi(15) = 23. A list of numbers n such that nphi(n) and or n+phi(n) are prime would also help here. Thanks. :smile:

Do you want both prime?
Then n must be odd (and composite) and ... (this is [url]https://oeis.org/A068081[/url] ) [CODE]? forstep(n=1,1000,2,p=eulerphi(n);if(isprime(np),if(isprime(n+p),print(n" +"p" "np" "n+p)))) 15 +8 7 23 33 +20 13 53 35 +24 11 59 51 +32 19 83 65 +48 17 113 77 +60 17 137 91 +72 19 163 95 +72 23 167 143 +120 23 263 161 +132 29 293 177 +116 61 293 209 +180 29 389 213 +140 73 353 215 +168 47 383 217 +180 37 397 247 +216 31 463 255 +128 127 383 303 +200 103 503 335 +264 71 599 341 +300 41 641 371 +312 59 683 411 +272 139 683 427 +360 67 787 435 +224 211 659 447 +296 151 743 455 +288 167 743 533 +480 53 1013 545 +432 113 977 561 +320 241 881 573 +380 193 953 591 +392 199 983 611 +552 59 1163 665 +432 233 1097 707 +600 107 1307 713 +660 53 1373 717 +476 241 1193 779 +720 59 1499 803 +720 83 1523 871 +792 79 1663 917 +780 137 1697 933 +620 313 1553 965 +768 197 1733 [/CODE] Download and learn a few things about Pari/GP and you will be all set for many similar questions. If you want "or" and want to find them faster than using phi, then: One simple subset is: For n prime, phi(n)=n1 => nphi(n) is 1 (not prime) but 2*n1 will be frequently prime. 
You can find the first 1000 of the "and" version here:
[url]https://oeis.org/A068081[/url] 
P.S. (For "and" case) Interestingly, [B]n[/B] cannot be a multiple of 21 (or of 2, or of 9, 25... or more generally, must be squarefree. This is easily proven.)
More generally, if [B]n[/B] = p*q*... and p  phi(q), then [B]n[/B] is not in the sequence. The case of n = 2*a is a bit trickier. Either 3  n and then 2  phi(3) and [B]n[/B] is not in the sequence or 3 doesn't divide [B]n[/B], but then 3 divides either nphi(n) or either n+phi(n). 
All times are UTC. The time now is 14:44. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2020, Jelsoft Enterprises Ltd.