core.exception.OutOfMemoryError@(0) using a large dynamic array

Question

import std.math;
import std.bigint;
import std.stdio;

BigInt sum_min_pfactor(long N){
    BigInt f(int n) {
        return BigInt(n)*(BigInt(n)+1) / 2 - 1;
    }

    int v = cast(int)(sqrt(float(N)));

    bool[] used;
    used.length = v+1;

    BigInt ret;
    BigInt finish;

    BigInt[] s_sum,s_cnt,l_cnt,l_sum;
    s_sum.length = v+1;
    l_sum.length = v+1;
    s_cnt.length = v+1;
    l_cnt.length = v+1;

    for (long i = 0; i <= v; i++) {
        s_cnt[i] = i - 1;
        s_sum[i] = f(cast(int)i);
    }

    for (long i = 1; i <= v; i++) {
        l_cnt[i] = N / cast(int)i - 1;
        l_sum[i] = f(cast(int)(N) / cast(int)i);
    }

    for (long p = 2; p <= v; p++) {
        if (s_cnt[p] == s_cnt[p-1]) {
            continue;
        }

        BigInt p_cnt = s_cnt[p-1];
        BigInt p_sum = s_sum[p - 1];
        long q = p * p;

        ret = ret + p * (l_cnt[p] - p_cnt);
        l_cnt[1] = l_cnt[1] - l_cnt[p] + p_cnt;
        l_sum[1] = l_sum[1] - (l_sum[p] - p_sum) * p;

        long interval = (p & 1) + 1;

        if (v > N / q) {
            finish = N / q;
        }
        else {
            finish = v; 
        }

        for (long i = p+interval; i <= finish; i += interval){
            if (used[i]) {
                continue;
            }

            long d = i * p;

            if (d <= v) {
                l_cnt[i] = l_cnt[i] - l_cnt[d] + p_cnt;
                l_sum[i] = l_sum[i] - (l_sum[d] - p_sum) * p;
            }
            else {
                long t = N / d;   
                l_cnt[i] = l_cnt[i] - s_cnt[t] + p_cnt;
                l_sum[i] = l_sum[i] - (s_sum[t] - p_sum) * p;
            }
        }

        if (q <= v) {
            for (long i = q; i < finish; i += p*interval){
                used[i] = true;
            }
        }

        for (long i = v; i >= q - 1; i--) {
            long t = i / p;
            s_cnt[i] = s_cnt[i] - s_cnt[t] + p_cnt;
            s_sum[i] = s_sum[i] - (s_sum[t] - p_sum) * p;
        }
    }
    return l_sum[1] + ret;
}

void main () {
    writeln(sum_min_pfactor(pow(10,12)));
}

The code above works perfectly when dealing with numbers below 10^9. However, after that it starts giving incorrect values and crashes with a memory error when trying to compute an answer for 10^9. I'm using the BigInt library but my guess is one of the variables that is not declared as BigInts is messing up my results. I'm also assuming the memory error is caused by the size of the dynamic arrays, but I can't figure out how to solve that particular problem.

Answer 1

The answer is a silent integer overflow in the std.math.pow() function.

The output of

writefln("%d", pow(10, 12));
writefln("%d", pow(10, 12L));

is

-727379968
1000000000000

Now sqrt(-727379968) is -nan. Cast to integer gives int.min, which is about -2 GiB. The length property of the arrays is unsigned. Therefore each array is type.sizeof * 2 GiB in size which explains the out-of-memory error.

Solution: add suffix L to one or both numbers, e.g.

writeln(sum_min_pfactor(pow(10L,9L)));