Recently I read the novel "The Solitude of Prime Numbers" where the main characters are somewhat compared to twin prime numbers ("always together, but never touching").

A twin prime is a prime number that is either 2 less or 2 more than another prime number —for example, the twin prime pair (41, 43). In other words, a twin prime is a prime that has a prime gap of two. Sometimes the term twin prime is used for a pair of twin primes; an alternative name for this is prime twin or prime pair. Wikipedia

Although I didn't like much the depressing novel, and since I have fallen into PPCG lately, that raised a question in my mind...

Task:

Given a positive integer number N > 4, find the lonely prime numbers (AKA isolated prime numbers) between the closest couples of twin primes.

Please note that in this case with the term lonely prime numbers, I mean all the prime numbers that are not twin primes and between couples of twin primes. That's why N > 4 because the first two couples of prime numbers are (3, 5) and (5, 7).

Example:

  1. N = 90.
  2. Find the first two couples of twin primes < N and > N. They are: (71, 73) and (101, 103).
  3. Find the lonely primes in the range > 73 and < 101.
  4. They are: 79, 83, 89, 97.

Special cases:

  • If N is in between two twin prime numbers, find the closest couples of twin primes > N+1 and < N-1. Example: N=72, find the closest couples of twin primes > 73 and < 71 then exclude from the list 71 and 73 because they are not lonely primes. So for N = 72 the expected result is: 67, 71, 73, 79, 83, 89, 97
  • If N belongs to a couple of twin primes, for example N = 73, the closest couples of twin primes are (71, 73) and (101, 103). If N = 71, the closest couples of twin primes are (59, 61) and (71, 73).

Test cases:

N = 70   >  Lonely primes are:  67
N = 71   >  Lonely primes are:  67
N = 72   >  Lonely primes are:  67, 79, 83, 89, 97 (not the twins 71 and 73)
N = 73   >  Lonely primes are:  79, 83, 89, 97 
N = 90   >  Lonely primes are:  79, 83, 89, 97
N = 201  >  Lonely primes are:  211, 223
N = 499  >  Lonely primes are:  467, 479, 487, 491, 499, 503, 509

Rules:

  • Write a full program or function that will take the number N from standard input.
  • Output the list of lonely primes in a readable format as csv, list, array, etc.
  • Shortest code wins.
  • Please include (when possible) a testable online fiddle.
  • 4
    What is the expected output for inputs like 71, 72 or 73? – Martin Ender Sep 27 '16 at 16:39
  • 1
    Lonely Prime AKA Isolated Prime – Digital Trauma Sep 27 '16 at 17:32
  • @MartinEnder I extended my question with special cases. Thanks for the clarification. – Mario Sep 27 '16 at 17:56
  • 1
    I find the special cases spoil the challenge a little (and were added when some answers had already been posted) – Luis Mendo Sep 27 '16 at 22:25
  • 1
    @JonathanAllan Yes you can consider N > 4 because the first two couples of twin prime numbers are (3, 5) and (5, 7). I addedd the specification to make it clear to everyone. – Mario Sep 28 '16 at 6:22
up vote 2 down vote accepted

Actually, 47 bytes

This solution deals with the case where n is between two twin primes, by checking if the lower bound is the larger of a pair of twin primes (eliminating the twin prime to the left of us from being our lower bound) and if the upper bound is the smaller of a pair of twin primes (eliminating the twin prime to the right of us from being our upper bound). To prevent the twin primes from being included in our range once we have the lower and upper bounds, we need to remove primes p where p-2 OR p+2 are prime, hence the logical OR and negate in the code.

This is a little long and can probably be golfed further. Golfing suggestions welcome. Try it online!

╗1`╜+;⌐p@p&`╓F╜+1`╜-;¬p@p&`╓F╜-x`;;¬p@⌐p|Y@p&`░

Ungolfing

╗         Store implicit input n in register 0.

1`...`╓   Get the first value x for which the following function f returns a truthy value.
  ╜         Push n from register 0.
  +         Add x to n.
  ;⌐        Duplicate n+x and add 2 to a copy of n+x.
  p         Check if n+x+2 is prime.
  @p        Swap n+x to TOS and check if n+x is prime.
  &         Logical AND the two results.
F         Push the first (and only) result of previous filtering
╜+        Add that result to n to get the upper bound for our solitude.

