11
\$\begingroup\$

Sexy Primes are pairs of numbers (n, m) such as n and m both are prime, and m = n + 6.

You need to create a function which will take an integer, check for sexy primes from 0 to that integer, and return an array of arrays.

For example, listSexy(30) must return [[5,11], [7,13], [11,17], [13,19], [17,23], [23,29]] or some equivalent.

This is so the program with the shortest bytecount wins!

\$\endgroup\$
  • \$\begingroup\$ Can you explain what the desired output format looks like? \$\endgroup\$ – Howard Jun 26 '12 at 14:34
  • 12
    \$\begingroup\$ Bah, I hate it when the challenge changes after answers have been submitted. \$\endgroup\$ – Griffin Jun 26 '12 at 15:25
  • 2
    \$\begingroup\$ Is there a certain reason to check from 0? Why shouldn't I check from (5,11)? A short definition of sexy primes should be given right here, while linking to Wikipedia for further reading is welcome. \$\endgroup\$ – user unknown Jun 27 '12 at 14:45
  • 5
    \$\begingroup\$ In Portuguese Sexy Primes translates to the same as Sexy Cousins! \$\endgroup\$ – sergiol Nov 6 '17 at 23:35
  • \$\begingroup\$ @sergiol haha... \$\endgroup\$ – Victor VosMottor thanks Monica Jul 28 at 10:50

32 Answers 32

12
\$\begingroup\$

MATLAB 32

i=1:n;i(isprime(i)&isprime(i+6))

n is your number

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ +1 That is the right tool for the job: isprime. Not that the op intended it. \$\endgroup\$ – Johannes Kuhn Nov 19 '13 at 7:34
  • \$\begingroup\$ This could be shortened by giving the isprime function a shorter name: i=1:n;p=@isprime;i(p(i)&p(i+6)) \$\endgroup\$ – Luis Mendo Jul 8 at 17:22
5
\$\begingroup\$

J, 34 33 31 32 39 37 characters

