I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

Quadrat Special Primes

From Rosetta Code
Quadrat Special Primes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Task

n   is smallest prime such that the difference of successive terms are the smallest squares of positive integers, where     n   <   16000.

ALGOL 68[edit]

Translation of: ALGOL W
BEGIN # find some primes where the gap between the current prime and the next is a square #
# reurns a sieve of primes up to n #
PROC eratosthenes = ( INT n )[]BOOL:
BEGIN
[ 1 : n ]BOOL p;
p[ 1 ] := FALSE; p[ 2 ] := TRUE;
FOR i FROM 3 BY 2 TO n DO p[ i ] := TRUE OD;
FOR i FROM 4 BY 2 TO n DO p[ i ] := FALSE OD;
FOR i FROM 3 BY 2 TO ENTIER sqrt( n ) DO
IF p[ i ] THEN FOR s FROM i * i BY i + i TO n DO p[ s ] := FALSE OD FI
OD;
p
END # eratosthenes # ;
# an array of squares #
PROC get squares = ( INT n )[]INT:
BEGIN
[ 1 : n ]INT s;
FOR i TO n DO s[ i ] := i * i OD;
s
END # get squares # ;
INT max number = 16000;
[]BOOL prime = eratosthenes( max number );
[]INT square = get squares( max number );
INT p count, this prime, next prime;
# the first square gap is 1 (between 2 and 3) the gap between all other primes is even #
# so we treat 2-3 as a special case #
p count := 1; this prime := 2; next prime := 3;
print( ( " ", whole( this prime, -5 ) ) );
WHILE next prime < max number DO
this prime := next prime;
p count +:= 1;
print( ( " ", whole( this prime, -5 ) ) );
IF p count MOD 12 = 0 THEN print( ( newline ) ) FI;
INT sq pos := 2;
WHILE next prime := this prime + square[ sq pos ];
IF next prime < max number THEN NOT prime[ next prime ] ELSE FALSE FI
DO sq pos +:= 2 OD
OD
END
Output:
     2     3     7    11    47    83   227   263   587   911   947   983
  1019  1163  1307  1451  1487  1523  1559  2459  3359  4259  4583  5483
  5519  5843  5879  6203  6779  7103  7247  7283  7607  7643  8219  8363
 10667 11243 11279 11423 12323 12647 12791 13367 13691 14591 14627 14771
 15671

ALGOL W[edit]

begin % find some primes where the gap between the current prime and the next is a square %
 % sets p( 1 :: n ) to a sieve of primes up to n %
procedure Eratosthenes ( logical array p( * ) ; integer value n ) ;
begin
p( 1 ) := false; p( 2 ) := true;
for i := 3 step 2 until n do p( i ) := true;
for i := 4 step 2 until n do p( i ) := false;
for i := 3 step 2 until truncate( sqrt( n ) ) do begin
integer ii; ii := i + i;
if p( i ) then for pr := i * i step ii until n do p( pr ) := false
end for_i ;
end Eratosthenes ;
 % sets s( 1 :: n ) to the squares %
procedure getSquares ( integer array s ( * ) ; integer value n ) ;
for i := 1 until n do s( i ) := i * i;
integer MAX_NUMBER;
MAX_NUMBER := 16000;
begin
logical array prime( 1 :: MAX_NUMBER );
integer array square( 1 :: MAX_NUMBER );
integer pCount, thisPrime, nextPrime;
 % sieve the primes to MAX_NUMBER %
Eratosthenes( prime, MAX_NUMBER );
 % calculate the squares to MAX_NUMBER %
getSquares( square, MAX_NUMBER );
 % the first gap is 1 (between 2 and 3) the gap between all other primes is even %
 % so we treat 2-3 as a special case  %
pCount := 1; thisPrime := 2; nextPrime := 3;
write( i_w := 6, s_w := 0, " ", thisPrime );
while nextPrime < MAX_NUMBER do begin
integer sqPos;
thisPrime := nextPrime;
pCount := pCount + 1;
writeon( i_w := 6, s_w := 0, " ", thisPrime );
if pCount rem 12 = 0 then write();
sqPos := 2;
while begin
nextPrime := thisPrime + square( sqPos );
nextPrime < MAX_NUMBER and not prime( nextPrime )
end do sqPos := sqPos + 2;
end while_thisPrime_lt_MAX_NUMBER
end
end.
Output:
      2      3      7     11     47     83    227    263    587    911    947    983
   1019   1163   1307   1451   1487   1523   1559   2459   3359   4259   4583   5483
   5519   5843   5879   6203   6779   7103   7247   7283   7607   7643   8219   8363
  10667  11243  11279  11423  12323  12647  12791  13367  13691  14591  14627  14771
  15671


