20170126, 01:02  #1 
"Sam"
Nov 2016
2^{2}·79 Posts 
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 Euler's Phi Function.) 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.

20170126, 01:19  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3·3,041 Posts 
Do you want both prime?
Then n must be odd (and composite) and ... (this is https://oeis.org/A068081 ) 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 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. Last fiddled with by Batalov on 20170126 at 01:21 
20170126, 01:29  #3 
Aug 2006
13446_{8} Posts 
You can find the first 1000 of the "and" version here:
https://oeis.org/A068081 
20170126, 01:29  #4 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3×3,041 Posts 
P.S. (For "and" case) Interestingly, n 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 n = p*q*... and p  phi(q), then n is not in the sequence. The case of n = 2*a is a bit trickier. Either 3  n and then 2  phi(3) and n is not in the sequence or 3 doesn't divide n, but then 3 divides either nphi(n) or either n+phi(n). Last fiddled with by Batalov on 20170126 at 01:48 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Primes of the form (b+1)*b^n+1 and b^n+(b+1)  sweety439  sweety439  162  20200515 18:33 
Search primes of form 2*n^n ± 1  JeppeSN  And now for something completely different  27  20180412 14:20 
Infinitely many primes of a form?  PawnProver44  Homework Help  1  20160315 22:39 
Primes of the form a^(2^n)+b^(2^n)  YuL  Math  21  20121023 11:06 
Primes of the form 2.3^n+1  Dougy  Math  8  20090903 02:44 