Equal prime and composite sums: Difference between revisions
Content added Content deleted
(→{{header|Wren}}: Added a further series term.) |
|||
| Line 31: | Line 31: | ||
=={{header|Julia}}== |
|||
<lang julia>using Primes |
|||
function getsequencematches(N) |
|||
pmask = primesmask(N) |
|||
psum, csum, pindex, cindex, pcount, ccount = 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 pindex < N |
|||
while psum < csum |
|||
pindex >= N && @goto done |
|||
incrementpsum() |
|||
end |
|||
if psum == csum |
|||
println("Primes up to $pindex at position $pcount and composites up to $cindex at position $ccount sum to $psum.") |
|||
while psum == csum |
|||
incrementpsum() |
|||
incrementcsum() |
|||
end |
|||
end |
|||
while csum < psum |
|||
incrementcsum() |
|||
end |
|||
end |
|||
@label done |
|||
end |
|||
getsequencematches(500_000_000) |
|||
</lang>{{out}} |
|||
<pre> |
|||
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. |
|||
</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Revision as of 02:34, 2 March 2022
Equal prime and composite sums 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.
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
Julia
<lang julia>using Primes
function getsequencematches(N)
pmask = primesmask(N)
psum, csum, pindex, cindex, pcount, ccount = 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 pindex < N
while psum < csum
pindex >= N && @goto done
incrementpsum()
end
if psum == csum
println("Primes up to $pindex at position $pcount and composites up to $cindex at position $ccount sum to $psum.")
while psum == csum
incrementpsum()
incrementcsum()
end
end
while csum < psum
incrementcsum()
end
end
@label done
end
getsequencematches(500_000_000)
</lang>
- 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.
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 while found<iff(platform()=JS?10:11) do integer c = compare(ps,cs)+3 -- {-1,0,+1} --> {2,3,4}, -- so odd() means equal(), -- else bit2 ==> inc(ps), -- and bit4 ==> inc(cs). if odd(c) 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 c = 6 -- do both, ie inc(ps) and inc(cs) end if if and_bits(c,2) then psn += 1 -- prime sum number npi += 1 -- next prime index ps += get_prime(npi) end if if and_bits(c,4) 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.4s)
9,646,383,703,961 - 1,131,142nd prime sum, 4,229,425th composite sum (1.7s)
209,456,854,921,713 - 5,012,372nd prime sum, 19,786,181st composite sum (6.9s)
3,950,430,820,867,201 - 20,840,220th prime sum, 86,192,660th composite sum (29.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. <lang perl6>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;
};</lang>
- 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
Wren
Takes around 2 minutes, which is respectable for Wren, but uses a lot of memory. <lang ecmascript>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)
}
}</lang>
- 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