1`...`╓   Get the first value x for which the following function f returns a truthy value.
  ╜         Push n from register 0.
  -         Subtract x from n.
  ;¬        Duplicate n-x and subtract 2 from a copy of n-x.
  p         Check if n-x-2 is prime.
  @p        Swap n-x to TOS and check if n-x is prime.
  &         Logical AND the two results.
F         Push the first (and only) result of previous filtering.
╜-        Subtract that result from n to get the lower bound for our solitude.

x`...`░   Push values of the range [a...b] where f returns a truthy value. Variable m.
  ;;        Duplicate m twice.
  ¬p        Check if m-2 is prime.
  @⌐p       Check if m+2 is prime. 
  |Y        Logical OR the results and negate.
             This eliminates any numbers with neighboring primes.
  @p        Check if m is prime.
  &         Logical AND primality_check(m) and the previous negation.
             This keeps every other prime number in the range.
  • I don't get expected output 23 when input 24 is given. The twin prime bounds should be 17 / 19 and 29 / 31, and 23 is an isolated prime in the range 19 .. 29. – AdmBorkBork Sep 28 '16 at 15:33
  • @TimmyD Oh for the love of esolangs. Either the bug where p says 25 is prime hasn't been fixed yet, or Dennis hasn't pulled Actually since the bug fix. Let me go check. – Sherlock9 Sep 28 '16 at 19:17
  • @TimmyD As the bug fix was already completed, this answer is still valid as the main interpreter worked. It was just that the online interpreter, Try It Online, had not been updated yet. It has since been updated and TIO should work now. – Sherlock9 Sep 29 '16 at 4:41
  • Yep - thanks for the explanation! – AdmBorkBork Sep 29 '16 at 12:31

PowerShell v2+, 237 149 147 231 216 181 174 169 166 bytes

param($n)filter f($a){'1'*$a-match'^(?!(..+)\1+$)..'}for($i=$n;!((f $i)-and(f($i+2)))){$i++}for(){if(f(--$i)){if((f($i-2))-or(f($i+2))){if($i-lt$n-1){exit}}else{$i}}}

Takes input $n. Defines a new function f as the regex prime function (here returning a Boolean if the input is a prime or not).

The next part sets $i to be equal to $n, then loops upward until we find the bottom half of our twin prime pair upper bound. E.g., for input 90, this stops at $i=101.

Then, we loop from the upper bound downward. I know, it looks like an infinite loop, but it'll eventually end.