FreeBASIC[edit]

 
#include "isprime.bas"
 
dim as integer p = 2, j = 1
print 2;" ";
do
do
if isprime(p + j*j) then exit do
j += 1
loop
p += j*j
if p > 16000 then exit do
print p;" ";
j = 1
loop
print
 
Output:
2  3  7  11  47  83  227  263  587  911  947  983  1019  1163  1307  1451  1487  1523  1559  2459  3359  4259  4583  5483  5519  5843  5879  6203  6779  7103  7247  7283  7607  7643  8219  8363  10667  11243  11279  11423  12323  12647  12791  13367  13691  14591  14627  14771  15671

Go[edit]

Translation of: Wren
package main
 
import (
"fmt"
"math"
)
 
func sieve(limit int) []bool {
limit++
// True denotes composite, false denotes prime.
c := make([]bool, limit) // all false by default
c[0] = true
c[1] = true
// no need to bother with even numbers over 2 for this task
p := 3 // Start from 3.
for {
p2 := p * p
if p2 >= limit {
break
}
for i := p2; i < limit; i += 2 * p {
c[i] = true
}
for {
p += 2
if !c[p] {
break
}
}
}
return c
}
 
func isSquare(n int) bool {
s := int(math.Sqrt(float64(n)))
return s*s == n
}
 
func commas(n int) string {
s := fmt.Sprintf("%d", n)
if n < 0 {
s = s[1:]
}
le := len(s)
for i := le - 3; i >= 1; i -= 3 {
s = s[0:i] + "," + s[i:]
}
if n >= 0 {
return s
}
return "-" + s
}
 
func main() {
c := sieve(15999)
fmt.Println("Quadrat special primes under 16,000:")
fmt.Println(" Prime1 Prime2 Gap Sqrt")
lastQuadSpecial := 3
gap := 1
count := 1
fmt.Printf("%7d %7d %6d %4d\n", 2, 3, 1, 1)
for i := 5; i < 16000; i += 2 {
if c[i] {
continue
}
gap = i - lastQuadSpecial
if isSquare(gap) {
sqrt := int(math.Sqrt(float64(gap)))
fmt.Printf("%7s %7s %6s %4d\n", commas(lastQuadSpecial), commas(i), commas(gap), sqrt)
lastQuadSpecial = i
count++
}
}
fmt.Println("\n", count+1, "such primes found.")
}
Output:
Same as Wren example.

Julia[edit]

using Primes
 
function quadrat(N = 16000)
pmask = primesmask(1, N)
qprimes, lastn = [2], isqrt(N)
while (n = qprimes[end]) < N
for i in 1:lastn
q = n + i * i
if q > N
return qprimes
elseif pmask[q] # got next qprime
push!(qprimes, q)
break
end
end
end
end
 
println("Quadrat special primes < 16000:")
foreach(p -> print(rpad(p[2], 6), p[1] % 10 == 0 ? "\n" : ""), enumerate(quadrat()))
 
Output:
Quadrat special primes < 16000:
2     3     7     11    47    83    227   263   587   911   
947   983   1019  1163  1307  1451  1487  1523  1559  2459
3359  4259  4583  5483  5519  5843  5879  6203  6779  7103
7247  7283  7607  7643  8219  8363  10667 11243 11279 11423
12323 12647 12791 13367 13691 14591 14627 14771 15671

Phix[edit]

constant desc = split("linear quadratic cubic quartic quintic sextic septic octic nonic decic"),
         limits =       {1,     16000,  15000, 14e9,  8025e5, 25e12, 195e12,75e11, 3e9, 11e8}
for p=2 to length(desc) do
    atom N = limits[p], lastn = ceil(power(N,1/p))
    sequence res = {2}
    bool done = false
    while not done do
        for n=1 to lastn do
            atom m = res[$] + power(n,p)
            if m>N then
                done = true
                exit
            elsif is_prime(m) then
                res &= m
                exit
            end if
        end for
    end while
    string r = join_by(apply(true,sprintf,{{"%,6d"},res}),1,p+5)
    printf(1,"Found %d %s special primes < %g:\n%s\n",{length(res),desc[p],N,r})
