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
 OEIS:A007504 - Sum of the first n primes
 OEIS:A053767 - Sum of first n composite numbers
 OEIS:A294174 - Numbers that can be expressed both as the sum of first primes and as the sum of first composites


#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";
}