18
\$\begingroup\$

Finding primes is a programming rite of passage and very frequently the first serious program someone creates (usually with trial division).

But primes alone are already worn out. A next far more interesting thing is to get the prime gaps: the so-far-longest gaps between consecutive primes. These are quite rare and "precious". A first few pairs and their differences are:

2 3 1
3 5 2
7 11 4
23 29 6
89 97 8
113 127 14
...

My father used to calculate these by hand for fun up to 10k. Let's see how short a code you can get.

Write a program which goes through primes and produces a line of output every time the difference between two consecutive primes is bigger than that of any two previous consecutive primes.

Your output can either be the two primes followed by their gap, or just the gap. If you choose the later add 10 to your overall score.

For instance, between 3 and 5, there is a gap 2 units wide. The gap between 5 and 7 is also 2, but that's old news, we don't care any more. Only when you see a new biggest gap, you report it. This reflects how the primes are getting less and less frequent, as the gaps become wider and wider.

Rules:

  • no builtin functions for prime testing, prime generation or prime gaps
  • no retrieving http://oeis.org/A002386 or similar (I can smell you cheaters from far away :) )
  • no precomputed arrays
  • keep printing until your internal integer type fails on you

Answers are scored in characters, plus the potential 10 penalty. With lower scores being the goal.

You can also show off versions with builtin functions if they are interesting. Be creative.


EDIT: Most of the answers are brilliant and deserve more recognition. However, so far, a GolfScript entry with 48 characters is the shortest.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ In your example 3 is the end of a pair, and the start of the next pair, while this is not the case for other numbers. What do you want? \$\endgroup\$
    – mmumboss
    Mar 12, 2014 at 12:20
  • \$\begingroup\$ Nevermind, I got it now. \$\endgroup\$
    – mmumboss
    Mar 12, 2014 at 12:45
  • \$\begingroup\$ You may want to rewrite your rule as "no builtin functions for prime testing, prime calculation or prime gaps". Otherwise an obvious solution would use a function that returns the n th prime, then increment n, run the function again and find the difference. \$\endgroup\$
    – user12205
    Mar 12, 2014 at 13:25
  • 2
    \$\begingroup\$ Aww. i love OEIS \$\endgroup\$
    – TheDoctor
    Mar 12, 2014 at 14:50
  • \$\begingroup\$ I have the same doubt as @mmumboss. Could you please xplain? \$\endgroup\$
    – Clyde Lobo
    Mar 12, 2014 at 15:04

28 Answers 28

11
\$\begingroup\$

Python, 121 110 109 108 104 103 characters

p,n,m=[2],3,0
while 1:
 if all(n%x for x in p):
  c=n-p[0]
  if m<c:m=c;print(p[0],n,c)
  p=[n]+p
 n+=1

First time I tried to answer here, I hope I did it right... not sure I even counted the characters right.

Hmmm, I could save another character on the print by downgrading to Python 2.x...

\$\endgroup\$
7
  • \$\begingroup\$ 121 chars, make the title a heading with # , you seriously don't count the chars by hand do you? javascriptkit.com/script/script2/charcount.shtml \$\endgroup\$
    – user80551
    Mar 12, 2014 at 12:43
  • \$\begingroup\$ No, I didn't count by hand :) But I've seen other Python answers to some questions flattened to one line in a way that reduced whitespace, and frankly I'm not sure whether a newline is counted as 1 or 2 characters... \$\endgroup\$
    – Tal
    Mar 12, 2014 at 12:49
  • 1
    \$\begingroup\$ We count newlines as 1 character unless the question's rules explicitly state otherwise. Welcome to PPCG! \$\endgroup\$ Mar 12, 2014 at 12:50
  • 3
    \$\begingroup\$ Welcome! Nice answer, and it also has some room for improvement. For example, if all(n%x>0for x in p): is a bit shorter. You can also save some characters by moving statements onto the same line (e.g. a=1;b=2;f()). \$\endgroup\$
    – grc
    Mar 12, 2014 at 12:57
  • 1
    \$\begingroup\$ Latest change broke the code by not pushing [n] to the front like stated. \$\endgroup\$
    – orion
    Mar 12, 2014 at 19:04
4
\$\begingroup\$

JavaScript, 90 85 78 74 chars

Short Code (Google Closure Compiler - Advanced Optimizations; some manual edits; more edits by @MT0)

for(a=b=2,c=0;b++;)for(d=b;b%--d;)d<3&&(c<b-a&&console.log(a,b,c=b-a),a=b)

Long Code

var lastPrime = 2,
    curNumber = lastPrime,
    maxDistance = 0,
    i;