end for
Output:
Found 49 quadratic special primes < 16000:
     2        3        7       11       47       83      227
   263      587      911      947      983    1,019    1,163
 1,307    1,451    1,487    1,523    1,559    2,459    3,359
 4,259    4,583    5,483    5,519    5,843    5,879    6,203
 6,779    7,103    7,247    7,283    7,607    7,643    8,219
 8,363   10,667   11,243   11,279   11,423   12,323   12,647
12,791   13,367   13,691   14,591   14,627   14,771   15,671

Found 23 cubic special primes < 15000:
     2        3       11       19       83    1,811    2,027    2,243
 2,251    2,467    2,531    2,539    3,539    3,547    4,547    5,059
10,891   12,619   13,619   13,627   13,691   13,907   14,419

Found 9 quartic special primes < 1.4e+10:
     2        3       19   160,019   1,049,920,019   1,050,730,019   1,051,540,019   12,910,750,019   13,960,510,019

Found 9 quintic special primes < 8.025e+8:
     2        3   32,771   32,803   33,827   41,603   579,427   778,179,427   802,479,427

Found 6 sextic special primes < 2.5e+13:
     2        3       67      131   2,176,782,467   22,485,250,805,891

Found 7 septic special primes < 1.95e+14:
     2        3      131   194,871,710,000,131   194,893,580,000,131   194,893,580,280,067   194,971,944,444,163

Found 4 octic special primes < 7.5e+12:
     2        3   65,539   6,553,600,065,539

Found 6 nonic special primes < 3e+9:
     2        3   262,147   10,339,843   20,417,539   1,020,417,539

Found 4 decic special primes < 1.1e+9:
     2        3   1,073,741,827   1,073,742,851

Raku[edit]

my @sqp = 2, -> $previous {
my $next;
for (1..).map: *² {
$next = $previous + $_;
last if $next.is-prime;
}
$next
}*;
 
say "{+$_} matching numbers:\n", $_».fmt('%5d').batch(7).join: "\n" given
@sqp[^(@sqp.first: * > 16000, :k)];
Output:
49 matching numbers:
    2     3     7    11    47    83   227
  263   587   911   947   983  1019  1163
 1307  1451  1487  1523  1559  2459  3359
 4259  4583  5483  5519  5843  5879  6203
 6779  7103  7247  7283  7607  7643  8219
 8363 10667 11243 11279 11423 12323 12647
12791 13367 13691 14591 14627 14771 15671

REXX[edit]

/*REXX program finds the smallest primes such that the difference of successive terms   */
/*─────────────────────────────────────────────────── are the smallest quadrat numbers. */
parse arg hi cols . /*obtain optional argument from the CL.*/
if hi=='' | hi=="," then hi= 16000 /* " " " " " " */
if cols=='' | cols=="," then cols= 10 /* " " " " " " */
call genP /*build array of semaphores for primes.*/
w= 10 /*width of a number in any column. */
@sqp= 'the smallest primes < ' commas(hi) " such that the" ,
'difference of successive terma are the smallest quadrat numbers'
if cols>0 then say ' index │'center(@sqp , 1 + cols*(w+1) )
if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─')
sqp= 0; idx= 1 /*initialize number of sqp and index.*/
op= 1
$= /*a list of nice primes (so far). */
do j=0 by 0
do k=1 until !.np; np= op + k*k /*find the next square + oldPrime.*/
if np>= hi then leave j /*Is newPrime too big? Then quit.*/
end /*k*/
sqp= sqp + 1 /*bump the number of sqp's. */
op= np /*assign the newPrime to the oldPrime*/
if cols==0 then iterate /*Build the list (to be shown later)? */
c= commas(np) /*maybe add commas to the number. */
$= $ right(c, max(w, length(c) ) ) /*add a nice prime ──► list, allow big#*/
if sqp//cols\==0 then iterate /*have we populated a line of output? */
say center(idx, 7)'│' substr($, 2); $= /*display what we have so far (cols). */
idx= idx + cols /*bump the index count for the output*/
end /*j*/
 
if $\=='' then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/
say
say 'Found ' commas(sqp) " of " @sqp
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ?
/*──────────────────────────────────────────────────────────────────────────────────────*/
genP: !.= 0 /*placeholders for primes (semaphores).*/
@.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define some low primes. */
 !.2=1;  !.3=1;  !.5=1;  !.7=1;  !.11=1 /* " " " " flags. */
