18
\$\begingroup\$

I am 2/3 twins with my brother, i.e. born on the same day of the same month but twelve years later. When I was 5, he was 17, both primes; the last pair of ages we can reasonably count on is [71, 83] with both of us being alive and able to celebrate this coincidental jubilee.

Task

Create a code that

  • takes two integers as input: the difference between the counter and the "twin" as a positive integer k (well yes, I'm the younger) and the upper bound as a positive integer u (runtime consideration)

  • and gives output as an array or list of all i numbers lower than or equal u for which both i and i+k are primes. The output does not need to be sorted.

Test Cases

12, 1000 -> [5, 7, 11, 17, 19, 29, 31, 41, 47, 59, 61, 67, 71, 89, 97, 101, 127, 137, 139, 151, 167, 179, 181, 199, 211, 227, 229, 239, 251, 257, 269, 271, 281, 337, 347, 367, 389, 397, 409, 419, 421, 431, 449, 467, 479, 487, 491, 509, 557, 587, 601, 607, 619, 631, 641, 647, 661, 727, 739, 757, 761, 797, 809, 811, 827, 907, 929, 941, 971, 997]
2, 999 -> [3, 5, 11, 17, 29, 41, 59, 71, 101, 107, 137, 149, 179, 191, 197, 227, 239, 269, 281, 311, 347, 419, 431, 461, 521, 569, 599, 617, 641, 659, 809, 821, 827, 857, 881]
3, 1500 -> [2]
30, 1500 -> [7, 11, 13, 17, 23, 29, 31, 37, 41, 43, 53, 59, 67, 71, 73, 79, 83, 97, 101, 107, 109, 127, 137, 149, 151, 163, 167, 181, 193, 197, 199, 211, 227, 233, 239, 241, 251, 263, 277, 281, 283, 307, 317, 337, 349, 353, 359, 367, 379, 389, 401, 409, 419, 431, 433, 449, 457, 461, 479, 491, 541, 547, 557, 563, 569, 571, 577, 587, 601, 613, 617, 631, 643, 647, 653, 661, 709, 727, 739, 743, 757, 797, 809, 823, 827, 829, 853, 857, 877, 881, 907, 911, 937, 941, 947, 953, 967, 983, 991, 1009, 1019, 1021, 1031, 1033, 1039, 1061, 1063, 1087, 1093, 1123, 1151, 1163, 1171, 1187, 1193, 1201, 1229, 1249, 1259, 1277, 1289, 1291, 1297, 1399, 1409, 1423, 1429, 1451, 1453, 1459, 1481, 1493]

Edit

Since I failed to specify the upper bound, both inclusive and exclusive solutions are welcome.

Edit No. 2

The challenge ends on 1st September, one week from the start.
Looks like we have a winner but in case of a tie popularity is the tie-breaker; in this case the "second" will be compensated via bounty.

\$\endgroup\$

19 Answers 19

5
\$\begingroup\$

Jelly, 8 7 bytes

+ÆR©_f®

Try it online!

Explanation

+          add the upper bound and the difference
 ÆR        find all primes up to that number
   ©       save that in the register
    _      subtract the difference from each
     f®    remove anything not in the original prime list
\$\endgroup\$
  • \$\begingroup\$ Congratulations @Pietu1998 ! \$\endgroup\$ – user3819867 Sep 1 '16 at 8:13
6
\$\begingroup\$

Brachylog, 27 23 bytes

:1f
hS,?tye.:S+:.L*$pL,

Try it online!

Verify all testcases.

Predicate 0 (main predicate)

:1f                     Find all solutions of predicate 1
                        given Input as Input,
                        Unify Output with the set of all solutions.

Predicate 1 (auxiliary predicate)

hS,?tye.:S+:.L*$pL,

hS                      the first element of Input is S,
   ?tye.                Output is an element between 0 and
                        the last element of Input,
       .:S+:.L          The list [Output+S,Output] is L,
             L*$pL      The product of L, prime-factorized, is still L
\$\endgroup\$
5
\$\begingroup\$

05AB1E, 9 bytes

Code:

LDpÏDI+pÏ

Uses the CP-1252 encoding. Try it online!.

\$\endgroup\$
4
\$\begingroup\$

Pyke, 10 bytes

S#_PiQ+_P&

Try it here!

S#         - filter(range(input_2), V) as i
  _P       -   is_prime(i)
         & -  ^ & V
    iQ+    -    i + input_1
       _P  -   is_prime(^)

Also 10 bytes:

S#_DP.IQ-P

Try it here!

\$\endgroup\$
  • \$\begingroup\$ Another 10-byte. \$\endgroup\$ – Leaky Nun Aug 25 '16 at 11:36
  • \$\begingroup\$ @LeakyNum that's actually really clever! \$\endgroup\$ – Blue Aug 25 '16 at 11:41
4
\$\begingroup\$

Octave, 34 33 bytes

@(k,u)(a=primes(u))(isprime(a+k))
\$\endgroup\$
  • \$\begingroup\$ Great approach! It allowed me to reduce frrom 11 to 8 bytes in my answer \$\endgroup\$ – Luis Mendo Aug 25 '16 at 10:31
4
\$\begingroup\$

MATL, 8 bytes

Credit to @alephalpha for his approach, which helped me save 3 bytes

Zqti+Zp)