s=.[:(,.-&6)[:I.1([:*/p:)"1 i.,.6-~i.

Lost a character keeping both primes below the limit...and another 7 declaring a function.

Usage:

   s 100
11  5
13  7
17 11
19 13
23 17
29 23
37 31
43 37
47 41
53 47
59 53
67 61
73 67
79 73
89 83

Edit

Seems like a lot of the new answers are not creating functions, taking input or limiting both numbers in the pair to be below n - if I ignore those restrictions too I can get down to 28 characters:

(,.6&+)I.*/"1[1 p:(i.,.6+i.)
| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

Mathematica, 35

{#,#+6}&~Array~#~Cases~{__?PrimeQ}&
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

GolfScript, 32 characters

~),2>{:P{(.P\%}do(!},:L{6+L?)},p

Since the output format was not specified, the code above will print the lower prime of each pair. Thus a number x is included if x and x+6 are both prime and both are below n. Input is given as single number on STDIN.

> 150
[5 7 11 13 17 23 31 37 41 47 53 61 67 73 83 97 101 103 107 131]
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I think you should print both primes. It's a part of the task. \$\endgroup\$ – ugoren Jun 27 '12 at 8:45
  • 1
    \$\begingroup\$ @ugoren The task was changed after I submitted my version. I'll try and add that to my version soon. \$\endgroup\$ – Howard Jun 27 '12 at 9:14
  • \$\begingroup\$ Yes, your answer matches the original task. \$\endgroup\$ – ugoren Jun 27 '12 at 9:25
3
+100
\$\begingroup\$

05AB1E, 7 bytes

ÅPãʒÆ7+

Try it online or verify a few more test cases.

Explanation:

ÅP       # Push a list of primes smaller than or equal to the (implicit) input-integer
  ã      # Create all possible pairs by taking the cartesian product with itself
         # (which will include inverted duplicates - i.e. both [5,11] and [11,5])
   ʒ     # Filter this list of pairs [a,b] by:
    Æ    #  Reduce it by subtracting: a-b
     7+  #  Add 7
         #  (only 1 is truthy in 05AB1E, so this will keep pairs that satisfy a-b+7==1)
         # (after which the resulting list of pairs is output implicitly)
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Python 2, 137 132 126 122 118

f=lambda x:not[y for y in range(2,x)if x%y==0]
i=30
print [(x,y)for x in range(i)for y in range(i)if f(x)&f(y)&x-6==y]

Try it online!

Using list comprehensions, as well as the fact that [] = False

f(x) actually returns all the factors of x, and you can then work out prime-ness from that.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You can turn f(x) into f=lambda x:not[y for y in range(2,x)if x%y==0] to save a few characters. You can also reduce the ifs at the end of your list comprehension with f(x)&f(y)&(x-6==y). \$\endgroup\$ – beary605 Jul 20 '12 at 23:20
  • \$\begingroup\$ @beary605 I don't really know a lot about lamdas (well, I know nothing), so I'll look in to that, but yes, anda not ifs. \$\endgroup\$ – ACarter Jul 27 '12 at 21:32
  • \$\begingroup\$ A lambda is an anonymous function which returns a value. a=lambda x,y,z:(value here) is the same as def a(x,y,z):return (value here). \$\endgroup\$ – beary605 Jul 28 '12 at 3:21
  • \$\begingroup\$ Awesome, I seem to get the hang. Updated. Thanks! \$\endgroup\$ – ACarter Jul 28 '12 at 19:01
2
\$\begingroup\$

K3 / Kona, 45

{a@&6=(-).'a:,/a,\:/:a:&{(x>1)&&/x!'2_!x}'!x}

.

{a@&6=(-).'a:,/a,\:/:a:&{(x>1)&&/x!'2_!x}'!x}100
(11 5
 13 7
 17 11
 19 13
 23 17
 29 23
 37 31
 43 37
 47 41
 53 47
 59 53
 67 61
 73 67
 79 73
 89 83)

And the same solution in the current incarnation of K which is identical to the K3 solution except for the fact that it does not have an inbuilt mod operator, which adds about 14 chars for 59

{a@&6=(-).'a:,/a,\:/:a:&{(x>1)&&/{x-y*x div y}[x;2_!x]}'!x}
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Python (93 90 99 95)

Yay for quick and dirty isprime functions!

a=lambda x:all(x%i for i in range(2,x));b=2
while b<input():
 b+=1
 if a(b)&a(b+6):print b,b+6
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 1 instead of True will save you 3 characters... \$\endgroup\$ – Wooble Jun 26 '12 at 17:54
  • \$\begingroup\$ Why do I keep missing that? Fixed. \$\endgroup\$ – beary605 Jun 27 '12 at 5:44
  • \$\begingroup\$ You don't get a limit parameter. Also, [] in all() isn't needed (at least in Python 2.7). \$\endgroup\$ – ugoren Jun 27 '12 at 8:43
  • \$\begingroup\$ Wow, really? Cool! I will implement the parameter. \$\endgroup\$ – beary605 Jun 27 '12 at 14:13
  • \$\begingroup\$ I don't know why you subtract 1 from x, but you can remove that for 2 characters. Then you can replace the while loop with a for loops from 2 to input()+1 for another 2 characters. \$\endgroup\$ – JPvdMerwe Jul 20 '12 at 22:33
2
\$\begingroup\$

x86-Assembly (78 Bytes)

This example uses Intel syntax. Besides, here the fastcall or register calling convention is used (the latter from 32-bit Delphi), so the parameter is in ecx. I also introduce a second parameter that points to a free space for the result and is saved in edx. A function for allocating memory space would be specific to the operating system and a transfer via the stack would be problematic, so I chose this option.

listSexy:
   mov   ebp, esp      ; 89E5    Save initial esp
   mov   edi, edx      ; 89D7    Save second parameter in edx
   
   ; Part One: Save all prime numbers from 3 to the limit on the stack
   ; (This takes 32 Bytes)
   xor   eax, eax      ; 31C0    set eax = 1 (shorter than mov eax, 1)
   inc   eax           ; 40
checkComplete:
   add   eax, 2        ; 83C002  Go to next possible number (first is 3)
   cmp   eax, ecx      ; 39C8    Has the limit, i.e. the parameter, been skipped?
   jae   partTwo       ; 7316
   mov   ebx, esp      ; 89E3    Check it against all previous prime numbers
checkNext:             ;         which are stored between ebp and esp
   cdq                 ; 99      Clear edx for the later division
   push  eax           ; 50      Put the number on the stack
   cmp   ebx, ebp      ; 39E5    Has the check already completed?
   je    partTwo       ; 74F1    The comfirmed prime number remains on stack
   mov   esi, [ebx]    ; 8B33    Load a previous prime
   div   esi           ; F7F6
   pop   eax           ; 58
   test  edx, edx      ; 85D2    Is esi a divider?
   je    checkComplete ; 74E8
   add   ebx, 4        ; 83C304  Let ebx point to the next possible divisor
   jmp   checkNext     ; EBEC
   
   ; Part Zwo: Check all prime numbers if they are sexy primes
   ; (This takes 39 Bytes)
partTwo:
   mov   ebx, ebp      ; 89E5    Start with the first prime number, i.e. 3
NextPrime:
   sub   ebx, 4        ; 83EB04  Let ebx point to the next prime number
   cmp   ebx, esp      ; 39E3    Has the last number been reached? It cant be sexy,
                       ;         since it has no successors here
   jmp   Finished      ; 761E
   mov   edx, ebx      ; 89DA    Check all successors up to a distance of 6
   mov   eax, [ebx]    ; 8B03    eax is the prime number whose successors are checked
   add   eax, 6        ; 83C006
GoFurther:
   sub   edx, 4        ; 83EA04
   cmp   eax, [edx]    ; 8B02
   jb    NextPrime     ; 72EB    If the successor is too large, x can no longer be sexy
   ja    GoFurther     ; 77F7    If the successor is too small, take the next one
   mov   eax, [ebx]    ; 8B03    Load eax again (shorter than sub eax, 6)
   mov   ecx, [edx]    ; 8B0A    Load the successor which makes eax a sexy prime
   mov   [edi], eax    ; 8907    Store both in their intended place
   mov   [edi+4], ecx  ; 894F04
   add   edi, 8        ; 83C708
   jmp   NextPrime     ; EBDB

Finished:
   mov   esp, ebp      ; 89EC    Restore stack
   ret                 ; C3

The opcodes (and thus the size of the instruction) are given in the comment. The function can be called from C with, for example

int n = 100;
int resultList[50] = { };
listSexy(n, resultList);

The result list should be initialized with zero, since no final null byte sequence or similar is written into.

Online working example: http://tpcg.io/mEPb1Wy9

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Welcome to the site! I'm not too familiar with Assembly, but I just wanted to make sure that your program follows the standard allowed input/output methods? It seems as though it does, but the snippet of C code is making me unsure. Furthermore, make sure to take a look at TryItOnline to see if any of the languages included can run your program, so that others can verify and help improve your answer \$\endgroup\$ – caird coinheringaahing Jul 5 at 12:08
  • \$\begingroup\$ @cairdcoinheringaahing Thanks for your comment, I added a corresponding link and was able to fix a few typing errors too. From your link of the allowed input/output methods, however, I do not quite understand. My example provides a function, memory space for the return value is passed as a parameter at function call. \$\endgroup\$ – fcdt Jul 5 at 14:53
  • \$\begingroup\$ As I said, I‘m not very familiar with Assembly, so I can’t pass judgement on it’s validity. You can ask in our Chatroom, TNB, and I‘m sure someone more knowledgeable could answer \$\endgroup\$ – caird coinheringaahing Jul 5 at 15:00
2
\$\begingroup\$

05AB1E, 10 bytes

Outputs in reversed order, because the K3 answer also seems to do that.

LεD6-‚}ʒpP

Try it online!

Explanation

L           Length range
 ε          Map:
  D             Duplicate
   6-           Minus 6
     ‚          Pair
      }         Reverse the pair
       ʒ    Filter:
        p       Is_prime
         P      in both items
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Perl: 73 char

sub p{(1x$_[0])!~/^(11+?)\1+$/}map{$x=$_+6;p($_)&&p($x)&&say"$_,$x"}2..<>

usage:

echo 30 | perl -E 'sub p{(1x$_[0])!~/^(11+?)\1+$/}map{$x=$_+6;p($_)&&p($x)&&say"$_,$x"}2..<>'

output:

5,11
7,13
11,17
13,19
17,23
23,29
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Nice sulution with the regex. You can even shorten by 3 bytes: sub p{(1x$_[0])!~/^(11+?)\1+$/}map{p($_)&&p($_+6)&&say"$_,",$_+6}2..<> \$\endgroup\$ – Donat Jul 8 at 20:50
1
\$\begingroup\$

Octave 39

Modified my MATLAB answer to comply with the new (annoying) rules. n is your value.

p=@isprime;i=1:n;[j=i(p(i)&p(i+6));j+6]

Can be tested here

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

C, 102 99 95 chars

Returning an array in C is something you try to avoid. So the function s gets the limit n and a pointer to an array of integers, and fills it with the data. Each pair of sexy primes is placed in two positions in the array. So o[0]=5, o[1]=11, o[2]=7, o[3]=13. The function assumes the array is large enough.

x=7,l;
p(){
    return++l>=x/2||x*(x-6)%l&&p();
}
s(int n,int*o){
    for(;l=++x<=n;)p()?*o++=x-6,*o++=x:0;
}
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

R, 83 characters

f=function(n){library(gmp);p=isprime;for(i in 1:n)if(p(i)&p(i+6)){print(c(i,i+6))}}

Usage:

f(150)
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Ruby 75 74

The new version uses Artem Ice's prime test method:

z=->x{(9..x).map{|i|[i-6,i]}.select{|a|a.all?{|r|(2...r).all?{|m|r%m>0}}}}

Online test: http://ideone.com/yaOdn

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Ruby, 99 88 86 84 82 78

f=->x{(9..x).map{|n|[n-6,n]if[n,n-6].all?{|t|(2...t).all?{|m|t%m>0}}}.compact}

Sample output:

[[5, 11], [7, 13], [11, 17], [13, 19], [17, 23], [23, 29], [31, 37], [37, 43], [41, 47], [47, 53], [53, 59], [61, 67], [67, 73], [73, 79], [83, 89]]

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

J, 25 chars

(#~*/"1@p:~&1)(,+&6)"0 i.

i.n creates a range of [0,n)

(,+&6)"0 takes each integer n in the list and makes a pair n, n+6

(#~ condition) is basically a filter, and the condition in this case, */"1@p:~&1, just checks if a pair is composed solely of primes.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

C# (279 characters)

Basically, it's Saumil's solution with a couple of tweaks. I don't have enough any reputation for commenting though, so...

using System;namespace X{public class P{static int l=100;static void Main(){F(0);}static bool I(int n){bool b=1>0;if(n==1){b=1<0;}for(int i=2;i<n;++i){if(n%i==0){b=1<0;break;}}return b;}static void F(int p){if((p+6)<=l){if(I(p+6)&&I(p)){Console.WriteLine(p+6+","+p);}F(p+1);}}}}

Output:

11,5
13,7
17,11
19,13
23,17
29,23
37,31
43,37
47,41
53,47
59,53
67,61
73,67
79,73
89,83
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Jelly, 13 bytes (non-competing)

‘Ḷµż+6$ÆPẠ$Ðf

Try it online!

Enhanced explanation:

‘Ḷµż+6$ÆPẠ$Ðf Main link. Arguments: z.
‘Ḷ            Range: [0..z].
  µ           Start a new monadic chain.
    +6        Add 6 to each element of x. (implicit x=⁸).
      $       Last two links (+6) as a monad.
   ż          Interleave x and y.
       ÆP     Do a primality check every element of every element of z.
         Ạ    Do an "all" check on every element of z.
          $   Last two links as a monad.
           Ðf Keep the elements of z that return a truthy value given this monad.
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I know you posted this 3.5 years ago, but this fails for input n=47, since it includes [47,53]. \$\endgroup\$ – Kevin Cruijssen Jul 7 at 13:17
1
\$\begingroup\$

JavaScript (140 113 Characters)

t=(i,n)=>{for(n=i;n%--i;);return 1==i};s=(n,p)=>{for(p=[],i=2;i<n-6;i++)if(t(i)&&t(i+6))p.push([i,i+6]);return p}

Try s(30).

Updated to use the shorter primality test from here, and to use the new arrow notation.

Old version (140 characters):

function t(n,i){for(i=2;i<n;i++)if(!(n%i))return!1;return!0}function s(n,p){for(p=[],i=2;i<n-6;i++)if(t(i)&&t(i+6))p.push([i,i+6]);return p}

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Brachylog, 12 10 bytes

-2 thanks to @Fatalize

≥Iṗ-₆ṗ;I≜ᶠ

Try it online!

How it works

≥Iṗ-₆ṗ;I≜ᶠ
         ᶠ find all …
        ≜   force number-finding of constraints that fulfill …
             (strictly not necessary, but otherwise constraints will be returned)
≥             any number less than the input
 I            assign it to I
  ṗ           must be prime
   -₆ṗ        minus 6 must also be prime
      ;I      append I again (so we have [I-6,I])
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ You can use findall directly on the labelling predicate, to save 2 bytes: ≥Iṗ-₆ṗ;I≜ᶠ \$\endgroup\$ – Fatalize Jul 28 at 7:31
0
\$\begingroup\$

C# 295

using System;using System.Linq;namespace K{class C{public static void Main(string[]a){Func<int,bool>p=i=>Enumerable.Range(2,i-3).All(x=>i%x>0);Console.WriteLine("["+String.Join(",",Enumerable.Range(0,int.Parse(a[0])).Where(i=>i>9&&p(i)&&p(i-6)).Select(i=>"["+(i-6)+","+i+"]").ToArray())+"]");}}}

Online test: http://ideone.com/4PwTW (in this test I've replaced int.Parse(a[0]) with the actual int value, as I cannot supply command line arguments to programs running on ideone.com)

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Mathematica - 69 48 chars

Assuming m has been assigned a value

p=PrimeQ;Cases[Range@m,n_/;p@n&&p[n+6]:>{n,n+6}]
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Scala (82)

def p(n:Int)=9 to n map(x=>List(x-6,x))filter(_.forall(l=>2 to l-1 forall(l%_>0)))

Sample output: Vector(List(5, 11), List(7, 13), List(11, 17), List(13, 19), List(17, 23), List(23, 29), List(31, 37), List(37, 43), List(41, 47), List(47, 53), List(53, 59), List(61, 67), List(67, 73), List(73, 79), List(83, 89))

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Factor 140

This language is fun and interesting. My first script.

:: i ( n -- ? )
n 1 - 2 [a,b] [ n swap mod 0 > ] all? ;
:: s ( n -- r r )
11 n [a,b] [ i ] filter [ 6 - ] map [ i ] filter dup [ 6 + ] map ;

Usage:

( scratchpad ) 100 f

--- Data stack:
V{ 5 7 11 13 17 23 31 37 41 47 53 61 67 73 83 }
V{ 11 13 17 19 23 29 37 43 47 53 59 67 73 79 89 }
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

PARI/GP (62 characters)

f(a)=w=[];forprime(x=0,a,isprime(x+6)&w=concat(w,[[x,x+6]]));w

Example:

 (00:01) gp > f(a)=w=[];forprime(x=0,a,isprime(x+6)&w=concat(w,[[x,x+6]]));w
 (00:01) gp > f(30)
 %1 = [[5, 11], [7, 13], [11, 17], [13, 19], [17, 23], [23, 29]]
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

C# ( 321 303 290 characters )

using System;namespace X{public class P{ static int l=100;static void Main(){F(0);}static bool I(int n){bool b=true;if(n==1){b=false;}for(int i=2;i<n;++i){if(n%i==0){b=false;break;}}return b;}static void F(int p){if((p+6)<=l){int m=p+6;if(I(m)&&I(p)){Console.WriteLine(m+","+p);}F(p+1);}}}}

Output:
11,5
13,7
17,11
19,13
23,17
29,23
37,31
43,37
47,41
53,47
59,53
67,61
73,67
79,73
89,83

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Welcome to CodeGolf! You can save some chars if you give the class and methods one-letter names (ex: class P instead of class Program). \$\endgroup\$ – Cristian Lupascu Jul 20 '12 at 12:16
0
\$\begingroup\$

Haskell (65 chars)

p n=[(x,x+6)|x<-[3..n-6],all(\k->all((>0).mod k)[2..k-1])[x,x+6]]

The output:

Prelude> p 100
[(5,11),(7,13),(11,17),(13,19),(17,23),(23,29),(31,37),(37,43),(41,47),(47,53),(
53,59),(61,67),(67,73),(73,79),(83,89)]

About the MATLAB answer here:

(I spent all my rep on a bounty so can't comment just yet). Google says: " the Matlab's isprime function ... is based on the probabilistic Miller-Rabin". So it seems that the MATLAB entry should be disqualified.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

R 85 81 characters

f=function(n){m=2:n;a=m[rowSums(!outer(m,m,`%%`))<2];cbind(b<-a[(a+6)%in%a],b+6)}

Example run:

f(50)
      [,1] [,2]
 [1,]    5   11
 [2,]    7   13
 [3,]   11   17
 [4,]   13   19
 [5,]   17   23
 [6,]   23   29
 [7,]   31   37
 [8,]   37   43
 [9,]   41   47
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

PHP, 106 bytes

function p($n){for($i=$n;--$i&&$n%$i;);return$i-1;}for(;++$i<$argv[1]-5;)p($i)|p($k=$i+6)?:print"$i,$k\n";

program prints pairs as n,n+6 delimited by linebreaks. Run with -r.

I modified my is_prime function (& saved a byte) so that it returns 0 for primes to golf on the Elvis.

| improve this answer | |
\$\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.