Equal prime and composite sums

From Rosetta Code
Revision as of 10:29, 1 March 2022 by PureFox (talk | contribs) (→‎{{header|Wren}}: Added a further series term.)
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


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
Retrieved from "https://rosettacode.org/wiki/Equal_prime_and_composite_sums?oldid=320104"