Equal prime and composite sums: Difference between revisions
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 34: | Line 34: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
{{libheader|Primesieve}} |
{{libheader|Primesieve}} |
||
< |
<syntaxhighlight lang="cpp">#include <primesieve.hpp> |
||
#include <chrono> |
#include <chrono> |
||
Line 96: | Line 96: | ||
std::chrono::duration<double> duration(end - start); |
std::chrono::duration<double> duration(end - start); |
||
std::cout << "\nElapsed time: " << duration.count() << " seconds\n"; |
std::cout << "\nElapsed time: " << duration.count() << " seconds\n"; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 119: | Line 119: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)] |
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)] |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// Equal prime and composite sums. Nigel Galloway: March 3rd., 2022 |
// 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 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()) |
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}.") |
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> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 143: | Line 143: | ||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
{{trans|XPL0}} |
{{trans|XPL0}} |
||
< |
<syntaxhighlight lang="freebasic">#include "isprime.bas" |
||
Dim As Integer i = 0 |
Dim As Integer i = 0 |
||
Line 175: | Line 175: | ||
IndM += 1 |
IndM += 1 |
||
End If |
End If |
||
Loop</ |
Loop</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> sum prime sum composite sum |
<pre> sum prime sum composite sum |
||
Line 191: | Line 191: | ||
{{trans|Wren}} |
{{trans|Wren}} |
||
{{libheader|Go-rcu}} |
{{libheader|Go-rcu}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 244: | Line 244: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 264: | Line 264: | ||
Brute force seems fast enough for this task |
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 |
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(e.#[)Cn NB. numbers in both sequences |
||
Line 276: | Line 276: | ||
18859052 2142 5698 |
18859052 2142 5698 |
||
93952013 4555 12820 |
93952013 4555 12820 |
||
89171409882 118784 403340</ |
89171409882 118784 403340</syntaxhighlight> |
||
=={{header|jq}}== |
=={{header|jq}}== |
||
Line 286: | Line 286: | ||
The program given in this entry requires foreknowledge of the appropriate size of the (virtual) Eratosthenes sieve. |
The program given in this entry requires foreknowledge of the appropriate size of the (virtual) Eratosthenes sieve. |
||
< |
<syntaxhighlight lang="jq">def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] +.; |
||
def task($sievesize): |
def task($sievesize): |
||
Line 307: | Line 307: | ||
; |
; |
||
task(1E5)</ |
task(1E5)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 320: | Line 320: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">using Primes |
||
function getsequencematches(N, masksize = 1_000_000_000) |
function getsequencematches(N, masksize = 1_000_000_000) |
||
Line 347: | Line 347: | ||
@time getsequencematches(11) |
@time getsequencematches(11) |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
Primes up to 5 at position 3 and composites up to 6 at position 2 sum to 10. |
Primes up to 5 at position 3 and composites up to 6 at position 2 sum to 10. |
||
Line 364: | Line 364: | ||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">$HistoryLength = 1; |
||
ub = 10^8; |
ub = 10^8; |
||
ps = Prime[Range[PrimePi[ub]]]; |
ps = Prime[Range[PrimePi[ub]]]; |
||
Line 374: | Line 374: | ||
TableForm[MapThread[Prepend, {Flatten /@ poss, indices}], |
TableForm[MapThread[Prepend, {Flatten /@ poss, indices}], |
||
TableHeadings -> {None, {"Sum", "Prime Index", "Composite Index"}}, |
TableHeadings -> {None, {"Sum", "Prime Index", "Composite Index"}}, |
||
TableAlignments -> Right]</ |
TableAlignments -> Right]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Sum Prime Index Composite Index |
<pre>Sum Prime Index Composite Index |
||
Line 391: | Line 391: | ||
Not especially fast, but minimal memory usage. |
Not especially fast, but minimal memory usage. |
||
{{libheader|ntheory}} |
{{libheader|ntheory}} |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
use feature <say state>; |
use feature <say state>; |
||
Line 419: | Line 419: | ||
$ci++; |
$ci++; |
||
redo |
redo |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 10 - 3rd prime sum, 2nd composite sum |
<pre> 10 - 3rd prime sum, 2nd composite sum |
||
Line 433: | Line 433: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<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> |
<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 465: | Line 465: | ||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 484: | Line 484: | ||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
Let it run until I got bored and killed it. Time is total accumulated seconds since program start. |
Let it run until I got bored and killed it. Time is total accumulated seconds since program start. |
||
<lang |
<syntaxhighlight lang="raku" line>use Lingua::EN::Numbers:ver<2.8.2+>; |
||
my $prime-sum = [\+] (2..*).grep: *.is-prime; |
my $prime-sum = [\+] (2..*).grep: *.is-prime; |
||
Line 499: | Line 499: | ||
++$c-index; |
++$c-index; |
||
redo; |
redo; |
||
};</ |
};</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 10 - 3ʳᵈ prime sum, 2ⁿᵈ composite sum 0.01 seconds |
<pre> 10 - 3ʳᵈ prime sum, 2ⁿᵈ composite sum 0.01 seconds |
||
Line 514: | Line 514: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">func f(n) { |
||
var ( |
var ( |
||
Line 541: | Line 541: | ||
f(8).each_2d {|n, ci, pi| |
f(8).each_2d {|n, ci, pi| |
||
printf("%12s = %-9s = %s\n", n, "P(#{pi})", "C(#{ci})") |
printf("%12s = %-9s = %s\n", n, "P(#{pi})", "C(#{ci})") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 558: | Line 558: | ||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
Takes around 2 minutes, which is respectable for Wren, but uses a lot of memory. |
Takes around 2 minutes, which is respectable for Wren, but uses a lot of memory. |
||
< |
<syntaxhighlight lang="ecmascript">import "./math" for Int |
||
import "./sort" for Find |
import "./sort" for Find |
||
import "/fmt" for Fmt |
import "/fmt" for Fmt |
||
Line 583: | Line 583: | ||
Fmt.print("$,21d - $,12r prime sum, $,12r composite sum", primeSums[i], i+1, ix+1) |
Fmt.print("$,21d - $,12r prime sum, $,12r composite sum", primeSums[i], i+1, ix+1) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 601: | Line 601: | ||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
< |
<syntaxhighlight lang="xpl0">func IsPrime(N); \Return 'true' if N is prime |
||
int N, I; |
int N, I; |
||
[if N <= 2 then return N = 2; |
[if N <= 2 then return N = 2; |
||
Line 641: | Line 641: | ||
]; |
]; |
||
]; |
]; |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
Revision as of 10:24, 27 August 2022
You are encouraged to solve this task according to the task description, using any language you may know.
Suppose we have a sequence of prime sums, where each term Pn is the sum of the first n primes.
P = (2), (2 + 3), (2 + 3 + 5), (2 + 3 + 5 + 7), (2 + 3 + 5 + 7 + 11), ...
P = 2, 5, 10, 17, 28, etc.
Further; suppose we have a sequence of composite sums, where each term Cm is the sum of the first m composites.
C = (4), (4 + 6), (4 + 6 + 8), (4 + 6 + 8 + 9), (4 + 6 + 8 + 9 + 10), ...
C = 4, 10, 18, 27, 37, etc.
Notice that the third term of P; P3 (10) is equal to the second term of C; C2 (10);
- Task
- Find and display the indices (n, m) and value of at least the first 6 terms of the sequence of numbers that are both the sum of the first n primes and the first m composites.
- See also
C++
#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";
}
- Output:
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
F#
This task uses 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}.")
- Output:
Primes up to 5 at position 3 and composites up to 6 at position 2 sum to 10. Primes up to 137 at position 33 and composites up to 72 at position 51 sum to 1988. Primes up to 409 at position 80 and composites up to 190 at position 147 sum to 14697. Primes up to 1039 at position 175 and composites up to 448 at position 361 sum to 83292. Primes up to 4937 at position 660 and composites up to 1868 at position 1582 sum to 1503397. Primes up to 18787 at position 2143 and composites up to 6544 at position 5699 sum to 18859052. Primes up to 43753 at position 4556 and composites up to 14522 at position 12821 sum to 93952013. Primes up to 1565929 at position 118785 and composites up to 440305 at position 403341 sum to 89171409882. Primes up to 17662763 at position 1131142 and composites up to 4548502 at position 4229425 sum to 9646383703961. Primes up to 86254457 at position 5012372 and composites up to 21123471 at position 19786181 sum to 209456854921713. Primes up to 390180569 at position 20840220 and composites up to 91491160 at position 86192660 sum to 3950430820867201.
FreeBASIC
#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
- Output:
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
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))
}
}
}
- Output:
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
J
Brute force seems fast enough for this task
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
jq
Works with gojq, the Go implementation of jq
See Erdős-primes#jq for a suitable definition of `is_prime` as used here.
The program given in this entry requires foreknowledge of the appropriate size of the (virtual) Eratosthenes sieve.
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] +.;
def task($sievesize):
{compSums:[],
primeSums:[],
csum:0,
psum:0 }
| reduce range(2; $sievesize) as $i (.;
if $i|is_prime
then .psum += $i
| .primeSums += [.psum]
else .csum += $i
| .compSums += [ .csum ]
end)
| range(0; .primeSums|length) as $i
| .primeSums[$i] as $ps
| (.compSums | index( $ps )) as $ix
| select($ix >= 0)
| "\($ps|lpad(21)) - \($i+1|lpad(21)) prime sum, \($ix+1|lpad(12)) composite sum"
;
task(1E5)
- Output:
10 - 3 prime sum, 2 composite sum 1988 - 33 prime sum, 51 composite sum 14697 - 80 prime sum, 147 composite sum 83292 - 175 prime sum, 361 composite sum 1503397 - 660 prime sum, 1582 composite sum 18859052 - 2143 prime sum, 5699 composite sum 93952013 - 4556 prime sum, 12821 composite sum
Julia
using Primes
function getsequencematches(N, masksize = 1_000_000_000)
pmask = primesmask(masksize)
found, psum, csum, pindex, cindex, pcount, ccount = 0, 2, 4, 2, 4, 1, 1
incrementpsum() = (pindex += 1; if pmask[pindex] psum += pindex; pcount += 1 end)
incrementcsum() = (cindex += 1; if !pmask[cindex] csum += cindex; ccount += 1 end)
while found < N
while psum < csum
pindex >= masksize && return
incrementpsum()
end
if psum == csum
println("Primes up to $pindex at position $pcount and composites up to $cindex at position $ccount sum to $psum.")
found += 1
while psum == csum
incrementpsum()
incrementcsum()
end
end
while csum < psum
incrementcsum()
end
end
end
@time getsequencematches(11)
- Output:
Primes up to 5 at position 3 and composites up to 6 at position 2 sum to 10. Primes up to 137 at position 33 and composites up to 72 at position 51 sum to 1988. Primes up to 409 at position 80 and composites up to 190 at position 147 sum to 14697. Primes up to 1039 at position 175 and composites up to 448 at position 361 sum to 83292. Primes up to 4937 at position 660 and composites up to 1868 at position 1582 sum to 1503397. Primes up to 18787 at position 2143 and composites up to 6544 at position 5699 sum to 18859052. Primes up to 43753 at position 4556 and composites up to 14522 at position 12821 sum to 93952013. Primes up to 1565929 at position 118785 and composites up to 440305 at position 403341 sum to 89171409882. Primes up to 17662763 at position 1131142 and composites up to 4548502 at position 4229425 sum to 9646383703961. Primes up to 86254457 at position 5012372 and composites up to 21123471 at position 19786181 sum to 209456854921713. 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)
Mathematica/Wolfram Language
$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]
- Output:
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
Perl
Not especially fast, but minimal memory usage.
use strict;
use warnings;
use feature <say state>;
use ntheory <is_prime next_prime>;
sub comma { reverse ((reverse shift) =~ s/(.{3})/$1,/gr) =~ s/^,//r }
sub suffix { my($d) = $_[0] =~ /(.)$/; $d == 1 ? 'st' : $d == 2 ? 'nd' : $d == 3 ? 'rd' : 'th' }
sub prime_sum {
state $s = state $p = 2; state $i = 1;
if ($i < (my $n = shift) ) { do { $s += $p = next_prime($p) } until ++$i == $n }
$s
}
sub composite_sum {
state $s = state $c = 4; state $i = 1;
if ($i < (my $n = shift) ) { do { 1 until ! is_prime(++$c); $s += $c } until ++$i == $n }
$s
}
my $ci++;
for my $pi (1 .. 5_012_372) {
next if prime_sum($pi) < composite_sum($ci);
printf( "%20s - %11s prime sum, %12s composite sum\n",
comma(prime_sum $pi), comma($pi).suffix($pi), comma($ci).suffix($ci))
and next if prime_sum($pi) == composite_sum($ci);
$ci++;
redo
}
- Output:
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
Phix
with javascript_semantics atom t0 = time() atom ps = 2, -- current prime sum cs = 4 -- current composite sum integer psn = 1, npi = 1, -- (see below) csn = 1, nci = 3, nc = 4, ncp = 5, found = 0 constant limit = iff(platform()=JS?10:11) while found<limit do integer c = compare(ps,cs) -- {-1,0,+1} if c=0 then printf(1,"%,21d - %,10d%s prime sum, %,10d%s composite sum (%s)\n", {ps, psn, ord(psn), csn, ord(csn), elapsed(time()-t0)}) found += 1 end if if c<=0 then psn += 1 -- prime sum number npi += 1 -- next prime index ps += get_prime(npi) end if if c>=0 then csn += 1 -- composite sum number nc += 1 -- next composite? if nc=ncp then -- "", erm no nci += 1 -- next prime index ncp = get_prime(nci) nc += 1 -- next composite (even!) end if cs += nc end if end while
- Output:
10 - 3rd prime sum, 2nd composite sum (0s) 1,988 - 33rd prime sum, 51st composite sum (0.2s) 14,697 - 80th prime sum, 147th composite sum (0.2s) 83,292 - 175th prime sum, 361st composite sum (0.2s) 1,503,397 - 660th prime sum, 1,582nd composite sum (0.2s) 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.3s) 9,646,383,703,961 - 1,131,142nd prime sum, 4,229,425th composite sum (1.3s) 209,456,854,921,713 - 5,012,372nd prime sum, 19,786,181st composite sum (5.2s) 3,950,430,820,867,201 - 20,840,220th prime sum, 86,192,660th composite sum (22.4s)
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.
Raku
Let it run until I got bored and killed it. Time is total accumulated seconds since program start.
use Lingua::EN::Numbers:ver<2.8.2+>;
my $prime-sum = [\+] (2..*).grep: *.is-prime;
my $composite-sum = [\+] (2..*).grep: !*.is-prime;
my $c-index = 0;
for ^∞ -> $p-index {
next if $prime-sum[$p-index] < $composite-sum[$c-index];
printf( "%20s - %11s prime sum, %12s composite sum %5.2f seconds\n",
$prime-sum[$p-index].&comma, ordinal-digit($p-index + 1, :u, :c),
ordinal-digit($c-index + 1, :u, :c), now - INIT now )
and next if $prime-sum[$p-index] == $composite-sum[$c-index];
++$c-index;
redo;
};
- Output:
10 - 3ʳᵈ prime sum, 2ⁿᵈ composite sum 0.01 seconds 1,988 - 33ʳᵈ prime sum, 51ˢᵗ composite sum 0.01 seconds 14,697 - 80ᵗʰ prime sum, 147ᵗʰ composite sum 0.02 seconds 83,292 - 175ᵗʰ prime sum, 361ˢᵗ composite sum 0.03 seconds 1,503,397 - 660ᵗʰ prime sum, 1,582ⁿᵈ composite sum 0.04 seconds 18,859,052 - 2,143ʳᵈ prime sum, 5,699ᵗʰ composite sum 0.08 seconds 93,952,013 - 4,556ᵗʰ prime sum, 12,821ˢᵗ composite sum 0.14 seconds 89,171,409,882 - 118,785ᵗʰ prime sum, 403,341ˢᵗ composite sum 4.23 seconds 9,646,383,703,961 - 1,131,142ⁿᵈ prime sum, 4,229,425ᵗʰ composite sum 76.23 seconds 209,456,854,921,713 - 5,012,372ⁿᵈ prime sum, 19,786,181ˢᵗ composite sum 968.26 seconds ^C
Sidef
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})")
}
- Output:
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)
(takes ~6 seconds)
Wren
Takes around 2 minutes, which is respectable for Wren, but uses a lot of memory.
import "./math" for Int
import "./sort" for Find
import "/fmt" for Fmt
var limit = 4 * 1e8
var c = Int.primeSieve(limit - 1, false)
var compSums = []
var primeSums = []
var csum = 0
var psum = 0
for (i in 2...limit) {
if (c[i]) {
csum = csum + i
compSums.add(csum)
} else {
psum = psum + i
primeSums.add(psum)
}
}
for (i in 0...primeSums.count) {
var ix
if ((ix = Find.first(compSums, primeSums[i])) >= 0) {
Fmt.print("$,21d - $,12r prime sum, $,12r composite sum", primeSums[i], i+1, ix+1)
}
}
- Output:
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
XPL0
func IsPrime(N); \Return 'true' if N is prime
int N, I;
[if N <= 2 then return N = 2;
if (N&1) = 0 then \even >2\ return false;
for I:= 3 to sqrt(N) do
[if rem(N/I) = 0 then return false;
I:= I+1;
];
return true;
];
int Cnt, N, M, SumP, SumC, NumP, NumC;
[Cnt:= 0;
N:= 1; M:= 1;
NumP:= 2; NumC:= 4;
SumP:= 2; SumC:= 4;
Format(8, 0);
Text(0, " sum prime composit
");
loop [if SumC > SumP then
[repeat NumP:= NumP+1 until IsPrime(NumP);
SumP:= SumP + NumP;
N:= N+1;
];
if SumP > SumC then
[repeat NumC:= NumC+1 until not IsPrime(NumC);
SumC:= SumC + NumC;
M:= M+1;
];
if SumP = SumC then
[RlOut(0, float(SumP));
RlOut(0, float(N));
RlOut(0, float(M)); CrLf(0);
Cnt:= Cnt+1;
if Cnt >= 6 then quit;
repeat NumC:= NumC+1 until not IsPrime(NumC);
SumC:= SumC + NumC;
M:= M+1;
];
];
]
- Output:
sum prime composit 10 3 2 1988 33 51 14697 80 147 83292 175 361 1503397 660 1582 18859052 2143 5699