Try it online!

Zq    % Take input implicitly. Vector of primes up to that. Call this vector A
ti+   % Duplicate, take second input, add element-wise. Call this vector B
Zp    % Vector containing true for prime numbers in B
)     % Use as an index into A. Display implicitly
\$\endgroup\$
4
\$\begingroup\$

Python 3, 114 92 90 bytes

Thanks to @Dennis for -2 bytes

def f(k,u):
 i=P=1;l={0}
 while i<u+k:l|={P%i*i};P*=i*i;i+=1
 return{i-k for i in l}&l-{0}

A function that takes input via argument and returns an unsorted set. This is exclusive with respect to the upper bound.

This uses the method in @xnor's answer here to find primes.

Try it on Ideone

How it works

Prime finding

We first initialise a test value i and a product P as 1, and a list of primes l as the set containing 0. Then, a while loop that tests all values of i in the range [1, u+k-1] for primality is executed. The idea is that by multiplying P by i^2 at the end of each iteration, P takes the value (i-1)!^2 while testing i, i.e the product of the integers [1, i+1] squared. The actual primality test is then performed by calculating P mod i; if this returns zero, then i cannot be prime since this implies that i is divisible by at least one of the values that make up the product. If this returns 1, then i must be prime since it is not divisible by any of the values in the product. If i is prime, it is appended to l, and if not, 0 is appended. The squaring of the product prevents false identification of 4 as prime, and is useful here since it guarantees that only 0 or 1 will be returned, allowing the choice of the value to be appended to be made by simply multiplying the result by i.

Identification of 'twin' primes

We now create a furter set, containing all the elements of l-k, element-wise. The intersection of this set and l is then found using &, which leaves a set containing only the elements common to both sets. A number i is only in both sets if both i and i+k are prime, meaning that this leaves the desired output. However, if k is prime, 0 will be present in both sets, meaning that this must be removed before returning.

\$\endgroup\$
  • 2
    \$\begingroup\$ k,u=input();i=P=1;l={0};exec'l|={P%i*i};P*=i*i;i+=1;'*(u+k);print{i-k for i in l}&l works for 83 bytes in Python 2. Even in 3, constructing a set this way should save some bytes. \$\endgroup\$ – Dennis Aug 26 '16 at 7:44
  • \$\begingroup\$ @Dennis Thanks - this does save a few bytes in Python 3. However, I did have to remove 0 from the final set, since if k is prime, this mistakenly gets returned. \$\endgroup\$ – TheBikingViking Aug 26 '16 at 17:23
3
\$\begingroup\$

R, 98 bytes