// check all numbers
while( curNumber++ ) {

  // check for primes
  i = curNumber;
  while( curNumber % --i != 0 ) {}

  // if prime, then i should be equal to one here
  if( i == 1 ) {

    // calc distance
    i=curNumber-lastPrime;

    // new hit
    if( maxDistance < i ) {
      maxDistance = i;
      console.log( lastPrime, curNumber, maxDistance );
    }

    // remember prime
    lastPrime = curNumber;
  }
}

Output

2 3 1
3 5 2
7 11 4
23 29 6
89 97 8
113 127 14
523 541 18
887 907 20
1129 1151 22
1327 1361 34
9551 9587 36
15683 15727 44
19609 19661 52
31397 31469 72
...

Pretty inefficient test for primes, but that way it uses less characters.

First post here, so please excuse any mistakes.

\$\endgroup\$
3
  • \$\begingroup\$ 78 Characters - for(a=b=2,c=0;b++;){for(d=b;b%--d;);1==d&&(c<b-a&&console.log(a,b,c=b-a),a=b)} \$\endgroup\$
    – MT0
    Mar 18, 2014 at 21:39
  • \$\begingroup\$ @MT0 Thanks. Did not spot those. Edited. \$\endgroup\$
    – Sirko
    Mar 19, 2014 at 9:54
  • \$\begingroup\$ Even more inefficient but 74 characters - for(a=b=2,c=0;b++;)for(d=b;b%--d;)d<3&&(c<b-a&&console.log(a,b,c=b-a),a=b) \$\endgroup\$
    – MT0
    Mar 19, 2014 at 22:09
3
\$\begingroup\$

GolfScript 66 59 57 49 48

[2.0{:d{;\;.{).{(1$1$%}do(}do.2$-.d>!}do].p~.}do

Although I'm having trouble running it here http://golfscript.apphb.com/ (maybe that site doesn't like the infinite loop?) but it works fine when I run it on my computer with golfscript.rb. I'm pretty new to GolfScript so this can probably be golfed down even further. UPDATE: I don't think this can be golfed down much more without changing the algorithm somehow.

First few lines printed (If you do not like the "" being printed you can add ; at the beginning of the script, but that bumps it up to 49 chars) :

[2 3 1]
["" 3 5 2]
["" 7 11 4]
["" 23 29 6]
["" 89 97 8]
["" 113 127 14]
["" 523 541 18]
["" 887 907 20]
["" 1129 1151 22]
...

