Generate strong primes

Question

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

Answer 1

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.

Answer 2

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, ...

Answer 3

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)

Answer 4

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.

Answer 5

Mathematica, 81 66 bytes

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

thanx to @Marthe172 for -15 bytes

Answer 6

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.

Answer 7

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

Answer 8

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;
}

Answer 9

05AB1E, 19 bytes

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

Try it online!

Answer 10

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]

Answer 11

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!

Answer 12

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]

Answer 13

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.

Answer 14

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
}