function(k,u){v=c();for(i in 1:u)if(sum(i%%(1:i)==0)==2&&sum((i+k)%%(1:(i+k))==0)==2){v=c(v,i)};v}

Ungolfed :

function(k,u)
v=c()                                                    #Empty vector

for(i in 1:u)
    if(sum(i%%(1:i)==0)==2&&sum((i+k)%%(1:(i+k))==0)==2) #If both i and i+k only have 
                                                         #2 divisors such as the rest of the 
                                                         #euclidian division is 0 
                                                         #(i.e., they're both prime) :
        v=c(v,i)
v
\$\endgroup\$
3
\$\begingroup\$

CJam, 17 bytes

Either as a full program:

q~{_mp\W$+mp&},p;

Try it online!

Or as an unnamed block:

{:X;{_mp\X+mp&},}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Java 7, 185 175 bytes

import java.util.*;List c(int k,int u){List l=new ArrayList();for(int i=1;++i<u;)if(p(i)&p(i+k))l.add(i);return l;}boolean p(int n){for(int i=2;i<n;)n=n%i++<1?0:n;return n>1;}

Ungolfed & test code:

Try it here.

import java.util.*;
class M{
  static List c(int k, int u){
    List l = new ArrayList();
    for(int i = 1; ++i < u; ){
      if(p(i) & p(i+k)){
        l.add(i);
      }
    }
    return l;
  }

  static boolean p(int n){
    for(int i = 2; i < n; ){
      n = n % i++ < 1
           ? 0
           : n;
    }
    return n>1;
  }

  public static void main(String[] a){
    System.out.println(c(12, 1000));
    System.out.println(c(2, 999));
    System.out.println(c(3, 1500));
    System.out.println(c(30, 1500));
  }
}

Output:

[5, 7, 11, 17, 19, 29, 31, 41, 47, 59, 61, 67, 71, 89, 97, 101, 127, 137, 139, 151, 167, 179, 181, 199, 211, 227, 229, 239, 251, 257, 269, 271, 281, 337, 347, 367, 389, 397, 409, 419, 421, 431, 449, 467, 479, 487, 491, 509, 557, 587, 601, 607, 619, 631, 641, 647, 661, 727, 739, 757, 761, 797, 809, 811, 827, 907, 929, 941, 971, 997]
[3, 5, 11, 17, 29, 41, 59, 71, 101, 107, 137, 149, 179, 191, 197, 227, 239, 269, 281, 311, 347, 419, 431, 461, 521, 569, 599, 617, 641, 659, 809, 821, 827, 857, 881]
[2]
[7, 11, 13, 17, 23, 29, 31, 37, 41, 43, 53, 59, 67, 71, 73, 79, 83, 97, 101, 107, 109, 127, 137, 149, 151, 163, 167, 181, 193, 197, 199, 211, 227, 233, 239, 241, 251, 263, 277, 281, 283, 307, 317, 337, 349, 353, 359, 367, 379, 389, 401, 409, 419, 431, 433, 449, 457, 461, 479, 491, 541, 547, 557, 563, 569, 571, 577, 587, 601, 613, 617, 631, 643, 647, 653, 661, 709, 727, 739, 743, 757, 797, 809, 823, 827, 829, 853, 857, 877, 881, 907, 911, 937, 941, 947, 953, 967, 983, 991, 1009, 1019, 1021, 1031, 1033, 1039, 1061, 1063, 1087, 1093, 1123, 1151, 1163, 1171, 1187, 1193, 1201, 1229, 1249, 1259, 1277, 1289, 1291, 1297, 1399, 1409, 1423, 1429, 1451, 1453, 1459, 1481, 1493]
\$\endgroup\$
2
\$\begingroup\$

PARI/GP, 39 bytes

k->u->[x|x<-primes([1,u]),isprime(x+k)]
\$\endgroup\$
2
\$\begingroup\$

Mathematica, 43 bytes

