14
\$\begingroup\$

In number theory, a strong prime is a prime number that is greater than the arithmetic mean of the nearest prime above and below (in other words, it's closer to the following than to the preceding prime).

Given an input integer, n, where n >= 0, your task is to generate the first n strong primes. For example, the sixth, seventh, and eighth primes are 13, 17, and 19, respectively:

(13 + 19) / 2 < 17

Therefore, 17 is a strong prime.

Input

  • an integer

Output

  • if n is 0
    • program: output nothing
    • function: return an empty array
  • if n is greater than 0
    • program: output the first n strong primes, each on its own line
    • function: return an array containing the first n strong primes

Test cases

0
[]

4
[11, 17, 29, 37]

7
[11, 17, 29, 37, 41, 59, 67]

47
[11, 17, 29, 37, 41, 59, 67, 71, 79, 97, 101, 107, 127, 137, 149, 163, 179, 191, 197, 223, 227, 239, 251, 269, 277, 281, 307, 311, 331, 347, 367, 379, 397, 419, 431, 439, 457, 461, 479, 487, 499, 521, 541, 557, 569, 587, 599]

See also: Strong primes on OEIS

\$\endgroup\$
  • \$\begingroup\$ output n strong primes - Any n strong primes or the first n strong primes? A few test cases/examples of corresponding inputs and outputs would a nice addition to the challenge. \$\endgroup\$ – Mr. Xcoder Sep 3 '17 at 7:52
  • 1
    \$\begingroup\$ @Mr.Xcoder: I've updated the spec; added a link to OEIS, as well. \$\endgroup\$ – Zach Gates Sep 3 '17 at 7:55
  • \$\begingroup\$ Does it really have to be a newline as delimiter? \$\endgroup\$ – Titus Sep 3 '17 at 11:49
  • \$\begingroup\$ @Titus: Yes it does. \$\endgroup\$ – Zach Gates Sep 3 '17 at 12:02
  • \$\begingroup\$ is it an "and" or an "or" in the spec? "output and return" or "output, or return"?? \$\endgroup\$ – Will Ness Sep 3 '17 at 22:14

14 Answers 14

13
\$\begingroup\$

Husk, 12 11 bytes

↑§foẊ<Ẋ-tİp

Try it online!

-1 byte thanks to H.PWiz.

Explanation

↑§foẊ<Ẋ-tİp  Input is n.
         İp  The infinite list of primes.
      Ẋ-     Take pairwise differences,
   oẊ<       then pairwise comparisons.
        t    Frop the first element from İp
 §f          and filter the rest using the result of oẊ<Ẋ-.
↑            Take first n elements of this list.
\$\endgroup\$
  • \$\begingroup\$ 11 bytes, but a bit more boring \$\endgroup\$ – H.PWiz Sep 3 '17 at 12:00
6
\$\begingroup\$

Jelly, 14 bytes

Æp+ÆnH<ȧÆP
3Ç#

Try it online!

Explanation

Æp+ÆnH<ȧÆP  Helper link. Input: k
Æp          Prime less than k
  +         Plus
   Æn       Prime greater than k
     H      Halve
      <     Less than k?
       ȧ    Logical AND
        ÆP  Is k prime?

3Ç#  Main link. Input: n
  #  Find n matches
3Ç     Call the helper link on 3, 4, 5, ...
\$\endgroup\$
  • \$\begingroup\$ I discovered an alternative and thought it might be worth mentioning it: Æp+Æn<ḤȧÆP \$\endgroup\$ – Mr. Xcoder Sep 3 '17 at 8:14
6
\$\begingroup\$

Java 182 167 153 bytes

Second version

Thank's to Roman Gräf for saving 29 bytes!

n->{int s[]=new int[n],i=1,p=i,q=i;while(n>0)if(java.math.BigInteger.valueOf(++i).isProbablePrime(n.MAX_VALUE)){if(p>(i+q)/2)s[--n]=p;q=p;p=i;}return s;}

ungolfed

int[] strongPrimes(Integer n) {
        int[] strongPrimes = new int[n];
        int i=1;
        int p1=i; //last prime
        int p2=i; //2 primes ago
        while(n>0) if(java.math.BigInteger.valueOf(++i).isProbablePrime(n.MAX_VALUE)) { //increment i and if prime
            //System.out.println("p1:"+p1+" i:"+i+" p2:"+p2);
            if(p1>(i+p2)/2) strongPrimes[--n]=p1; //if the previous one was strong
            p2=p1;
            p1=i;           
        }       
        return strongPrimes;        
    }

General

I don't think I can get it any smaller without help. Doesn't anyone now of an other build in function to check for primes?

concerns

technically there is 2^(-2^31) chance that isProbablePrime(Integer.MAX_VALUE) returns true on a non prime but this doesn't happen for an integer.

It also outputs the numbers in reverse order but I didn't see anything about the order in which the primes should be outputted but that's an easy fix (although it could cost some bytes)

\$\endgroup\$
  • \$\begingroup\$ int[]s(int n){int s[]=new int[n],i=1,p=i,q=i;while(n>0)if(java.math.BigInteger.valueOf(++i).isProbablePrime(n.MAX_VALUE)){if(p>(i+q)/2)s[--n]=p;q=p;p=i;}return s;} without changing any code this should be a bit shorter \$\endgroup\$ – Roman Gräf Sep 3 '17 at 15:13
  • 1
    \$\begingroup\$ n.MAX_VALUE (which is equivalent to -1>>>1) can be replaced with 50 (upper bound for BigIntegers with less than 100 bits) (-9 bytes), if(p‌​>(i+q)/2) can be replaced with if(2*p>i+q)(-2 bytes). \$\endgroup\$ – Nevay Sep 3 '17 at 18:43
  • 1
    \$\begingroup\$ @KevinCruijssen The code doesn't actually use the BigIntegers for anything other than the primality check. \$\endgroup\$ – JollyJoker Sep 4 '17 at 13:29
  • 1
    \$\begingroup\$ @JollyJoker Ah, you're right. In that case the byte-count can be lowered to 133 bytes, like this: n->{int s[]=new int[n],i=1,p=i,q=i,j,t;while(n>0){for(j=2,t=++i;j<t;t=t%j++<1?0:t);if(t>1){if(p>(i+q)/2)s[--n]=p;q=p;p=i;}}return s;}. \$\endgroup\$ – Kevin Cruijssen Sep 4 '17 at 13:51
  • 1
    \$\begingroup\$ @JollyJoker 117 bytes (Only golfed your last if). \$\endgroup\$ – Olivier Grégoire Sep 4 '17 at 15:07
4
\$\begingroup\$

Python 2, 106 103 bytes

Edit: -3 bytes thanks to @Mr.Xcoder

n=input()
a=2;b=i=3
while n:
 i+=2
 if all(i%k for k in range(3,i)):
 	if i+a<b*2:print b;n-=1
	a,b=b,i

Try it online!

Quite straight forward. Loop through all prime numbers keeping track of the two last primes. When a new prime is found, we check if the previous prime is a strong prime, and then update the two primes kept track of. This is done until n strong primes have been found.

\$\endgroup\$
  • 2
    \$\begingroup\$ (i+a)/2<b means i+a<b*2 (105 bytes) \$\endgroup\$ – Mr. Xcoder Sep 3 '17 at 8:06
  • 2
    \$\begingroup\$ You can reorder them a bit: a=2;b=i=3 (103 bytes) \$\endgroup\$ – Mr. Xcoder Sep 3 '17 at 8:09
3
\$\begingroup\$

Pyth, 25 bytes

.f&P_Z>yZ+fP_ThZefP_TUZQ3

Try it here! or Check out the test Suite!


Explanation

Quite happy with this golf given that Pyth kind of lacks prime built-ins.

.f&P_Z>yZ+fP_ThZefP_TUZQ3    Full program. Note that Q means input.

.f                     Q3    First Q inputs with truthy results, starting at 3 and counting up by 1.
          fPThZ              First prime after the current number.
               efP_TUZ       The last prime before the current number.
         +                   Sum.
      >yZ                    Is the current number doubled higher than the sum?
  &P_Z                       And is the current number prime?
                             Output implicitly.
\$\endgroup\$
3
\$\begingroup\$

Mathematica, 81 66 bytes

Select[Partition[Prime@Range[#^2],3,1],Apply[#+#3<2#2&]][[;;#,2]]&  

thanx to @Marthe172 for -15 bytes

\$\endgroup\$
  • 1
    \$\begingroup\$ -15 bytes: Select[Partition[Prime@Range[#^2],3,1],Apply[#+#3<2#2&]][[;;#,2]]& \$\endgroup\$ – Lukas Lang Sep 3 '17 at 15:01
  • \$\begingroup\$ You could use Martin's answer here to make this way shorter. \$\endgroup\$ – Wheat Wizard Sep 3 '17 at 22:25
  • 4
    \$\begingroup\$ @WheatWizard you could use Martin's answers any way you like \$\endgroup\$ – J42161217 Sep 4 '17 at 0:07
2
\$\begingroup\$

Actually, 17 bytes

⌠;D;⌐P@P+½@P>⌡╓♂P

Try it online!

Explanation:

⌠;D;⌐P@P+½@P>⌡╓♂P
⌠;D;⌐P@P+½@P>⌡╓    first n values (starting with k=0) where:
  D    P             (k-1)th prime
   ;⌐P@ +            plus (k+1)th prime
         ½           divided by 2
 ;        @P>        is less than kth prime
               ♂P  primes at those indices
\$\endgroup\$
  • \$\begingroup\$ feature-request: P maps on a list \$\endgroup\$ – Erik the Outgolfer Sep 3 '17 at 14:37
  • \$\begingroup\$ @EriktheOutgolfer Actually has a GitHub repo. Make an issue there. \$\endgroup\$ – Mego Sep 3 '17 at 17:17
  • \$\begingroup\$ You probably misunderstood the meaning of the comment then :p (like, "this would've been shorter if behavior like other commands existed in this one too"...probably it was a fail...) \$\endgroup\$ – Erik the Outgolfer Sep 3 '17 at 17:32
2
\$\begingroup\$

05AB1E, 19 bytes

µNØN<ØN>Ø+;›i¼NØ}})

Try it online!

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

C++, 334 bytes, 318 with MSVC

-1 byte thanks to Mr.Xcoder -1 byte thanks to Zacharý

With the MSVC compilation, you don't need to include the cmath header yourself, it compiles without

#include<vector>
#include<cmath>
typedef std::vector<int>v;v p{2};int i(int t){int m=sqrt(t)+2,i=2;for(;i<m;++i)if(t%i<1)return 0;return 1;}void n(){int l=p.back()+1;while(!i(l))++l;p.push_back(l);}auto s(int m){if(!m)return v();n();n();v r;while(r.size()!=m){if((p[0]+p[2])/2<p[1])r.push_back(p[1]);p.erase(p.begin());n();}return r;}

tsh and Mr.Xcoder answer : 131 bytes

tsh rewrote the answer in 139 bytes ( -195 ), and Mr.Xcoder golfed it more with 131 bytes

int N,t,o,a,b,i;void n(){t=++N;for(o=2;++o<t;)if(t%o<1)n();}void s(int m,int*r){b=N=t=5;for(;i<m;)if(a=b,b=t,n(),b+b>a+t)r[i++]=b;}

Mr.Xcoder TIO Link

First version ungolfed :

#include<vector>
#include<cmath>
typedef std::vector<int> v;
v p{2};
//Tells if a number is prime or not
int i(int t) {
    int m = sqrt(t) + 2, i = 2;
    for (;i < m;++i)
        if (t%i < 1)
            return 0;
    return 1;
}
//Push back the next prime number
void n() {
    int l = p.back() + 1;
    while (!i(l))
        ++l;
    p.push_back(l);
}
//Generate a list of m strong primes
auto s(int m) {
    if (!m)
        return v();
    n();
    n();
    v r;
    while (r.size() != m) {
        if ((p[0] + p[2]) / 2 < p[1])
            r.push_back(p[1]);
        p.erase(p.begin());
        n();
    }
    return r;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ You can save 1 byte by replacing if(t%i==0) with if(t%i<1). \$\endgroup\$ – Mr. Xcoder Sep 3 '17 at 12:49
  • \$\begingroup\$ 1. Where are you getting sqrt from? 2. I think you can remove the space between std::vector<int> and v. \$\endgroup\$ – Zacharý Sep 3 '17 at 18:04
  • \$\begingroup\$ @Zacharý From the vector include file, apparently. It compiles with MSVC, haven't test with GCC, though \$\endgroup\$ – HatsuPointerKun Sep 3 '17 at 18:12
  • \$\begingroup\$ Then place a note about it being MSVC-only, since I've tested on g++, and it doesn't work due to sqrt. Also, is that byte count still correct? \$\endgroup\$ – Zacharý Sep 3 '17 at 18:14
  • \$\begingroup\$ @Zacharý I think it's correct. I used the byte counter snippet from code golf meta to do the count \$\endgroup\$ – HatsuPointerKun Sep 3 '17 at 18:31
1
\$\begingroup\$

Haskell, 123 121 114 85 bytes

import Data.List
g=(`take`(tails(nubBy(((>1).).gcd)[2..])>>=(\(a:b:c:_)->[b|b-a>c-b])))

(anonymous function courtesy of H.PWiz; I initially thought I must both print and then return, so had a longer code)

(not counting the g= bit)

Running it:

~> g 7
[11,17,29,37,41,59,67]
\$\endgroup\$
  • \$\begingroup\$ @H.PWiz thanks, on all counts! \$\endgroup\$ – Will Ness Sep 3 '17 at 22:29
  • \$\begingroup\$ Don't need to include g=, see this \$\endgroup\$ – H.PWiz Sep 3 '17 at 22:33
  • \$\begingroup\$ @H.PWiz can I just have the anonymous function by itself? Trying it with the CPP pragma, it didn't work, probably because of the import. \$\endgroup\$ – Will Ness Sep 3 '17 at 22:48
  • \$\begingroup\$ (like this) \$\endgroup\$ – Will Ness Sep 3 '17 at 22:50
  • \$\begingroup\$ You don't need the CPP bit, I was just looking for a post that explained that g= wasn't counted. \$\endgroup\$ – H.PWiz Sep 3 '17 at 23:04
0
\$\begingroup\$

Python 2 + SymPy, 118 bytes

Not as short as the classic approach, but I think it's worth posting.

from sympy.ntheory import*
def f(i):
 k=3
 while i:
	if prevprime(k)+nextprime(k)<k*2and isprime(k):i-=1;yield k
	k+=2

Try it online!

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

Axiom, 109 bytes

h(n)==(c:=s:=3;r:=[];for i in 5..by 2|prime?(i)repeat(#r>=n=>break;p:=c;c:=s;s:=i;p+s<2*c=>(r:=cons(c,r)));r)

ungolf and results

f(n)==
   p:=c:=s:=3;r:List INT:=[]
   for i in 5.. by 2|prime?(i) repeat
      #r>=n=>break
      p:=c;c:=s;s:=i;(p+s)/2<c=>(r:=cons(c,r))
   r

(4) -> f 47
   (4)
   [599, 587, 569, 557, 541, 521, 499, 487, 479, 461, 457, 439, 431, 419, 397,
    379, 367, 347, 331, 311, 307, 281, 277, 269, 251, 239, 227, 223, 197, 191,
    179, 163, 149, 137, 127, 107, 101, 97, 79, 71, 67, 59, 41, 37, 29, 17, 11]
\$\endgroup\$
0
\$\begingroup\$

Python 2, 86 bytes

n=input()
u=p=2;v=i=3
while n:
 p*=i;i+=1
 if p*p%i:
	if u+i<2*v:print v;n-=1
	u,v=v,i

Try it online!

Uses Wilson's theorem for the primality test.

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

Kotlin, 181 180 bytes

fun f(l:Int):Array<Int>{var a=1
var b=1
var i=0
var c=0
val o=Array(l,{0})
while(l>0){c++
if((1..c).filter{c%it==0}.size==2){if(c-b<b-a){o[i]=b
if(++i>=l)break}
a=b
b=c}}
return o}

Try it online!

Explained

fun f(l: Int): Array<Int> {
    var a = 1 // Lowest prime
    var b = 1 // Middle prime
    var i = 0 // Current prime index
    var c = 0 // Highest prime
    val o = Array(l, { 0 }) // Output array
    while (l > 0) {  // Functions as while true, while skipping for the 0 case
        c++ // Increment the highest prime
        if ((1..c).filter { c % it == 0 }.size == 2) { // Only if it is prime
            if (c - b < b - a) {                       // If it is strongly prime
                o[i] = b                               // Then record it
                if (++i >= l) break                    // If we have all the answers then stop
            }                                     
            a = b                                      // Rotate the primes
            b = c                                      // As above
        }
    }
    return o  // Return the answer
}
\$\endgroup\$

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