#=5; s.#= @.# **2 /*number of primes so far; prime². */
/* [↓] generate more primes ≤ high.*/
do [email protected].#+2 by 2 to hi /*find odd primes from here on. */
parse var j '' -1 _; if _==5 then iterate /*J divisible by 5? (right dig)*/
if j// 3==0 then iterate /*" " " 3? */
if j// 7==0 then iterate /*" " " 7? */
/* [↑] the above five lines saves time*/
do k=5 while s.k<=j /* [↓] divide by the known odd primes.*/
if j // @.k == 0 then iterate j /*Is J ÷ X? Then not prime. ___ */
end /*k*/ /* [↑] only process numbers ≤ √ J */
#= #+1; @.#= j; s.#= j*j;  !.j= 1 /*bump # of Ps; assign next P; P²; P# */
end /*j*/; return
output   when using the default inputs:
 index │ the smallest primes  <  16,000  such that the difference of successive terma are the smallest quadrat numbers
───────┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────
   1   │          2          3          7         11         47         83        227        263        587        911
  11   │        947        983      1,019      1,163      1,307      1,451      1,487      1,523      1,559      2,459
  21   │      3,359      4,259      4,583      5,483      5,519      5,843      5,879      6,203      6,779      7,103
  31   │      7,247      7,283      7,607      7,643      8,219      8,363     10,667     11,243     11,279     11,423
  41   │     12,323     12,647     12,791     13,367     13,691     14,591     14,627     14,771     15,671

Found  49  of  the smallest primes  <  16,000  such that the difference of successive terma are the smallest quadrat numbers

Ring[edit]

load "stdlib.ring"
 
/* Searching for the smallest prime gaps under a limit,
such that the difference of successive terms (gaps)
is of the smallest degree. */
 
? "working..."
 
desc = split("na quadratic cubic quartic quintic sextic septic octic nonic decic"," ")
limits = [1, 16000, 15000, 30000, 50000, 50000, 50000, 75000, 300000, 500000]
for deg = 2 to len(desc)
 
Primes = []
limit = limits[deg]
oldPrime = 2
add(Primes, 2)
 
for n = 1 to sqrt(limit)
nextPrime = oldPrime + pow(n, deg)
if isprime(nextPrime)
n = 1
if nextPrime < limit add(Primes, nextPrime) ok
oldPrime = nextPrime
else
nextPrime = nextPrime - oldPrime
ok
if nextPrime > limit exit ok
next
 
 ? nl + desc[deg] + ":" + nl + " prime1 prime2 Gap Rt"
for n = 1 to Len(Primes) - 1
diff = Primes[n + 1] - Primes[n]
 ? sf(Primes[n], 7) + " " + sf(Primes[n+1], 7) + " " + sf(diff, 6) + " " + sf(floor(0.49 + pow(diff, 1 / deg)), 4)
next
 
 ? "Found " + Len(Primes) + " primes under " + limit + " for " + desc[deg] + " gaps."
next
? nl + "done..."
 
# a very plain string formatter, intended to even up columnar outputs
def sf x, y
s = string(x) l = len(s)
if l > y y = l ok
return substr(" ", 11 - y + l) + s
Output:
working...

quadratic:
 prime1  prime2    Gap   Rt
      2       3      1    1
      3       7      4    2
      7      11      4    2
     11      47     36    6
     47      83     36    6
     83     227    144   12
    227     263     36    6
    263     587    324   18
    587     911    324   18
    911     947     36    6
    947     983     36    6
    983    1019     36    6
   1019    1163    144   12
   1163    1307    144   12
   1307    1451    144   12
   1451    1487     36    6
   1487    1523     36    6
   1523    1559     36    6
   1559    2459    900   30
   2459    3359    900   30
   3359    4259    900   30
   4259    4583    324   18
   4583    5483    900   30
   5483    5519     36    6
   5519    5843    324   18
   5843    5879     36    6
   5879    6203    324   18
   6203    6779    576   24
   6779    7103    324   18
   7103    7247    144   12
   7247    7283     36    6
   7283    7607    324   18
   7607    7643     36    6
   7643    8219    576   24
   8219    8363    144   12
   8363   10667   2304   48
  10667   11243    576   24
  11243   11279     36    6
  11279   11423    144   12
  11423   12323    900   30
  12323   12647    324   18
  12647   12791    144   12
  12791   13367    576   24
  13367   13691    324   18
  13691   14591    900   30
  14591   14627     36    6
  14627   14771    144   12
  14771   15671    900   30