If the current number is a prime (f(--$i)), but its +/- 2 isn't a prime, we add $i to the pipeline. However, if its +/- 2 is a prime, we check whether we're lower than $n-1 (i.e., to account for the situation when it's inside a twin prime pair), at which point we exit. At program completion, the pipeline is printed to screen via implicit Write-Output.

NB - Due to the looping structure, prints the primes in descending order. OP has clarified that's OK.

Examples

Output here is space-separated, as that's the default stringification method for an array.

PS C:\Tools\Scripts\golfing> 70,71,72,73,90,201,499,982|%{"$_ --> "+(.\the-solitude-of-prime-numbers.ps1 $_)}
70 --> 67
71 --> 67
72 --> 97 89 83 79 67
73 --> 97 89 83 79
90 --> 97 89 83 79
201 --> 223 211
499 --> 509 503 499 491 487 479 467
982 --> 1013 1009 997 991 983 977 971 967 953 947 941 937 929 919 911 907 887

Haskell, 105 bytes

p x=all((>0).mod x)[2..x-1]
a%x=until(\z->p z&&p(z+2*a))(+a)x
f n=[x|x<-[(-1)%n+1..1%n-1],p x,1%x>x,(-1)%x<x]

Try it Online

JavaScript, 186 183 168 158 Bytes

// solution:
function d(d){function p(n){for(i=n;n%--i;);return!--i}u=d;for(;!p(d--)||!p(--d););for(;!p(u++)||!p(++u););for(;++d<u;)if(p(d)&&!p(d-2)&&!p(d+2))console.log(d)}

// runnable test cases:
console.info('Test ' + 70);
d(70);
console.info('Test ' + 71);
d(71);
console.info('Test ' + 72);
d(72);
console.info('Test ' + 73);
d(73);
console.info('Test ' + 90);
d(90);
console.info('Test ' + 201);
d(201);
console.info('Test ' + 499);
d(499);

  • Welcome to PPCG! Nice first answer. – AdmBorkBork Sep 28 '16 at 16:02

PHP, 207 bytes

47 54 bytes for the is_prime function that PHP does not have. I´d beat Mathematica without that. :-D

function p($n){for($i=$n>1?$n:4;$n%--$i;);return$i<2;}if(p($n=$argv[1])&p($n+2)|$z=p($n-1)&p($n+1))$n-=2;for($n|=1;!p($n)|!p($n-2);$n--);for($z++;$z--;$n+=2)for(;$n+=2;)if(p($n)){if(p($n+2))break;echo"$n,";}

run with -r. prints a trailing comma.

breakdown

// is_prime function:
// loops from $n-1 down to 1, breaks if it finds a divisor.
// returns true if divisor is <2 (==1)
// special case $n==1: initialize $i=4 to prevent warnings
function p($n){for($i=$n>1?$n:4;$n%--$i;);return$i<2;}

// is $n between primes?
if($z=p(1+$n=$argv[1])&p($n-1)) // set $z to go to the _second_ twin pair above
    $n-=2;
// no:
else
    if(p($n)&p($n+2))$n-=2;     // $n is part of the upper pair
    // p($n)&p($n-2):           // $n is part of the lower pair
    // else:                    // this is a lonely (isolated) prime

// 1. find closest twins <=$n
for($n|=1;!p($n)|!p($n-2);$n--);

// 2. list primes until the next twin primes
L:
for(;$n+=2;)if(p($n))
    if(p($n+2))break;       // next twin primes found: break loop
    else echo"$n,";         // isolated prime: print

// 3. if ($z) repeat (once)
$n+=2;  // skip twin pair
if($z--)goto L;

Note:

The is_prime function actually returns true for $n<2; but at least it doesn´t produce a warning. Insert $n= before $n>1 to fix.

Mathematica, 169 157 bytes

Select[PrimeQ]@Sort@Flatten@{If[q@#,0,#],Most@NestWhileList[i-=2;#+i&,#,!q@#&]&/@(i=3;q=PrimeQ@#&&Or@@PrimeQ[{2,-2}+#]&;#+{1,-1}(1+Boole@PrimeQ[{1,-1}+#]))}&

Racket 228 bytes

(λ(n)(let*((t 0)(lr(λ(l i)(list-ref l i)))(pl(drop(reverse(for/list((i(in-naturals))#:when(prime? i)#:final(and(> i n)
(= 2(- i t))))(set! t i)i))2)))(for/list((i(length pl))#:break(= 2(-(lr pl i)(lr pl(add1 i)))))(lr pl i))))

Disadvantage of this version is that it finds all prime numbers till N and not just those around N.

Ungolfed version:

(define (f n)
  (let* ((t 0)
         (lr (λ(l i) (list-ref l i)))
         (pl (drop(reverse  
                   (for/list ((i (in-naturals))
                              #:when (prime? i)
                              #:final (and
                                       (> i n)
                                       (= 2 (- i t))))
                     (set! t i)
                     i)) 2)))
    (for/list ((i (length pl))
               #:break (= 2 (- (lr pl i) (lr pl (add1 i)))) )
      (lr pl i)))
)

Testing:

(f 90)

Output:

'(97 89 83 79)

Racket 245 bytes

(λ(n)(let((pl(reverse(let lp((n n)(t 0)(ol '()))(set! t(prev-prime n))(if(and(>(length ol)0)
(= 2(-(car ol)t)))(cdr ol)(lp t 0(cons t ol)))))))(let lq((n n)(t 0)(ol pl))(set! t(next-prime n))
(if(= 2(- t(car ol)))(cdr ol)(lq t 0(cons t ol))))))

Ungolfed version:

(require math)
(define f
  (lambda(n)
    (let ((pl 
           (reverse
            (let loop ((n n) (t 0) (ol '()))
              (set! t (prev-prime n))
              (if (and
                   (> (length ol) 0)
                   (= 2 (- (car ol) t)))
                  (cdr ol)
                  (loop t 0 (cons t ol)))))))
      (let loop2 ((n n) (t 0) (ol pl))
        (set! t (next-prime n))
        (if (= 2 (- t (car ol)))
            (cdr ol)
            (loop2 t 0 (cons t ol))))))
  )

(f 90)

Output:

'(97 89 83 79)

Python 2.7: 160 bytes

t=lambda n:all(n%d for d in range(2,n))
def l(n):
 i=n
 while t(i)*t(i+2)-1:i+=1
 while t(n)*t(n-2)-1:n-=1
 print[x for x in range(n,i)if t(x)&~(t(x-2)|t(x+2))]

suggestions are welcome :)

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.