Project Euler - Problem 601

Divisibility streaks

正の数 n に対して, n+k が k+1 で割り切れないような最小の正の整数kをもって関数 streak(n)=k と定義しよう.

例えば:
13は1で割り切れる
14は2で割り切れる
15は3で割り切れる
16は4で割り切れる
17は5で割り切れない
よって, streak(13)=4

同様に:
120は1で割り切れる
121は2で割り切れない
よって, streak(120)=1

1 < n < N を満たし streak(n)=s である整数 n の個数を P(s,N) と定義する.
例えば, P(3,14)=1, P(6,10⁶)=14286 となる.

i が 1 から 31 の範囲にあるときの P(i, 4ⁱ) の和を求めよ.

(日本語訳より)

簡単な実験により

streak(n) ≧ s　⇔　n = k * LCM(1, 2, ..., s) + 1 (k = 1, 2, ...)

がわかる．証明はだるいのでしません．

P(i, 4ⁱ) を求める際のループ回数は約 4ⁱ / LCM(1, ..., i) 回ですが，これは最大でも i = 28 の時の約 900,000 回で済むのですぐに答えがでる．

typedef long long lint

lint LCM(lint m, lint n)
{
    lint k;
    lint m_tmp = m, n_tmp = n;
    do {
        k = m % n;
        m = n; n = k;
    } while (k != 0);
    return m_tmp / m * n_tmp;
}

lint streak(lint n) {
    for (lint k = 0; ; k++) {
        if ((n + k) % (k + 1) != 0) return k;
    }
}

lint P(lint s, lint N) {
    lint lcm = 1;
    for (lint i = 2; i <= s; i++) lcm = LCM(lcm, i);

    lint ret = 0;
    for (lint n = lcm + 1; n < N; n += lcm) {
        if (streak(n) == s) ret++;
    }
    return ret;
}

int main() {

    clock_t start, end;
    start = clock();

    lint ans = 0;
    for (lint i = 1; i <= 31; i++) ans += P(i, 1LL << (2 * i));
    cout << ans << endl;

    end = clock();
    printf("%f sec.\n", double(end - start) / CLOCKS_PER_SEC);
    return 0;
}

0.7 sec くらい．

絶滅

どうでもいい

Project Euler - Problem 601

Divisibility streaks