mersenneforum.org (https://www.mersenneforum.org/index.php)
-   carpetpool (https://www.mersenneforum.org/forumdisplay.php?f=145)
-   -   Primes of the form n+-phi(n) (https://www.mersenneforum.org/showthread.php?t=21969)

 carpetpool 2017-01-26 01:02

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 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. :smile:

 Batalov 2017-01-26 01:19

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(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
[/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)=n-1 => n-phi(n) is 1 (not prime) but 2*n-1 will be frequently prime.

 CRGreathouse 2017-01-26 01:29

You can find the first 1000 of the "and" version here:
[url]https://oeis.org/A068081[/url]

 Batalov 2017-01-26 01:29

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 square-free. 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 n-phi(n) or either n+phi(n).

 All times are UTC. The time now is 14:50.