Consecutive primes with ascending or descending differences
Consecutive primes with ascending or descending differences 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
Find and display here on this page, the longest sequence of consecutive prime numbers where the differences between the primes are strictly ascending.
Do the same for sequences of primes where the differences are strictly descending.
In both cases, show the sequence for primes < 1 000 000.
If there are multiple sequences of the same length, only the first need be shown.
ALGOL 68
<lang algol68>BEGIN # find sequences of primes where the gaps between the elements #
# are strictly ascending/descending #
# reurns a list of primes up to n #
PROC prime list = ( INT n )[]INT:
BEGIN
# sieve the primes to n #
INT no = 0, yes = 1;
[ 1 : n ]INT p;
p[ 1 ] := no; p[ 2 ] := yes;
FOR i FROM 3 BY 2 TO n DO p[ i ] := yes OD;
FOR i FROM 4 BY 2 TO n DO p[ i ] := no OD;
FOR i FROM 3 BY 2 TO ENTIER sqrt( n ) DO
IF p[ i ] = yes THEN FOR s FROM i * i BY i + i TO n DO p[ s ] := no OD FI
OD;
# replace the sieve with a list #
INT p pos := 0;
FOR i TO n DO IF p[ i ] = yes THEN p[ p pos +:= 1 ] := i FI OD;
p[ 1 : p pos ]
END # prime list # ;
# find the longest sequence of primes where the successive differences are ascending #
INT max number = 1 000 000;
[]INT primes = prime list( max number );
INT asc length := 0;
INT asc start := 0;
INT desc length := 0;
INT desc start := 0;
FOR p FROM LWB primes TO UPB primes DO
INT prev diff := 0;
INT length := 1;
FOR s FROM p + 1 TO UPB primes
WHILE INT diff = primes[ s ] - primes[ s - 1 ];
diff > prev diff
DO
length +:= 1;
prev diff := diff
OD;
IF length > asc length THEN
# found a longer sequence #
asc length := length;
asc start := p
FI
OD;
# find the longest sequence of primes where the successive differences are descending #
FOR p FROM LWB primes TO UPB primes DO
INT prev diff := max number + 1;
INT length := 1;
FOR s FROM p + 1 TO UPB primes
WHILE INT diff = primes[ s ] - primes[ s - 1 ];
diff < prev diff
DO
length +:= 1;
prev diff := diff
OD;
IF length > desc length THEN
# found a longer sequence #
desc length := length;
desc start := p
FI
OD;
# show the sequences #
print( ( "For primes up to ", whole( max number, 0 ), newline ) );
print( ( " Longest sequence of primes with ascending differences contains "
, whole( asc length, 0 )
, " primes, first such sequence:"
, newline
, "(differences in brackets):"
, newline
, " "
)
);
print( ( whole( primes[ asc start ], 0 ) ) );
FOR p FROM asc start + 1 TO asc start + ( asc length - 1 ) DO
print( ( " (", whole( primes[ p ] - primes[ p - 1 ], 0 ), ") ", whole( primes[ p ], 0 ) ) )
OD;
print( ( newline ) );
print( ( " Longest sequence of primes with descending differences contains "
, whole( asc length, 0 )
, " primes, first such sequence:"
, newline
, "(differences in brackets):"
, newline
, " "
)
);
print( ( whole( primes[ desc start ], 0 ) ) );
FOR p FROM desc start + 1 TO desc start + ( desc length - 1 ) DO
print( ( " (", whole( primes[ p ] - primes[ p - 1 ], 0 ), ") ", whole( primes[ p ], 0 ) ) )
OD;
print( ( newline ) )
END</lang>
- Output:
For primes up to 1000000
Longest sequence of primes with ascending differences contains 8 primes, first such sequence:
(differences in brackets):
128981 (2) 128983 (4) 128987 (6) 128993 (8) 129001 (10) 129011 (12) 129023 (14) 129037
Longest sequence of primes with descending differences contains 8 primes, first such sequence:
(differences in brackets):
322171 (22) 322193 (20) 322213 (16) 322229 (8) 322237 (6) 322243 (4) 322247 (2) 322249
Factor
<lang factor>USING: arrays assocs formatting grouping io kernel literals math math.primes math.statistics sequences sequences.extras tools.memory.private ;
<< CONSTANT: limit 1,000,000 >>
CONSTANT: primes $[ limit primes-upto ]
- run ( n quot -- seq quot )
[ primes ] [ <clumps> ] [ ] tri* '[ differences _ monotonic? ] ; inline
- max-run ( quot -- n )
1 swap '[ 1 + dup _ run find drop ] loop 1 - ; inline
- runs ( quot -- seq )
[ max-run ] keep run filter ; inline
- .run ( seq -- )
dup differences [ [ commas ] map ] bi@
[ "(" ")" surround ] map 2array round-robin " " join print ;
- .runs ( quot -- )
[ runs ] keep [ < ] = "rising" "falling" ? limit commas "Largest run(s) of %s gaps between primes less than %s:\n" printf [ .run ] each ; inline
[ < ] [ > ] [ .runs nl ] bi@</lang>
- Output:
Largest run(s) of rising gaps between primes less than 1,000,000: 128,981 (2) 128,983 (4) 128,987 (6) 128,993 (8) 129,001 (10) 129,011 (12) 129,023 (14) 129,037 402,581 (2) 402,583 (4) 402,587 (6) 402,593 (8) 402,601 (12) 402,613 (18) 402,631 (60) 402,691 665,111 (2) 665,113 (4) 665,117 (6) 665,123 (8) 665,131 (10) 665,141 (12) 665,153 (24) 665,177 Largest run(s) of falling gaps between primes less than 1,000,000: 322,171 (22) 322,193 (20) 322,213 (16) 322,229 (8) 322,237 (6) 322,243 (4) 322,247 (2) 322,249 752,207 (44) 752,251 (12) 752,263 (10) 752,273 (8) 752,281 (6) 752,287 (4) 752,291 (2) 752,293
Julia
<lang julia>using Primes
function primediffseqs(maxnum = 1_000_000)
mprimes = primes(maxnum)
diffs = map(p -> mprimes[p[1] + 1] - p[2], enumerate(@view mprimes[begin:end-1]))
incstart, decstart, bestinclength, bestdeclength = 1, 1, 0, 0
for i in 1:length(diffs)-1
foundinc, founddec = false, false
for j in i+1:length(diffs)
if !foundinc && diffs[j] <= diffs[j - 1]
if (runlength = j - i) > bestinclength
bestinclength, incstart = runlength, i
end
foundinc = true
end
if !founddec && diffs[j] >= diffs[j - 1]
if (runlength = j - i) > bestdeclength
bestdeclength, decstart = runlength, i
end
founddec = true
end
foundinc && founddec && break
end
end
println("Ascending: ", mprimes[incstart:incstart+bestinclength], " Diffs: ", diffs[incstart:incstart+bestinclength-1])
println("Descending: ", mprimes[decstart:decstart+bestdeclength], " Diffs: ", diffs[decstart:decstart+bestdeclength-1])
end
primediffseqs()
</lang>
- Output:
Ascending: [128981, 128983, 128987, 128993, 129001, 129011, 129023, 129037] Diffs: [2, 4, 6, 8, 10, 12, 14] Descending: [322171, 322193, 322213, 322229, 322237, 322243, 322247, 322249] Diffs: [22, 20, 16, 8, 6, 4, 2]
Phix
integer pn = 1, -- prime numb lp = 2, -- last prime lg = 0, -- last gap pd = 0 -- prev d sequence cr = {0,0}, -- curr run [a,d] mr = {{0},{0}} -- max runs "" while true do pn += 1 integer p = get_prime(pn), gap = p-lp, d = compare(gap,lg) if p>1e6 then exit end if if d then integer i = (3-d)/2 cr[i] = iff(d=pd?cr[i]:lp!=2)+1 if cr[i]>mr[i][1] then mr[i] = {cr[i],pn} end if end if {pd,lp,lg} = {d,p,gap} end while for run=1 to 2 do integer {l,e} = mr[run] sequence p = apply(tagset(e,e-l),get_prime), g = sq_sub(p[2..$],p[1..$-1]) printf(1,"longest %s run length %d: %v gaps: %v\n", {{"ascending","descending"}[run],length(p),p,g}) end for
- Output:
longest ascending run length 8: {128981,128983,128987,128993,129001,129011,129023,129037} gaps: {2,4,6,8,10,12,14}
longest descending run length 8: {322171,322193,322213,322229,322237,322243,322247,322249} gaps: {22,20,16,8,6,4,2}
Raku
<lang perl6>use Math::Primesieve; use Lingua::EN::Numbers;
my $sieve = Math::Primesieve.new;
my $limit = 1000000;
my @primes = $sieve.primes($limit);
sub runs (&op) {
my $diff = 1; my $run = 1;
my @diff = flat 1, (1..^@primes).map: {
my $next = @primes[$_] - @primes[$_ - 1];
if &op($next, $diff) { ++$run } else { $run = 1 }
$diff = $next;
$run;
}
my $max = max @diff; my @runs = @diff.grep: * == $max, :k;
@runs.map( {
my @run = (0..$max).reverse.map: -> $r { @primes[$_ - $r] }
flat roundrobin(@run».&comma, @run.rotor(2 => -1).map({[R-] $_})».fmt('(%d)'));
} ).join: "\n"
}
say "Longest run(s) of ascending prime gaps up to {comma $limit}:\n" ~ runs(&infix:«>»);
say "\nLongest run(s) of descending prime gaps up to {comma $limit}:\n" ~ runs(&infix:«<»);</lang>
- Output:
Longest run(s) of ascending prime gaps up to 1,000,000: 128,981 (2) 128,983 (4) 128,987 (6) 128,993 (8) 129,001 (10) 129,011 (12) 129,023 (14) 129,037 402,581 (2) 402,583 (4) 402,587 (6) 402,593 (8) 402,601 (12) 402,613 (18) 402,631 (60) 402,691 665,111 (2) 665,113 (4) 665,117 (6) 665,123 (8) 665,131 (10) 665,141 (12) 665,153 (24) 665,177 Longest run(s) of descending prime gaps up to 1,000,000: 322,171 (22) 322,193 (20) 322,213 (16) 322,229 (8) 322,237 (6) 322,243 (4) 322,247 (2) 322,249 752,207 (44) 752,251 (12) 752,263 (10) 752,273 (8) 752,281 (6) 752,287 (4) 752,291 (2) 752,293