General human-readable idea of how this works (a few things slightly different since I'm not using a stack in this version) :

cur_prime = 2
next_prime = 2
gap = 0        

do {
    do {
        cur_prime = next_prime
        do {
            next_prime = next_prime + 1
            possible_factor = next_prime
            do {
                possible_factor = possible_factor - 1
            } while (next_prime % possible_factor > 0)
        } while (possible_factor != 1)
    } while (next_prime - cur_prime <= gap)

    gap = next_prime - cur_prime
    print [cur_prime next_prime gap]
} while (true)
\$\endgroup\$
3
\$\begingroup\$

Mathematica, 114 108

Allows infinite output, although after a certain point in the sequence the fan spins up and you begin to suspect that your CPU is playing Freecell while doing its best to look busy.

p@x_:=NestWhile[#+1&,x+1,Divisors@#≠{1,#}&];m=0;q=1;While[1<2,If[p@q-q>m,Print@{q,p@q,p@q-q};m=p@q-q];q=p@q]

Output sample (These are the ones it picks up in the first ~30s):

{1,2,1}
{3,5,2}
{7,11,4}
{23,29,6}
{89,97,8}
{113,127,14}
{523,541,18}
{887,907,20}
{1129,1151,22}
{1327,1361,34}
{9551,9587,36}
{15683,15727,44}
{19609,19661,52}
{31397,31469,72}
{155921,156007,86}
{360653,360749,96}
{370261,370373,112}
{492113,492227,114}
{1349533,1349651,118}
{1357201,1357333,132}
{2010733,2010881,148}

Ungolfed code:

p@x_ := NestWhile[
   # + 1 &,
   x + 1,
   Divisors@# ≠ {1, #} &];
m = 0;
q = 1;
While[
 1 < 2,
 If[
  p@q - q > m,
  Print@{q, p@q, p@q - q}; m = p@q - q];
 q = p@q]
\$\endgroup\$
4
  • \$\begingroup\$ Does it recognize ? \$\endgroup\$
    – Riking
    Mar 13, 2014 at 1:39
  • \$\begingroup\$ Yes, it just doesn't export that way but it will parse it just fine when you paste code into the notebook. I've already scored it accordingly but I'll revise to simplify. \$\endgroup\$ Mar 13, 2014 at 1:44
  • \$\begingroup\$ how many characters if you do use mathematica's built-in Prime functions? \$\endgroup\$ Mar 20, 2014 at 16:32
  • \$\begingroup\$ 76. Since the entire p@x_ definition is just a reimplementation of NextPrime, it can be replaced by p=NextPrime; \$\endgroup\$ Mar 20, 2014 at 16:47
3
\$\begingroup\$

Haskell - 122 116 114 112 110

q=[n|n<-[3..],all((>0).rem n)[2..n-1]]
d m((p,q):b)|q-p>m=print(p,q,q-p)>>d(q-p)b|q>p=d m b
main=d 0$zip(2:q)q

(Inefficient) prime list expression stolen from Will Ness.

-edit- I never knew x|y=z|w=q would be valid.

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

MATLAB 104 89

Just implemented the basic method by checking every possible division.

a=2;g=0;for n=3:inf;b=n*(sum(mod(n,1:n)<1)<3);h=b-a;if(h>g)g=h;[a,b,h]
end;a=max(a,b);end

Output:

  2     3     1
  3     5     2
  7    11     4
 23    29     6
 89    97     8
113   127    14
523   541    18
887   907    20
\$\endgroup\$
2
  • \$\begingroup\$ I'm on octave and this inf thing doesn't work (and print is deferred until the loop ends). Does matlab have lazy range evaluation? \$\endgroup\$
    – orion
    Mar 12, 2014 at 22:25
  • \$\begingroup\$ Matlab prints realtime, each iteration of the loop. When I start my program I get a warning that the maximum index is 2147483647, and then it starts. Alternatively I could replace inf with intmax, but that is three chars more. \$\endgroup\$
    – mmumboss
    Mar 13, 2014 at 6:48
2
\$\begingroup\$

76 chars, dogelang

Converted from my Python version:

g=0
i=l=2
while i+=1=>all$map(i%)(2..i)=>(i-l>g=>(g=i-l),print(l,i,g)),(l=i)

Output:

(2, 3, 1)
(3, 5, 2)
(7, 11, 4)
(23, 29, 6)
(89, 97, 8)
(113, 127, 14)
(523, 541, 18)
(887, 907, 20)
(1129, 1151, 22)
...
\$\endgroup\$
1
  • \$\begingroup\$ Should be selected as the winner! \$\endgroup\$ May 24, 2014 at 18:25
2
\$\begingroup\$

Golfscript, 59 51 50 chars

Man each character is extremely difficult to lose:

0[2.{).,2>{\.@%!},{.2$-.4$>{].p~\[}{;\;}if..}or}do

Output:

[2 3 1]
[3 5 2]
[7 11 4]
[23 29 6]
[89 97 8]
[113 127 14]
...

Explanation:

The stack is set up so each iteration starts with the stack like this, the top being to the right. The [ indicates the current array marker, meaning when the interpreter encounters a ], everything on the stack from the mark to the top is put into an array.

g [ last | cur

g is the maximum gap so far. From the top down:

 command         | explanation
-----------------+----------------------------------------
 0[2.            | initialize vars g=0, last=2, cur=2
 {...}do         | loop forever...

Inside the loop:

 )               | cur += 1
 .,2>{\.@%!},    | put all divisors of cur into a list
 {...}or         | if the list is empty, cur is prime, so
                 | the block is executed. otherwise,
                 | 'do' consumes the stack, sees it is truthy,
                 | and loops again

How does it put all divisors into a list? Let's do it step by step

 Command         | explanation                                  | stack
-----------------+----------------------------------------------+----------------
                 | initial stack                                | n
 .,              | make list of 0..n-1                          | n [0,1,...,n-1]
 2>              | take elements at index 2 and greater         | n [2,3,...,n-1]
 {...},          | take list off stack, then iterate through    |
                 | the list. on each iteration, put the current |
                 | element on the stack, execute the block, and |
                 | pop the top of the stack. if the top is      |
                 | true then keep the element, else drop it.    |
                 | when done, push list of all true elements    |
                 | So, for each element...                      | n x
   \.            |   Swap & dup                                 | x n n 
   @             |   Bring x around                             | n n x
   %             |   Modulo                                     | n (n%x)
   !             |   Boolean not. 0->1, else->0. Thus this is 1 |
                 |   if x divides n.                            | n (x divides n)
                 | So only the divisors of n are kept           | n [divisors of n]

What does it do if the divisors are empty?

 Command         | explanation                                  | stack
-----------------+----------------------------------------------+----------------
                 | initial stack                                | g [ last | cur
  .              | dup                                          | g [ l | c | c
  2$             | copy 3rd down                                | g [ l | c | c | l
  -              | sub. This is the current gap, cur-last       | g [ l | c | c-l
  .              | dup                                          | g [ l | c | c-l | c-l
  4$             | copy 4th down                                | g [ l | c | c-l | c-l | g
  >              | is cur gap > max gap so far?                 | g [ l | c | c-l | c-l>g
  {#1}{#2}if..   | #1 if c-l > g, #2 otherwise, and do ".." in  | ... | g [ c | c | c
                 | either situation                             | 

Two paths: yes and no. If yes (note that if consumes the top value on the stack):

 Command         | explanation                                  | stack
-----------------+----------------------------------------------+----------------
                 | initial stack. note that now the old `g` is  | XX [ l | c | g
                 | garbage and `c-l` is the new `g`.            |
 ]               | close the array                              | XX [l, c, g]
 .p              | duplicate it and print it, consuming the dup | XX [l, c, g]
 ~               | pump array back onto the stack. Note now the | XX | l | c | j
                 | array marker [ is gone.                      | 
 \               | swap.                                        | XX | l | g | c                         
 [               | mark the array                               | XX | l | g | c [
 .               | this is the part after the if. dups the top, | XX | l | g [ c | c
                 | but it does this in two steps, first popping | 
                 | c then putting two copies on top, so the     | 
                 | array marker moves                           | 
 .               | dup again                                    | XX | l | g [ c | c | c

If no:

 Command         | explanation                                  | stack
-----------------+----------------------------------------------+----------------
                 | initial stack. In this case g is still the   | g [ l | c | c-l
                 | max gap so far                               | 
 ;\;             | dump top of stack, swap, and dump again      | g [ c
 ..              | the part after the if. dup twice             | g [ c | c | c

Note in either case, our stack is now in the form ... | g [ c | c | c.

Now the do pops the top value off the stack - always c - and loops if it is positive. Since c always increasing, this is always true, so we loop forever.

Once popped, the top of the stack is g [ c | c, meaning last has been updated to c, the array mark is in the same place, and g is still where we expect it.

These are the convoluted operations of GolfScript. I hope you enjoyed following along!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Excellent elucidation! \$\endgroup\$ Mar 12, 2014 at 22:30
1
\$\begingroup\$

Ruby, 110

Only for Ruby 2.0 due to the lazymethod:

(2..1.0/0).lazy.select{|n|!(2...n).any?{|m|n%m==0}}.reduce([2,0]){|(l,t),c|d=c-l;p [l,c,d]if d>t;[c,d>t ?d:t]}

Output:

[2, 3, 1]
[3, 5, 2]
[7, 11, 4]
[23, 29, 6]
[89, 97, 8]
[113, 127, 14]
[523, 541, 18]
[887, 907, 20]
[1129, 1151, 22]
[1327, 1361, 34]
[9551, 9587, 36]
[15683, 15727, 44]
[19609, 19661, 52]
[31397, 31469, 72]
[155921, 156007, 86]
[360653, 360749, 96]
[370261, 370373, 112]
[492113, 492227, 114]
...
\$\endgroup\$
1
\$\begingroup\$

Perl, 105 bytes

$p=2;$d=0;L:for($i=2;++$i>2;){!($i%$_)&&next L for 2..$i-1;if($i-$p>$d){$d=$i-$p;print"$p $i $d\n"}$p=$i}

Ungolfed:

$p = 2;
$d = 0;
L: for ($i = 2; ++$i > 2; ){
    !($i % $_) && next L for 2..$i-1;
    if ($i - $p > $d) {
        $d = $i - $p;
        print "$p $i $d\n"
    }
    $p = $i
}  

The algorithm is simple, $p remembers the previous prime number. Then $i goes from 3 up to, when the type $i "fails on me" or become negative because of overflow. $i is tested the crude way by checking all divisors from 2 to $i-1. A line is printed, if the current difference is larger than the previous printed difference $d.

With some more bytes the run-time can be improved:

$p = 2;
$d = 0;
L: for ($i=3; $i > 2; $i += 2){
    for ($j=3; $j <= sqrt($i); $j += 2){
        next L if !($i%$j)
    }
    if ($i - $p > $d) {
        $d = $i - $p;
        print "$p $i $d\n"
    }
    $p = $i
}

The result starts with:

2 3 1
3 5 2
7 11 4
23 29 6
89 97 8
113 127 14
523 541 18
887 907 20
1129 1151 22
1327 1361 34
9551 9587 36
15683 15727 44
19609 19661 52
31397 31469 72
155921 156007 86
360653 360749 96
370261 370373 112
492113 492227 114
1349533 1349651 118
1357201 1357333 132
2010733 2010881 148
4652353 4652507 154
17051707 17051887 180
20831323 20831533 210
47326693 47326913 220
...
\$\endgroup\$
3
  • 1
    \$\begingroup\$ That's not correct, you need to find the series of increasing gaps. See for instance the Ruby or Matlab answer for the expected output. \$\endgroup\$
    – mmumboss
    Mar 12, 2014 at 13:39
  • 1
    \$\begingroup\$ @mmumboss: Oh, I have overlooked this. Fixed now. \$\endgroup\$ Mar 12, 2014 at 14:05
  • \$\begingroup\$ Good for a language where all the variables require minimum 2 characters. \$\endgroup\$
    – orion
    Mar 12, 2014 at 14:13
1
\$\begingroup\$

Python, 93 91 chars

Naive prime checking (check if divisible by anything from 2 to n (less chars than to n/2)):

g=0;i=l=2
while 1:
 i+=1
 if all(i%x for x in range(2,i)):
    if i-l>g:g=i-l;print l,i,g
    l=i

Second level of indent is one tab character.

Output:

2 3 1
5 7 2
7 11 4
23 29 6
89 97 8
113 127 14
523 541 18
...
\$\endgroup\$
1
  • \$\begingroup\$ Nice, I forgot that range up to n only checks up to n-1 \$\endgroup\$
    – Claudiu
    Mar 12, 2014 at 18:56
1
\$\begingroup\$

Bash and some Perl for prime regex (167 157 143 112 bytes)

n=2
c=2
while p=$c
do perl -e\(1x$[++n]')=~/^(11+?)\1+$/&&exit 1'&&c=$n
((c-p>g))&&g=$[c-p]&&echo $p $c $g
done

some output:

$./golfd.sh
2 3 1
3 5 2
7 11 4
23 29 6
89 97 8
113 127 14
523 541 18
887 907 20
1129 1151 22
\$\endgroup\$
8
  • \$\begingroup\$ Using regex's NP backtracking to completely circumvent any loops and control structures is pure perfection. However, test is protesting quite a lot, and it doesn't work for me. You could also use some let n++ and let f=c-p and replace test with [. Or possibly test in (()) where you don't need $ or spaces. \$\endgroup\$
    – orion
    Mar 12, 2014 at 21:11
  • \$\begingroup\$ test -n $d returned true for an empty string. test -n "$d" was fine but longer. However, man page says -n is optional, and it turns out test $d was ok. And therefore [ $d ] too. And g=0 had to be initialized. \$\endgroup\$
    – orion
    Mar 12, 2014 at 21:21
  • \$\begingroup\$ @orion, sorry for some reason it seemed to work once now it broke on my machine too, i reverted it to 167. I'll try to add some of your other suggestions \$\endgroup\$
    – Newbrict
    Mar 12, 2014 at 21:21
  • \$\begingroup\$ Your environment maybe had predefined variables. \$\endgroup\$
    – orion
    Mar 12, 2014 at 21:27
  • \$\begingroup\$ @orion for some reason your edit was rejected, can you re-edit? \$\endgroup\$
    – Newbrict
    Mar 12, 2014 at 21:35
1
\$\begingroup\$

Perl 95 90 bytes

for($n=$c=2;$p=$c;$c-$p>$g&&printf"$p $c %d\n",$g=$c-$p){$c=$n if(1x++$n)!~/^(11+?)\1+$/}

old Non golf version:

$n=$c=2;
while($p=$c){
    $c=$n if (1x++$n)!~/^(11+?)\1+$/;
    if ($c-$p>$g) {$g=$c-$p;print "$p $c $g\n"}
}

This is similar to my other submission, sans bash.

\$\endgroup\$
2
  • \$\begingroup\$ I'm not annoying, I just want to see how far can this go. Here: for($n=$c=2;$p=$c;$c-$p>$g&&printf"$p $c %d\n",$g=$c-$p){$c=$n if(1x++$n)!~/^(11+?)\1+$/} \$\endgroup\$
    – orion
    Mar 13, 2014 at 22:01
  • \$\begingroup\$ @orion that is some serious for loop abuse haha! \$\endgroup\$
    – Newbrict
    Mar 13, 2014 at 22:11
1
\$\begingroup\$

C (100)

My own contribution, no special algorithm, just golf:

i,g,r,p=2;main(){for(;r=p;p-r>g?printf("%d %d %d\n",r,p,g=p-r):0)for(i=0;i-p;)for(i=1,++p;p%++i;);}
\$\endgroup\$
2
  • \$\begingroup\$ " +10 characters if you only print the gaps without the primes." - if you remove printing of r and p you will have fewer characters and score the bonus :) \$\endgroup\$
    – CompuChip
    Mar 14, 2014 at 15:03
  • \$\begingroup\$ Completness is pretty :) \$\endgroup\$
    – orion
    Mar 14, 2014 at 16:21
1
\$\begingroup\$

Haskell, 134C

Golfed:

c n=null[x|x<-[2..n-1],n`mod`x==0]&&n>1
p=filter c[1..]
g l(m:n:o)
 |(n-m)>l=do print(m,n,n-m);g(n-m)(n:o)
 |True=g l(n:o)
main=g 0 p

Ungolfed:

-- c function checks if n is a prime number
c n=null[x|x<-[2..n-1],n`mod`x==0]&&n>1

-- p is an infinite list of primes
p=filter c[1..]

-- g function prints a list of primes and differences.
--   l is the maximum difference seen so far
--   (m:n:o) is the list of unprocessed primes
g l(m:n:o)
 |(n-m)>l=do print(m,n,n-m);g(n-m)(n:o)
 |True=g l(n:o)

-- main starts the ball rolling with a default max-seen value of 0
main=g 0 p
\$\endgroup\$
1
  • \$\begingroup\$ Love that lazy evaluation! \$\endgroup\$ Mar 16, 2014 at 13:13
1
\$\begingroup\$

C: 493 302 272 246

int e(int j){for(int i=2;i<j;i++)if(j%i<1)return 0;return 1;}void f(int a,int b,int c){if(e(a)&e(b))if(c<b-a){printf("%d %d %d\n",a,b,b-a);f(a+1,b+1,b-a);}else f(a+1,b+1,c);if(e(b))f(a+1,b,c);if(e(a))f(a,b+1,c);f(a+1,b+1,c);}int main(){f(2,3,0);}

I used recursion not the usual loop of for or while.

int isPrime(int num){
    for( int i=2; i<num; i++ )
        if(num%i < 0) return 0;
    return 1;
}
void fun(int n1, int n2, int gap){
   if( isPrime(n1) & isPrime(n2) ){
        if( gap < n2-n1 ){
           printf("%d %d %d\n", n1, n2, n2-n1);
           fun(n1+1, n2+1, n2-n1);
        }else{
           fun(n1+1, n2+1, gap);
        }
   }
   if( isPrime(n2) ){
       fun(n1+1, n2, gap);
   }
   if( isPrime(n1) ){
       fun(n1, n2+1, gap);
   }
   fun(n1+1, n2+1, gap);
}

int main(){
   fun(2,3,0);
}

Output:

2 3 1
3 5 2
7 11 4
23 29 6
89 97 8
113 127 14
523 541 18
887 907 20
1129 1151 22
1327 1361 34
9551 9587 36
15683 15727 44
19609 19661 52
\$\endgroup\$
5
  • \$\begingroup\$ This doesn't work. true/false are not defined, but even if we fix that, it's reporting wrong gaps. For instance, there are A LOT of primes between 25219 and 43237. Your recursion is leaking at the top, because you are not testing isPrime(n2), you are letting primes between n1 and n2. And this can't really be fixed, because you can't increase n2 without meeting primes. \$\endgroup\$
    – orion
    Mar 13, 2014 at 7:56
  • \$\begingroup\$ You are right! It is wrong! My thinking was wrong from the beginning. \$\endgroup\$
    – Loukas
    Mar 13, 2014 at 8:10
  • 1
    \$\begingroup\$ Now it is better.. :) \$\endgroup\$
    – Loukas
    Mar 13, 2014 at 8:50
  • \$\begingroup\$ +1 Now that it's fixed I like it - it's nicely unusual (although not efficient). You could golf it down a lot. Skip return in main. Skip the last else. Replace && -> & and num%i==0 with num%i<1. And by the ancient c standards (there will be warnings), you don't need to specify return values for void and int functions (their arguments also default to int). \$\endgroup\$
    – orion
    Mar 13, 2014 at 15:27
  • \$\begingroup\$ I was playing a bit and got it down to 151 characters, with a single unconditional recursive call, only one type specifier (int) and much reduced prime testing function: e(j,i){while(j%++i);return i==j;}f(a,b,c){int A=e(a,1),B=e(b,1);if(A&B&&c<b-a)printf("%d %d %d\n",a,b,c=b-a);f(a+(B|!A),b+(A|!B),c);}main(){f(2,3,0);} \$\endgroup\$
    – orion
    Mar 14, 2014 at 10:38
1
\$\begingroup\$

Oracle SQL, 216 202 196 172 + 10 = 182

Just noticed this in the question:

Lowest character count wins. +10 characters if you only print the gaps without the primes.

As this is SQL and the keywords are so long it's actually better to take the penalty, giving the following. It's the same idea as the original.

with c as(select level+1n from dual connect by level<1e124)select lead(n)over(order by n) from(select*from c a where not exists(select*from c where n<a.n and mod(a.n,n)=0))

which prettifies to:

with c as ( 
 select level + 1 n 
   from dual 
connect by level < 1e124
        )
select lead(n) over ( order by n ) 
  from ( select *
           from c a 
          where not exists( select * 
                              from c 
                             where n < a.n 
                               and mod(a.n, n) = 0
                                   )
                )

Old answer (196)

with c as(select level+1n from dual connect by level<1e124)select n,p,p-n from(select n,lead(n)over(order by n)p from(select*from c a where not exists(select*from c where n<a.n and mod(a.n,n)=0)))

and in a readable format:

with c as ( 
 select level + 1 n 
   from dual 
connect by level < 1e124
        )
select n, p, p-n 
  from ( select n, lead(n) over ( order by n ) p 
           from ( select * 
                    from c a 
                   where not exists (
                                select * 
                                  from c
                                 where n < a.n 
                                   and mod(a.n, n) = 0
                                       )
                         )
                )

This creates a number generator in c, the innermost sub-select creates the primes numbers using a Sieve of Eratosthenes, the outer works out the previous prime and finally the last select subtract one from the other.

This won't return anything because it's performing 1 x 10 124 recursive queries... So, if you want it to work lower this number to something sensible.

\$\endgroup\$
3
  • \$\begingroup\$ When it comes to a challenge like this one, I think of SQL as not so much Turing-complete, but Turing-obstinate. \$\endgroup\$ Mar 14, 2014 at 13:23
  • \$\begingroup\$ But it is Turning-complete @Jonathan, though getting it there is sometimes "interesting" :-)? \$\endgroup\$
    – Ben
    Mar 14, 2014 at 13:34
  • \$\begingroup\$ Knowing it is Turing-complete, I was aiming to jest. Missed the mark, apparently. :) Anyway, there are several T-SQL answers in my profile...bring your Oracle and let's have a duel! \$\endgroup\$ Mar 14, 2014 at 14:10
0
\$\begingroup\$

D - 153 + 10 = 163

I'm willingly taking the +10 penalty here, because the char count is still lower than it would have been if I had printed the primes as well.

Golfed:

import std.stdio;bool p(int l){int n;foreach(i;1..l+1)n+=l%i==0?1:0;return n==2;}void main(){int g;foreach(l;0..int.max)if(l.p){if(g>0)(l-g).write;g=l;}}

Readable version:

import std.stdio;

bool prime( int number )
{
    int divisors;

    foreach( i; 1 .. number + 1 )
        divisors += number % i == 0 ? 1 : 0;

    return divisors == 2;
}

void main()
{
    int lastPrime;

    foreach( number; 0 .. int.max )
        if( number.prime )
        {
            if( lastPrime > 0 )
                ( number - lastPrime ).write;

            lastPrime = number;
        }
}
\$\endgroup\$
0
\$\begingroup\$

JAVASCRIPT 174 char

var p=[2],l=2,g=0;
for(var n=3;n>0;n+=2){
  var o=0;
  for(var t=0;t<p.length;++t){
    if(n/p[t] == parseInt(n/p[t])){
      o=1;
    }
  }
  if(o==0){
    p.push(n);
    if(n-l>g){
      g=n-l;
      console.log(l,n,g);
    }
    l=n;
  }
}

short version:

var p=[2],l=2,g=0;for(var n=3;n>0;n+=2){var o=0;for(var t=0;t<p.length;++t){if(n/p[t] == parseInt(n/p[t])){o=1;}}if(o==0){p.push(n);if(n-l>g){g=n-l;console.log(l,n,g);}l=n;}}
\$\endgroup\$
0
\$\begingroup\$

Javascript 138

for(var a=2,b=0,c=0;a++;){var d;a:{for(var e=a,f=2;f<e;f++)if(0==e%f){d=!1;break a}d=!0}d&&(0!=b&&a-b>c&&(c=a-b,console.log(b,a,c)),b=a)}

Copy this code to your browser console. It will for like forever as the max number is something around 1.79*10^308.

Ungolfed:

var number = 2;
var lastPrime = 0;
var gap = 0;

while(number++)
{
    if (isPrime(number)) {
        if (lastPrime != 0) {            
            if (number - lastPrime > gap)
            {
                gap = number - lastPrime;
                console.log(lastPrime, number, gap);
            }
        }

        lastPrime = number;
    }
}

function isPrime(n){
    for (var i = 2; i < n; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}
\$\endgroup\$
0
\$\begingroup\$

C# 162 161 chars

151 chars + 10 penalty chars = 161 chars

Short version:

using System;class P{static void Main(){int p=2,g=0;for(int i=3;;i++){for(int j=2;j<i;j++)if(i%j==0)goto e;if(i-p>g)Console.WriteLine(g=i-p);p=i;e:;}}}

Long version:

using System;

class PrimeGaps
{
    private static void Main()
    {
        int lastPrime = 2;
        int largestGap = 0;

        for (int i = 3; true; i++)
        {
            // Prime test
            for (int j = 2; j < i; j++)
                if (i%j == 0)
                    goto nextI; // Skip to next iteration of i

            // Largest gap check
            if (i - lastPrime > largestGap)
            {
                largestGap = i - lastPrime;
                Console.WriteLine(largestGap);
            }

            // Remember last prime
            lastPrime = i;

            nextI:
                ; // Do nothing
        }
    }
}

It was actually better to take 10 chars penalty, since it's shorter writing g (11 chars with penalty) than p+" "+i+" "+g (13 chars without penalty).

\$\endgroup\$
0
\$\begingroup\$

Ruby 90 86 84 83 chars

r,i,g=2,2,0;while i+=1 do(2...i).all?{|j|i%j>0}&&((i-r<=g||p([r,i,g=i-r]))&&r=i)end

Some boolean short circuits, abuse of expression evaluation, etc.

\$\endgroup\$
0
\$\begingroup\$

C 248

Code compares consecutive prime numbers a, b and then checks if gaps are larger than g then finds next pair of primes.

#include <cstdio>
void f(int* a, int* b){*a =*b;int t=1;while (*b += 2){t=1;for(int i=3;i<*b;i+=2){if(*b%i==0){t=0; break;}}if(t)break;}}
int main(){int a=2,b=3,g=0;do{(b-a>g)?printf("%d %d %d\n",a,b,(g=b-a)): f(&a,&b);} while(b>=0);return 0;}
\$\endgroup\$
1
  • \$\begingroup\$ This is C++, is it not? \$\endgroup\$
    – Adalynn
    Aug 5, 2017 at 15:33
0
\$\begingroup\$

Haskell, 154 144 137 123

The primes p are generated using the sieve of erasthotenes #, and then filtered and printed using %.

p=2:3#1
n#m|all((>0).mod n)$take m p=n:(n+1)#(m+1)|1<2=(n+1)#m
(l:u@(o:_))%k|o-l>k=print(l,o,o-l)>>u%(o-l)|1<2=u%k
main=p%0

The output looks like

(2,3,1)
(3,5,2)
(7,11,4)
(23,29,6)
(89,97,8)

which I hope is okay.

\$\endgroup\$
0
\$\begingroup\$

Game Maker Language, 85

Assuming all uninitialized variables as 0 (this is the default with some versions of Game Maker).

a=2b=2for(d=2;b++;1)for(c<b-a;b mod --d;1)d<3&&(c=b-a&&show_message_ext("",a,b,c)a=b)
\$\endgroup\$
0
\$\begingroup\$

Game Maker Language, 74 + 55 = 129

Assuming all uninitialized variables as 0 (this is the default with some versions of Game Maker).

n=2while(n++){if p(n){if l{if n-l>g{g=n-l;show_message_ext("",l,n,g)}}l=n}

Script p is below:

r=1a=argument0for(i=2i<a;i++){if a mod i=0r=0}return r}
\$\endgroup\$
0
\$\begingroup\$

Perl, 87 bytes (using a module)

use Math::Prime::Util":all";$l=2;forprimes{if($_-$l>$m){say"$l $_ ",$m=$_-$l}$l=$_}1e14

I wrote the module, but we'd have to add an extra 565,000 characters to the tally. Mostly posting for fun, but also to give a performance alternative since I don't see any so far using builtins. 4.6s for gaps to 1e9, 36s for gaps to 1e10, 6.5min for 1e11.

Pari/GP 2.8 can be done basically the same way, albeit over 2x slower:

l=2;m=0;forprime(p=2,1e14,if(p-l>m,print(l," ",p," ",m=p-l));l=p)
\$\endgroup\$
-1
\$\begingroup\$

Perl 153

Short code:

$i=$a=2;while($a=$i++){if(p($i)){if($m<$m2=$i-$a){$m=$m2;print"$a $i $m$/"}}}sub p{$d=2;$s=sqrt$_[0];while(){return 0if!($_[0]%$d);return 1if$d>$s;$d++}}

easy to Read:

$i=$a=2;
while($a=$i++){
  if(p($i)){
    if($m<$m2=$i-$a){
      $m=$m2;
      print"$a $i $m$/"
    }
  }
}
sub p {
  $d=2;
  $s=sqrt$_[0];
  while(){
    return 0if!($_[0]%$d);
    return 1if$d>$s;
    $d++;
  }
}
\$\endgroup\$
1
  • \$\begingroup\$ This outputs all gaps, not just the biggest so far. \$\endgroup\$
    – orion
    Mar 12, 2014 at 13:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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