#!/usr/bin/python
# -*- coding: utf-8 -*-
"Find the multiples of 3 or 5 under N."

def naive(n):
    return sum(i for i in range(n) if i % 3 == 0 or i % 5 == 0)

def ok(a, b): assert a == b, (a, b)
ok(naive(10), 23)
ok(naive(100), 2318)

# Multiples under 15.
muf = [_i for _i in range(15) if _i % 3 == 0 or _i % 5 == 0]
def smart(n):
    """Efficient algorithm for large n.

    In Project Euler itself, N is only 1000, but for
    <https://www.hackerrank.com/contests/projecteuler/challenges/euler001>
    n can be a billion, and they generally don’t give you enough
    computer time to do a billion of anything.  So this algorithm
    computes the result in a constant number of steps, somewhere in
    the neighborhood of 100 Python bytecodes.

    <https://aadrake.com/posts/2017-01-04-an-unreasonably-deep-dive-into-project-euler-problem-1.html>
    gives another O(1) algorithm, based on separately calculating the
    sums of the multiples of 3, 5, and 15.

    """
    div, mod = divmod(n, 15)
    # There are div-1 (? )multiples of 15 in n.  Each one of them is
    # part of the sum len(muf) times, and so is sum(muf).  The
    # (div-1)th triangular number (½i(i+1)) multiplied by 15 gives us
    # the sum of those multiples of 15.
    b = div * (div - 1) * 15 * len(muf) // 2 + sum(muf) * div
    # Mod tells us how many times the final multiple of 15
    # participates.
    cs = [i for i in muf if i < mod]
    c = 15 * div * len(cs) + sum(cs)
    return b + c

if __name__ == '__main__':
    for i in range(32) + [1000]:
        print i, naive(i), smart(i)

# This takes like 25 milliseconds.
for _i in 10, 100, 101, 103, 106, 110, 1000, 10000:
    ok(smart(_i), naive(_i))