mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > carpetpool

Reply
 
Thread Tools
Old 2017-01-26, 01:02   #1
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

31610 Posts
Post 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.
carpetpool is offline   Reply With Quote
Old 2017-01-26, 01:19   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22·2,281 Posts
Default

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
Batalov is offline   Reply With Quote
Old 2017-01-26, 01:29   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

72×112 Posts
Default

You can find the first 1000 of the "and" version here:
https://oeis.org/A068081
CRGreathouse is offline   Reply With Quote
Old 2017-01-26, 01:29   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22×2,281 Posts
Default

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
Batalov is offline   Reply With Quote
Reply

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 2020-05-15 18:33
Search primes of form 2*n^n ± 1 JeppeSN And now for something completely different 27 2018-04-12 14:20
Infinitely many primes of a form? PawnProver44 Homework Help 1 2016-03-15 22:39
Primes of the form a^(2^n)+b^(2^n) YuL Math 21 2012-10-23 11:06
Primes of the form 2.3^n+1 Dougy Math 8 2009-09-03 02:44

All times are UTC. The time now is 08:45.

Fri Oct 23 08:45:28 UTC 2020 up 43 days, 5:56, 0 users, load averages: 1.93, 1.36, 1.31

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.