mersenneforum.org Primes of the form n+-phi(n)
 Register FAQ Search Today's Posts Mark Forums Read

 2017-01-26, 01:02 #1 carpetpool     "Sam" Nov 2016 311 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 15-phi(15) = 7 and 15+phi(15) = 23. A list of numbers n such that n-phi(n) and or n+phi(n) are prime would also help here. Thanks.
 2017-01-26, 01:19 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 216448 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(n-p),if(isprime(n+p),print(n" +-"p" "n-p" "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 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)=n-1 => n-phi(n) is 1 (not prime) but 2*n-1 will be frequently prime. Last fiddled with by Batalov on 2017-01-26 at 01:21
 2017-01-26, 01:29 #3 CRGreathouse     Aug 2006 31·191 Posts You can find the first 1000 of the "and" version here: https://oeis.org/A068081
 2017-01-26, 01:29 #4 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 216448 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 square-free. 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 n-phi(n) or either n+phi(n). Last fiddled with by Batalov on 2017-01-26 at 01:48

 Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 sweety439 162 2020-05-15 18:33 JeppeSN And now for something completely different 27 2018-04-12 14:20 PawnProver44 Homework Help 1 2016-03-15 22:39 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:17.

Sun Sep 20 09:17:20 UTC 2020 up 10 days, 6:28, 0 users, load averages: 1.84, 1.63, 1.51