Found 49 primes under 16000 for quadratic gaps.

cubic:
 prime1  prime2    Gap   Rt
      2       3      1    1
      3      11      8    2
     11      19      8    2
     19      83     64    4
     83    1811   1728   12
   1811    2027    216    6
   2027    2243    216    6
   2243    2251      8    2
   2251    2467    216    6
   2467    2531     64    4
   2531    2539      8    2
   2539    3539   1000   10
   3539    3547      8    2
   3547    4547   1000   10
   4547    5059    512    8
   5059   10891   5832   18
  10891   12619   1728   12
  12619   13619   1000   10
  13619   13627      8    2
  13627   13691     64    4
  13691   13907    216    6
  13907   14419    512    8
Found 23 primes under 15000 for cubic gaps.

quartic:
 prime1  prime2    Gap   Rt
      2       3      1    1
      3      19     16    2
Found 3 primes under 30000 for quartic gaps.

quintic:
 prime1  prime2    Gap   Rt
      2       3      1    1
      3   32771  32768    8
  32771   32803     32    2
  32803   33827   1024    4
  33827   41603   7776    6
Found 6 primes under 50000 for quintic gaps.

sextic:
 prime1  prime2    Gap   Rt
      2       3      1    1
      3      67     64    2
     67     131     64    2
Found 4 primes under 50000 for sextic gaps.

septic:
 prime1  prime2    Gap   Rt
      2       3      1    1
      3     131    128    2
Found 3 primes under 50000 for septic gaps.

octic:
 prime1  prime2    Gap   Rt
      2       3      1    1
      3   65539  65536    4
Found 3 primes under 75000 for octic gaps.

nonic:
 prime1  prime2    Gap   Rt
      2       3      1    1
      3  262147 262144    4
Found 3 primes under 300000 for nonic gaps.

decic:
 prime1  prime2    Gap   Rt
      2       3      1    1
Found 2 primes under 500000 for decic gaps.

done...

Wren[edit]

Library: Wren-math
Library: Wren-fmt
import "/math" for Int
import "/fmt" for Fmt
 
var isSquare = Fn.new { |n|
var s = n.sqrt.floor
return s*s == n
}
 
var primes = Int.primeSieve(15999)
System.print("Quadrat special primes under 16,000:")
System.print(" Prime1 Prime2 Gap Sqrt")
var lastQuadSpecial = 3
var gap = 1
var count = 1
Fmt.print("$,7d $,7d $,6d $4d", 2, 3, 1, 1)
for (p in primes.skip(2)) {
gap = p - lastQuadSpecial
if (isSquare.call(gap)) {
Fmt.print("$,7d $,7d $,6d $4d", lastQuadSpecial, p, gap, gap.sqrt)
lastQuadSpecial = p
count = count + 1
}
}
System.print("\n%(count+1) such primes found.")
Output:
Quadrat special primes under 16,000:
 Prime1  Prime2    Gap  Sqrt
      2       3      1    1
      3       7      4    2
      7      11      4    2
     11      47     36    6
     47      83     36    6
     83     227    144   12
    227     263     36    6
    263     587    324   18
    587     911    324   18
    911     947     36    6
    947     983     36    6
    983   1,019     36    6
  1,019   1,163    144   12
  1,163   1,307    144   12
  1,307   1,451    144   12
  1,451   1,487     36    6
  1,487   1,523     36    6
  1,523   1,559     36    6
  1,559   2,459    900   30
  2,459   3,359    900   30
  3,359   4,259    900   30
  4,259   4,583    324   18
  4,583   5,483    900   30
  5,483   5,519     36    6
  5,519   5,843    324   18
  5,843   5,879     36    6
  5,879   6,203    324   18
  6,203   6,779    576   24
  6,779   7,103    324   18
  7,103   7,247    144   12
  7,247   7,283     36    6
  7,283   7,607    324   18
  7,607   7,643     36    6
  7,643   8,219    576   24
  8,219   8,363    144   12
  8,363  10,667  2,304   48
 10,667  11,243    576   24
 11,243  11,279     36    6
 11,279  11,423    144   12
 11,423  12,323    900   30
 12,323  12,647    324   18
 12,647  12,791    144   12
 12,791  13,367    576   24
 13,367  13,691    324   18
 13,691  14,591    900   30
 14,591  14,627     36    6
 14,627  14,771    144   12
 14,771  15,671    900   30

49 such primes found.