(Prime@Range@PrimePi@#2+#)~Select~PrimeQ-#&

Generate all primes less than or equal to the upper bound. Add the difference of ages to the result. Select prime numbers among them. Subtract the difference of ages to the result.

\$\endgroup\$
2
\$\begingroup\$

Swift, 142 bytes

func f(a:Int,b:Int)->Array<Int>{let p={(n:Int)->Int in([Int]()+(2..<n)).filter{n%$0<1}.count}
return([Int]()+(2...b)).filter{p($0)+p($0+a)<1}}
\$\endgroup\$
2
\$\begingroup\$

Perl 6,  39  37 bytes

->\k,\u{grep {($_&$_+k).is-prime},2..u}
->\k,\u{grep {($_&$_+k).is-prime},^u}

Explanation:

-> \k, \u {

  # find all the values
  grep

  # where
  {
    # 「all」 junction of the two values
    ( $_   &   $_ + k ) # 「 all( $_, $_ + k ) 」

    # autothread a method call against the junction
    .is-prime
  },

  # from the values up to (and excluding) 「u」
  ^ u # short for 「 0 ..^ u 」
  # for inclusive use 「 2 .. u 」

}
\$\endgroup\$
2
\$\begingroup\$

S.I.L.O.S, 205 bytes

GOTO b
funce
n = p
p - 1
f = 1
lbla
f * p
f % n
p - 1
if p a
return
lblb
readIO 
s = i
readIO 
i - 2
lblc
i + 1
p = i
GOSUB e
F = f
p = i
p + s
GOSUB e
F * f
if F g
GOTO h
lblg
printInt i
lblh
i - 2
if i c

Try it online!

Primalty test by Wilson's theorem.

\$\endgroup\$
1
\$\begingroup\$

Actually, 12 bytes

Input is u then k. Golfing suggestions welcome. Try it online!

╖R`;p@╜+p*`░

Ungolfing:

╖              Store k in register 0.
 R             Range [1..u]
  `       `░   Start a function f and push values i of the range where f(i) is truthy.
   ;p@         Duplicate i, check if i is prime, and swap with the other i.
      ╜+p      Push k, add to i, check if i+k is prime.
         *     Multiply the two if results together.
                 Similar to logical AND. 1 if both are true, else 0.
\$\endgroup\$
1
\$\begingroup\$

R, 104 bytes

Unlike the other R solution posted, this one takes input from stdin.

s=scan();sapply(1:s[2],function(i){j=i+s[1];if((all(i%%(3:i-1)!=0)|i==2)&all(j%%(3:j-1)!=0))cat(i," ")})

Ungolfed:

s=scan();        # Read from stdin
sapply(1:s[2],   # For i from 1 to u,
    function(i){     # apply this function:
        j=i+s[1];                # Define i+k
        if((all(i%%(3:i-1)!=0)   # Test if i is prime
           | i==2)               # (i is prime if i==2)
           & all(j%%(3:j-1)!=0)) # Test if i+k is prime
        cat(i," ")               # If i and i+k are prime, print i
    }
)
\$\endgroup\$
1
\$\begingroup\$

Javascript (ES6), 90 83 80 75 bytes

(k,u)=>(r=n=>n++<u+k?r(P[P.every(i=>n%i)*n]=n):P.filter(n=>P[n+k]))(1,P=[])

Example:

let F =
(k,u)=>(r=n=>n++<u+k?r(P[P.every(i=>n%i)*n]=n):P.filter(n=>P[n+k]))(1,P=[])

console.log(F(2, 999))

\$\endgroup\$
1
\$\begingroup\$

Pyth, 13 bytes

f&P_TP_+ThQSe

A program that takes input of a list of the form [k, u] and prints a list.

Try it online

How it works

f&P_TP_+ThQSe  Program. Input: Q
           Se  1-indexed range up to Q[1], yielding [1, 2, 3, ..., u]
f              Filter that, using variable T, by:
  P_T           T is prime
 &              and
     P_+ThQ     T+Q[0], i.e. T+k, is prime
               Implicitly print
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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