Equal prime and composite sums: Difference between revisions
m
→{{header|EasyLang}}
(→{{header|jq}}: simplify) |
|||
| (22 intermediate revisions by 15 users not shown) | |||
Line 1:
{{
Suppose we have a sequence of prime sums, where each term '''P<sub>n</sub>''' is the sum of the first '''n''' primes.
Line 31:
=={{header|ALGOL 68}}==
{{Trans|XPL0|With a coup[le of tweaks}}
<syntaxhighlight lang="algol68">
BEGIN # find n and m where the sums of the first n primes and first m #
# composites where the sums are equal #
MODE INTEGER = LONG INT; # size of INT MODE to use #
# alternative ROOT operators for different sizes of integer #
OP ROOT = ( INT n )INT: ENTIER sqrt( n );
OP ROOT = ( LONG INT n )LONG INT: ENTIER long sqrt( n );
PROC is prime = ( INTEGER n )BOOL: # returns TRUE if n is prime #
IF n <= 2 THEN n = 2
ELIF NOT ODD n THEN FALSE
ELSE BOOL prime := TRUE;
INTEGER i := 1;
INTEGER r := ROOT n;
WHILE ( i +:= 2 ) <= r AND prime DO prime := n MOD i /= 0 OD;
prime
FI # is prime # ;
INT count := 0;
INTEGER n := 2, m := 1, sum p := 5, sum c := 4, num p := 3, num c := 4;
print( ( " sum primes composites", newline ) );
WHILE IF sum c > sum p THEN
WHILE NOT is prime( num p +:= 2 ) DO SKIP OD;
sum p +:= num p;
n +:= 1
FI;
IF sum p > sum c THEN
WHILE is prime( num c +:= 1 ) DO SKIP OD;
sum c +:= num c;
m +:= 1
FI;
IF sum p = sum c THEN
print( ( whole( sum p, -16 ), whole( n, -10 ), whole( m, -11 ), newline ) );
count +:= 1;
IF count < 8 THEN
WHILE is prime( num c +:= 1 ) DO SKIP OD;
sum c +:= num c;
m +:= 1
FI
FI;
count < 8
DO SKIP OD
END
</syntaxhighlight>
{{out}}
<pre>
sum primes composites
10 3 2
1988 33 51
14697 80 147
83292 175 361
1503397 660 1582
18859052 2143 5699
93952013 4556 12821
89171409882 118785 403341
</pre>
=={{header|BASIC}}==
==={{header|BASIC256}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="vb">#include "isprime.kbs"
i = 0
IndN = 1 : IndM = 1
NumP = 2 : NumC = 4
SumP = 2 : SumC = 4
print " sum prime sum composite sum"
while True
if SumC > SumP then
do
NumP += 1
until isPrime(NumP)
SumP += NumP
IndN += 1
end if
if SumP > SumC then
do
NumC += 1
until not isPrime(NumC)
SumC += NumC
IndM += 1
end if
if SumP = SumC then
print rjust(string(SumP),9); " - "; rjust(string(IndN),8); " - ";rjust(string(IndM),8)
i += 1
if i >= 7 then exit while #valor mayor tarda MUUCHO
do
NumC += 1
until not isPrime(NumC)
SumC += NumC
IndM += 1
end if
end while</syntaxhighlight>
==={{header|FreeBASIC}}===
{{trans|XPL0}}
<syntaxhighlight lang="vb">#include "isprime.bas"
Dim As Integer i = 0
Dim As Integer IndN = 1, IndM = 1
Dim As Integer NumP = 2, NumC = 4
Dim As Integer SumP = 2, SumC = 4
Print " sum prime sum composite sum"
Do
If SumC > SumP Then
Do
NumP += 1
Loop Until isPrime(NumP)
SumP += NumP
IndN += 1
End If
If SumP > SumC Then
Do
NumC += 1
Loop Until Not isPrime(NumC)
SumC += NumC
IndM += 1
End If
If SumP = SumC Then
Print Using "##,###,###,###,### - ##,###,### - ##,###,###"; SumP; IndN; IndM
i += 1
If i >= 9 Then Exit Do
Do
NumC += 1
Loop Until Not isPrime(NumC)
SumC += NumC
IndM += 1
End If
Loop</syntaxhighlight>
{{out}}
<pre> sum prime sum composite sum
10 - 3 - 2
1,988 - 33 - 51
14,697 - 80 - 147
83,292 - 175 - 361
1,503,397 - 660 - 1,582
18,859,052 - 2,143 - 5,699
93,952,013 - 4,556 - 12,821
89,171,409,882 - 118,785 - 403,341
9,646,383,703,961 - 1,131,142 - 4,229,425</pre>
==={{header|Gambas}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="vbnet">'Use "isprime.bas"
Public Sub Main()
Dim i As Integer = 0
Dim IndN As Integer = 1
Dim IndM As Integer = 1
Dim NumP As Integer = 2
Dim NumC As Integer = 4
Dim SumP As Long = 2
Dim SumC As Long = 4
Print " sum prime sum composite sum"
Do
If SumC > SumP Then
Do
NumP += 1
Loop Until isPrime(NumP)
SumP += NumP
IndN += 1
End If
If SumP > SumC Then
Do
NumC += 1
Loop Until Not isPrime(NumC)
SumC += NumC
IndM += 1
End If
If SumP = SumC Then
Print Format$(Str$(SumP), "##,###,###,###,###"); " - ";
Print Format$(Str$(IndN), "##,###,###"); " - ";
Print Format$(Str$(IndM), "##,###,###")
i += 1
If i >= 9 Then Break
Do
NumC += 1
Loop Until Not isPrime(NumC)
SumC += NumC
IndM += 1
End If
Loop
End</syntaxhighlight>
{{out}}
<pre>Similar to FreeBASIC entry.</pre>
==={{header|PureBasic}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="vb">;XIncludeFile "isprime.pb"
OpenConsole()
Define.d IndN, IndM, NumP, NumC, SumP, SumC
i.i = 0
IndN = 1
IndM = 1
NumP = 2
NumC = 4
SumP = 2
SumC = 4
PrintN(" sum prime sum composite sum")
While #True
If SumC > SumP:
Repeat
NumP + 1
Until isPrime(NumP)
SumP + NumP
IndN + 1
EndIf
If SumP > SumC:
Repeat
NumC + 1
Until Not isPrime(NumC)
SumC + NumC
IndM + 1
EndIf
If SumP = SumC:
PrintN(RSet(Str(SumP),14) + " - " + RSet(Str(IndN),8) + " - " + RSet(Str(IndM),8))
i + 1
If i >= 9:
Break
EndIf
Repeat
NumC + 1
Until Not isPrime(NumC)
SumC + NumC
IndM + 1
EndIf
Wend
PrintN(#CRLF$ + "Press ENTER to exit"): Input()
CloseConsole()</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
==={{header|Yabasic}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="vb">//import isprime
i = 0
IndN = 1 : IndM = 1
NumP = 2 : NumC = 4
SumP = 2 : SumC = 4
print " sum prime sum composite sum"
do
if SumC > SumP then
repeat
NumP = NumP + 1
until isPrime(NumP)
SumP = SumP + NumP
IndN = IndN + 1
fi
if SumP > SumC then
repeat
NumC = NumC + 1
until not isPrime(NumC)
SumC = SumC + NumC
IndM = IndM + 1
fi
if SumP = SumC then
print SumP using ("##,###,###,###,###"), " - ", IndN using ("##,###,###"), " - ", IndM using ("##,###,###")
i = i + 1
if i >= 9 break
repeat
NumC = NumC + 1
until not isPrime(NumC)
SumC = SumC + NumC
IndM = IndM + 1
fi
loop
print
end</syntaxhighlight>
=={{header|C++}}==
{{libheader|Primesieve}}
<syntaxhighlight lang="cpp">#include <primesieve.hpp>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <locale>
class composite_iterator {
public:
composite_iterator();
uint64_t next_composite();
private:
uint64_t composite;
uint64_t prime;
primesieve::iterator pi;
};
composite_iterator::composite_iterator() {
composite = prime = pi.next_prime();
for (; composite == prime; ++composite)
prime = pi.next_prime();
}
uint64_t composite_iterator::next_composite() {
uint64_t result = composite;
while (++composite == prime)
prime = pi.next_prime();
return result;
}
int main() {
std::cout.imbue(std::locale(""));
auto start = std::chrono::high_resolution_clock::now();
composite_iterator ci;
primesieve::iterator pi;
uint64_t prime_sum = pi.next_prime();
uint64_t composite_sum = ci.next_composite();
uint64_t prime_index = 1, composite_index = 1;
std::cout << "Sum | Prime Index | Composite Index\n";
std::cout << "------------------------------------------------------\n";
for (int count = 0; count < 11;) {
if (prime_sum == composite_sum) {
std::cout << std::right << std::setw(21) << prime_sum << " | "
<< std::setw(12) << prime_index << " | " << std::setw(15)
<< composite_index << '\n';
composite_sum += ci.next_composite();
prime_sum += pi.next_prime();
++prime_index;
++composite_index;
++count;
} else if (prime_sum < composite_sum) {
prime_sum += pi.next_prime();
++prime_index;
} else {
composite_sum += ci.next_composite();
++composite_index;
}
}
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> duration(end - start);
std::cout << "\nElapsed time: " << duration.count() << " seconds\n";
}</syntaxhighlight>
{{out}}
<pre>
Sum | Prime Index | Composite Index
------------------------------------------------------
10 | 3 | 2
1,988 | 33 | 51
14,697 | 80 | 147
83,292 | 175 | 361
1,503,397 | 660 | 1,582
18,859,052 | 2,143 | 5,699
93,952,013 | 4,556 | 12,821
89,171,409,882 | 118,785 | 403,341
9,646,383,703,961 | 1,131,142 | 4,229,425
209,456,854,921,713 | 5,012,372 | 19,786,181
3,950,430,820,867,201 | 20,840,220 | 86,192,660
Elapsed time: 0.330966 seconds
</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
Makes extensive use of the [[Extensible_prime_generator#Delphi|Delphi Prime-Generator Object]]
<syntaxhighlight lang="Delphi">
procedure PrimeCompositeSums(Memo: TMemo);
{Find places where the prime and composite sums match}
var Sieve: TPrimeSieve;
var I,P,C,Count: integer;
var CSumArray,PSumArray: TInt64DynArray;
var CSum,PSum: int64;
var S: string;
begin
Sieve:=TPrimeSieve.Create;
try
{Build 10 million primes}
Sieve.Intialize(10000000);
{Build arrays of Prime and Composite sums}
SetLength(CSumArray,0);
SetLength(PSumArray,0);
CSum:=0; PSum:=0;
for I:=2 to Sieve.Count-1 do
if Sieve.Flags[I] then
begin
PSum:=PSum+I;
SetLength(PSumArray,Length(PSumArray)+1);
PSumArray[High(PSumArray)]:=PSum;
end
else
begin
CSum:=CSum+I;
SetLength(CSumArray,Length(CSumArray)+1);
CSumArray[High(CSumArray)]:=CSum;
end;
Memo.Lines.Add('Sum | Prime Index | Composite Index');
Memo.Lines.Add('------------------------------------------------------');
P:=0;C:=0;
Count:=0;
{Traverse the prime and composite sum looking for places they match}
while true do
begin
if PSumArray[P]=CSumArray[C] then
begin
Inc(Count);
Memo.Lines.Add(Format('%d %19.0n | %12d | %15d',[Count,PSumArray[P]+0.0,P+1,C+1]));
if Count>=8 then break;
end;
{Increment the index of array that is behind}
if PSumArray[P]<CSumArray[C] then Inc(P)
else Inc(C);
end;
finally Sieve.Free; end;
end;
</syntaxhighlight>
{{out}}
<pre>
Sum | Prime Index | Composite Index
------------------------------------------------------
1 10 | 3 | 2
2 1,988 | 33 | 51
3 14,697 | 80 | 147
4 83,292 | 175 | 361
5 1,503,397 | 660 | 1582
6 18,859,052 | 2143 | 5699
7 93,952,013 | 4556 | 12821
8 89,171,409,882 | 118785 | 403341
Elapsed Time: 761.859 ms.
</pre>
=={{header|EasyLang}}==
{{trans|FreeBASIC}}
<syntaxhighlight>
fastfunc isprim num .
if num mod 2 = 0 and num > 2
return 0
.
i = 3
while i <= sqrt num
if num mod i = 0
return 0
.
i += 2
.
return 1
.
indN = 1 ; indM = 2
numP = 2 ; numC = 4
sumP = 2 ; sumC = 4
#
numfmt 0 11
print " sum primes composites"
repeat
if sumC > sumP
repeat
numP += 1
until isprim numP = 1
.
sumP += numP
indN += 1
.
if sumP > sumC
repeat
numC += 1
until isprim numC = 0
.
sumC += numC
indM += 1
.
if sumP = sumC
print sumP & indN & indM
cnt += 1
if cnt < 8
repeat
numC += 1
until isprim numC = 0
.
sumC += numC
indM += 1
.
.
until cnt >= 8
.
</syntaxhighlight>
=={{header|F_Sharp|F#}}==
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)]
<
// Equal prime and composite sums. Nigel Galloway: March 3rd., 2022
let fN(g:seq<int64>)=let g=(g|>Seq.scan(fun(_,n,i) g->(g,n+g,i+1))(0,0L,0)|>Seq.skip 1).GetEnumerator() in (fun()->g.MoveNext()|>ignore; g.Current)
let fG n g=let rec fG a b=seq{match a,b with ((_,p,_),(_,c,_)) when p<c->yield! fG(n()) b |((_,p,_),(_,c,_)) when p>c->yield! fG a (g()) |_->yield(a,b); yield! fG(n())(g())} in fG(n())(g())
fG(fN(primes64()))(fN(primes64()|>Seq.pairwise|>Seq.collect(fun(n,g)->[1L+n..g-1L])))|>Seq.take 11|>Seq.iter(fun((n,i,g),(e,_,l))->printfn $"Primes up to %d{n} at position %d{g} and composites up to %d{e} at position %d{l} sum to %d{i}.")
</syntaxhighlight>
{{out}}
<pre>
Line 54 ⟶ 548:
Primes up to 390180569 at position 20840220 and composites up to 91491160 at position 86192660 sum to 3950430820867201.
</pre>
=={{header|Go}}==
{{trans|Wren}}
{{libheader|Go-rcu}}
<syntaxhighlight lang="go">package main
import (
"fmt"
"log"
"rcu"
"sort"
)
func ord(n int) string {
if n < 0 {
log.Fatal("Argument must be a non-negative integer.")
}
m := n % 100
if m >= 4 && m <= 20 {
return fmt.Sprintf("%sth", rcu.Commatize(n))
}
m %= 10
suffix := "th"
if m == 1 {
suffix = "st"
} else if m == 2 {
suffix = "nd"
} else if m == 3 {
suffix = "rd"
}
return fmt.Sprintf("%s%s", rcu.Commatize(n), suffix)
}
func main() {
limit := int(4 * 1e8)
c := rcu.PrimeSieve(limit-1, true)
var compSums []int
var primeSums []int
csum := 0
psum := 0
for i := 2; i < limit; i++ {
if c[i] {
csum += i
compSums = append(compSums, csum)
} else {
psum += i
primeSums = append(primeSums, psum)
}
}
for i := 0; i < len(primeSums); i++ {
ix := sort.SearchInts(compSums, primeSums[i])
if ix < len(compSums) && compSums[ix] == primeSums[i] {
cps := rcu.Commatize(primeSums[i])
fmt.Printf("%21s - %12s prime sum, %12s composite sum\n", cps, ord(i+1), ord(ix+1))
}
}
}</syntaxhighlight>
{{out}}
<pre>
10 - 3rd prime sum, 2nd composite sum
1,988 - 33rd prime sum, 51st composite sum
14,697 - 80th prime sum, 147th composite sum
83,292 - 175th prime sum, 361st composite sum
1,503,397 - 660th prime sum, 1,582nd composite sum
18,859,052 - 2,143rd prime sum, 5,699th composite sum
93,952,013 - 4,556th prime sum, 12,821st composite sum
89,171,409,882 - 118,785th prime sum, 403,341st composite sum
9,646,383,703,961 - 1,131,142nd prime sum, 4,229,425th composite sum
209,456,854,921,713 - 5,012,372nd prime sum, 19,786,181st composite sum
3,950,430,820,867,201 - 20,840,220th prime sum, 86,192,660th composite sum
</pre>
=={{header|J}}==
Brute force seems fast enough for this task
<syntaxhighlight lang="j">Pn=: +/\ pn=: p: i.1e6 NB. first million primes pn and their running sum Pn
Cn=: +/\(4+i.{:pn)-.pn NB. running sum of composites starting at 4 and excluding those primes
both=: Pn(e.#[)Cn NB. numbers in both sequences
both,.(Pn i.both),.Cn i.both NB. values, Pn index m, Cn index n
10 2 1
1988 32 50
14697 79 146
83292 174 360
1503397 659 1581
18859052 2142 5698
93952013 4555 12820
89171409882 118784 403340</syntaxhighlight>
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.BitSet;
import java.util.Objects;
public final class EqualPrimeAndCompositeSums {
public static void main(String[] aArgs) {
PrimeIterator primeIterator = new PrimeIterator();
CompositeIterator compositeIterator = new CompositeIterator();
long primeSum = primeIterator.next();
long compositeSum = compositeIterator.next();
int primeIndex = 1;
int compositeIndex = 1;
System.out.println("Sum | Prime Index | Composite Index");
System.out.println("----------------------------------------------");
int count = 0;
while ( count < 8 ) {
if ( primeSum == compositeSum ) {
System.out.println(String.format("%13d%s%12d%s%15d",
primeSum, " | ", primeIndex, " | ", compositeIndex));
primeSum += primeIterator.next();
primeIndex += 1;
compositeSum += compositeIterator.next();
compositeIndex += 1;
count += 1;
} else if ( primeSum < compositeSum ) {
primeSum += primeIterator.next();
primeIndex += 1;
} else {
compositeSum += compositeIterator.next();
compositeIndex += 1;
}
}
}
private static class CompositeIterator {
public CompositeIterator() {
primeIterator = new PrimeIterator();
prime = primeIterator.next();
composite = prime;
while ( composite == prime ) {
prime = primeIterator.next();
composite += 1;
}
}
public int next() {
final int result = composite;
while ( ++composite == prime ) {
prime = primeIterator.next();
}
return result;
}
public int prime, composite;
private PrimeIterator primeIterator;
}
private static class PrimeIterator {
public PrimeIterator() {
if ( Objects.isNull(sieve) ) {
listPrimeNumbers(10_000_000);
}
}
public int next() {
if ( lastPrime < sieve.cardinality() ) {
lastPrime = sieve.nextSetBit(lastPrime + 1);
} else {
do {
lastPrime += 2;
}
while ( ! isPrime(lastPrime) );
}
return lastPrime;
}
private static boolean isPrime(int aCandidate) {
for ( int i = 2; i <= Math.sqrt(aCandidate); i = sieve.nextSetBit(i + 1) ) {
if ( aCandidate % i == 0 ) {
return false;
}
}
return true;
}
private static void listPrimeNumbers(int aN) {
sieve = new BitSet(aN + 1);
sieve.set(2, aN + 1);
for ( int i = 2; i <= Math.sqrt(aN); i = sieve.nextSetBit(i + 1) ) {
for ( int j = i * i; j <= aN; j = j + i ) {
sieve.clear(j);
}
}
}
private int lastPrime;
private static BitSet sieve;
}
}
</syntaxhighlight>
{{ out }}
<pre>
Sum | Prime Index | Composite Index
----------------------------------------------
10 | 3 | 2
1988 | 33 | 51
14697 | 80 | 147
83292 | 175 | 361
1503397 | 660 | 1582
18859052 | 2143 | 5699
93952013 | 4556 | 12821
89171409882 | 118785 | 403341
</pre>
=={{header|jq}}==
{{works with|jq}}
Line 62 ⟶ 771:
The program given in this entry requires foreknowledge of the appropriate size of the (virtual) Eratosthenes sieve.
<
def task($sievesize):
Line 83 ⟶ 792:
;
task(1E5)</
{{out}}
<pre>
Line 96 ⟶ 805:
=={{header|Julia}}==
<
function getsequencematches(N, masksize = 1_000_000_000)
Line 123 ⟶ 832:
@time getsequencematches(11)
</
<pre>
Primes up to 5 at position 3 and composites up to 6 at position 2 sum to 10.
Line 137 ⟶ 846:
Primes up to 390180569 at position 20840220 and composites up to 91491160 at position 86192660 sum to 3950430820867201.
44.526876 seconds (1.09 G allocations: 16.546 GiB, 3.13% gc time)
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">$HistoryLength = 1;
ub = 10^8;
ps = Prime[Range[PrimePi[ub]]];
cs = Complement[Range[2, ub], ps];
cps = Accumulate[ps];
ccs = Accumulate[cs];
indices = Intersection[cps, ccs];
poss = {FirstPosition[cps, #], FirstPosition[ccs, #]} & /@ indices;
TableForm[MapThread[Prepend, {Flatten /@ poss, indices}],
TableHeadings -> {None, {"Sum", "Prime Index", "Composite Index"}},
TableAlignments -> Right]</syntaxhighlight>
{{out}}
<pre>Sum Prime Index Composite Index
10 3 2
1988 33 51
14697 80 147
83292 175 361
1503397 660 1582
18859052 2143 5699
93952013 4556 12821
89171409882 118785 403341
9646383703961 1131142 4229425
209456854921713 5012372 19786181</pre>
=={{header|Lua}}==
{{Trans|XPL0|with a couple of tweaks}}
<syntaxhighlight lang="lua">
do --[[ find n and m where the sums of the first n primes and first m
composites where the sums are equal
--]]
local function isPrime( n ) -- returns TRUE if n is prime
if n <= 2 then return n == 2
elseif n % 2 == 0 then return false
else local prime, i, r = true, 1, math.floor( math.sqrt( n ) )
repeat
i = i + 2
if i <= r then
prime = n % i ~= 0
end
until i > r or not prime
return prime
end
end
local count, n, m, sumP, sumC, numP, numC = 0, 2, 1, 5, 4, 3, 4
io.write( " sum primes composites\n" )
repeat
if sumC > sumP then
repeat numP = numP + 2 until isPrime( numP )
sumP = sumP + numP
n = n + 1
end
if sumP > sumC then
repeat numC = numC + 1 until not isPrime( numC )
sumC = sumC + numC
m = m + 1
end
if sumP == sumC then
io.write( string.format( "%14d", sumP ), string.format( "%10d", n ), string.format( "%11d", m ), "\n" )
count = count + 1;
if count < 8 then
repeat numC = numC + 1 until not isPrime( numC )
sumC = sumC + numC
m = m + 1
end
end
until count >= 8
end
</syntaxhighlight>
{{out}}
<pre>
sum primes composites
10 3 2
1988 33 51
14697 80 147
83292 175 361
1503397 660 1582
18859052 2143 5699
93952013 4556 12821
89171409882 118785 403341
</pre>
=={{header|Nim}}==
We use a sieve of Erathostenes for odd integers, each boolean being represented as a single bit.
<syntaxhighlight lang="Nim">import std/[bitops, math, monotimes, strformat, strutils, times]
type Sieve = object
data: seq[byte]
proc `[]`(sieve: Sieve; idx: Positive): bool =
## Return the sieve element at index "idx".
let idx = idx shr 1
let iByte = idx shr 3
let iBit = idx and 7
result = sieve.data[iByte].testBit(iBit)
proc `[]=`(sieve: var Sieve; idx: Positive; val: bool) =
## Set the sieve element at index "idx" with value "val".
let idx = idx shr 1
let iByte = idx shr 3
let iBit = idx and 7
if val: sieve.data[iByte].setBit(iBit)
else: sieve.data[iByte].clearBit(iBit)
proc newSieve(lim: Positive): Sieve =
## Create a sieve with maximum index "lim".
result.data = newSeq[byte]((lim + 16) shr 4)
const Limit = 400_000_000
let t0 = getMonoTime()
# Fill the sieve.
var composite = newSieve(Limit)
for n in countup(3, sqrt(Limit.toFloat).int, 2):
if not composite[n]:
for k in countup(n * n, Limit - 1, 2 * n):
composite[k] = true
proc isPrime(n: Positive): bool =
## Return true is "n" is prime.
assert n >= 2
if (n and 1) == 0: return n == 2
result = not composite[n]
proc updatePrime(np, ip, psum: var int) =
## Find the next prime number and update "np", "ip" and "psum".
inc np, 1
while np <= Limit and not np.isPrime:
inc np
inc ip
inc psum, np
proc updateComposite(nc, ic, csum: var int) =
## Find the next composite number and update "nc", "ic" and "csum".
inc nc, 1
while nc <= Limit and nc.isPrime:
inc nc
inc ic
inc csum, nc
echo " Sum | Prime Index | Composite Index "
echo "──────────────────────────────────────────────────────────"
var np = 2 # Current prime.
var nc = 4 # Current composite.
var ip, ic = 1 # Ranks of current prime and composite.
var psum = np # Current sum of prime numbers.
var csum = nc # Current sum of composite numbers.
while true:
if psum == csum:
echo &"{insertSep($psum):>21} | {insertSep($ip):>15} | {insertSep($ic):>15}"
updatePrime(np, ip, psum)
updateComposite(nc, ic, csum)
elif psum < csum:
updatePrime(np, ip, psum)
else:
updateComposite(nc, ic, csum)
if np > Limit or nc > Limit:
break
echo()
let dt = toParts(getMonoTime() - t0)
echo &"Elapsed time: {dt[Seconds]}.{dt[Milliseconds]} s"
</syntaxhighlight>
{{out}}
<pre> Sum | Prime Index | Composite Index
──────────────────────────────────────────────────────────
10 | 3 | 2
1_988 | 33 | 51
14_697 | 80 | 147
83_292 | 175 | 361
1_503_397 | 660 | 1_582
18_859_052 | 2_143 | 5_699
93_952_013 | 4_556 | 12_821
89_171_409_882 | 118_785 | 403_341
9_646_383_703_961 | 1_131_142 | 4_229_425
209_456_854_921_713 | 5_012_372 | 19_786_181
3_950_430_820_867_201 | 20_840_220 | 86_192_660
Elapsed time: 2.891 s
</pre>
Line 142 ⟶ 1,039:
Not especially fast, but minimal memory usage.
{{libheader|ntheory}}
<
use warnings;
use feature <say state>;
Line 170 ⟶ 1,067:
$ci++;
redo
}</
{{out}}
<pre> 10 - 3rd prime sum, 2nd composite sum
Line 184 ⟶ 1,081:
=={{header|Phix}}==
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
Line 192 ⟶ 1,089:
<span style="color: #000000;">csn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nci</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nc</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ncp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">
<span style="color: #004080;">integer</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">compare</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ps</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cs</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- {-1,0,+1}</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%,21d - %,10d%s prime sum, %,10d%s composite sum (%s)\n"</span><span style="color: #0000FF;">,</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">ps</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">psn</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">ord</span><span style="color: #0000FF;">(</span><span style="color: #000000;">psn</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">csn</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">ord</span><span style="color: #0000FF;">(</span><span style="color: #000000;">csn</span><span style="color: #0000FF;">),</span> <span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)})</span>
<span style="color: #000000;">found</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span>
<span style="color: #000000;">psn</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> <span style="color: #000080;font-style:italic;">-- prime sum number</span>
<span style="color: #000000;">npi</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> <span style="color: #000080;font-style:italic;">-- next prime index</span>
<span style="color: #000000;">ps</span> <span style="color: #0000FF;">+=</span> <span style="color: #7060A8;">get_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">npi</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span>
<span style="color: #000000;">csn</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> <span style="color: #000080;font-style:italic;">-- composite sum number</span>
<span style="color: #000000;">nc</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> <span style="color: #000080;font-style:italic;">-- next composite?</span>
Line 219 ⟶ 1,113:
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<!--</
{{out}}
<pre>
Line 229 ⟶ 1,123:
18,859,052 - 2,143rd prime sum, 5,699th composite sum (0.2s)
93,952,013 - 4,556th prime sum, 12,821st composite sum (0.2s)
89,171,409,882 - 118,785th prime sum, 403,341st composite sum (0.
9,646,383,703,961 - 1,131,142nd prime sum, 4,229,425th composite sum (1.
209,456,854,921,713 - 5,012,372nd prime sum, 19,786,181st composite sum (
3,950,430,820,867,201 - 20,840,220th prime sum, 86,192,660th composite sum (
</pre>
The next value in the series is beyond an 80 bit float, and I suspect this is one of those sort of tasks where gmp, or perhaps I should rather say over a billion invocations of the Phix interface to it, might not shine quite so brightly.
=={{header|Python}}==
<syntaxhighlight lang="python3">
# equal_prime_comp_sums.py by Xing216
import math
import numpy
def prime_composites(upto=50000):
nums = numpy.arange(2,upto+1)
primes=numpy.arange(3,upto+1,2)
isprime=numpy.ones((upto-1)//2,dtype=bool)
for factor in primes[:int(math.sqrt(upto))//2]:
if isprime[(factor-2)//2]: isprime[(factor*3-2)//2::factor]=0
primes = numpy.insert(primes[isprime],0,2)
intersect = nums[numpy.in1d(nums, primes)]
mask1 = numpy.searchsorted(nums,intersect)
composites = numpy.delete(nums,mask1)
return primes, composites
primes, composites = prime_composites()
cum_primes = numpy.cumsum(primes)
cum_composites = numpy.cumsum(composites)
print("Sum | Prime Index | Composite Index")
print("------------------------------------------")
for idx, num in enumerate(cum_primes):
if num in cum_composites:
print(f"{num:10,} | {idx+1:11,} | {numpy.where(cum_composites == num)[0][0]+1:15,}")
</syntaxhighlight>
{{out}}
<pre>
Sum | Prime Index | Composite Index
------------------------------------------
10 | 3 | 2
1,988 | 33 | 51
14,697 | 80 | 147
83,292 | 175 | 361
1,503,397 | 660 | 1,582
18,859,052 | 2,143 | 5,699
93,952,013 | 4,556 | 12,821
</pre>
=={{header|Quackery}}==
<code>isprime</code> is defined at [[Primality by trial division#Quackery]].
<syntaxhighlight lang="Quackery"> [ swap number$
tuck size -
space swap of
swap join echo$ ] is r-echo ( n n --> $ )
[ stack ] is primecount ( --> s )
[ stack ] is recentprime ( --> s )
[ stack ] is primesum ( --> s )
[ stack ] is compcount ( --> s )
[ stack ] is recentcomp ( --> s )
[ stack ] is compsum ( --> s )
[ recentprime take
[ 1+ dup isprime iff
[ 1 primecount tally
dup recentprime put
primesum tally ]
done
again ] ] is nextprime ( --> )
[ recentcomp take
[ 1+ dup isprime not iff
[ 1 compcount tally
dup recentcomp put
compsum tally ]
done
again ] ] is nextcomp ( --> )
1 primecount put
2 recentprime put
2 primesum put
1 compcount put
4 recentcomp put
4 compsum put
[]
[ primesum share
compsum share
2dup > iff
[ 2drop nextcomp ]
again
< iff nextprime again
compsum share
primecount share
compcount share
join join nested join
dup size 7 < while
nextcomp
nextprime
again ]
primecount release
recentprime release
primesum release
compcount release
recentcomp release
compsum release
say " sum prime composite" cr
witheach
[ witheach
[ 11 r-echo ]
cr ]</syntaxhighlight>
{{out}}
<pre> sum prime composite
10 3 2
1988 33 51
14697 80 147
83292 175 361
1503397 660 1582
18859052 2143 5699
93952013 4556 12821</pre>
=={{header|Raku}}==
Let it run until I got bored and killed it. Time is total accumulated seconds since program start.
<syntaxhighlight lang="raku"
my $prime-sum = [\+] (2..*).grep: *.is-prime;
Line 253 ⟶ 1,261:
++$c-index;
redo;
};</
{{out}}
<pre> 10 - 3ʳᵈ prime sum, 2ⁿᵈ composite sum 0.01 seconds
Line 266 ⟶ 1,274:
209,456,854,921,713 - 5,012,372ⁿᵈ prime sum, 19,786,181ˢᵗ composite sum 968.26 seconds
^C</pre>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">func f(n) {
var (
p = 2, sp = p,
c = 4, sc = c,
)
var res = []
while (res.len < n) {
if (sc == sp) {
res << [sp, c.composite_count, p.prime_count]
sc += c.next_composite!
}
while (sp < sc) {
sp += p.next_prime!
}
while (sc < sp) {
sc += c.next_composite!
}
}
return res
}
f(8).each_2d {|n, ci, pi|
printf("%12s = %-9s = %s\n", n, "P(#{pi})", "C(#{ci})")
}</syntaxhighlight>
{{out}}
<pre>
10 = P(3) = C(2)
1988 = P(33) = C(51)
14697 = P(80) = C(147)
83292 = P(175) = C(361)
1503397 = P(660) = C(1582)
18859052 = P(2143) = C(5699)
93952013 = P(4556) = C(12821)
89171409882 = P(118785) = C(403341)
</pre>
(takes ~6 seconds)
=={{header|Wren}}==
Takes around 2 minutes, which is respectable for Wren, but uses a lot of memory.
<
import "./sort" for Find
import "./fmt" for Fmt
var limit = 4 * 1e8
Line 294 ⟶ 1,345:
Fmt.print("$,21d - $,12r prime sum, $,12r composite sum", primeSums[i], i+1, ix+1)
}
}</
{{out}}
Line 312 ⟶ 1,363:
=={{header|XPL0}}==
<
int N, I;
[if N <= 2 then return N = 2;
Line 352 ⟶ 1,403:
];
];
]</
{{out}}
| |||