Problem 12: Highly Divisible Triangular Number

Problem

• Link to the problem

Solution

See it on GitHub.

//* Problem 12: Highly Divisible Triangular Number
//* The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
//* 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
//* Let us list the factors of the first seven triangle numbers:
//* 1: 1
//* 3: 1,3
//* 6: 1,2,3,6
//* 10: 1,2,5,10
//* 15: 1,3,5,15
//* 21: 1,3,7,21
//* 28: 1,2,4,7,14,28
//* We can see that 28 is the first triangle number to have over five divisors.
//* What is the value of the first triangle number to have over five hundred divisors?

//! time complexity: O(k sqrt T_k)
//! where k is the index of the triangle number T_k with >500 divisors
use euler::prelude::*;

const SMALL_PRIMES: &[usize] = &[
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
];

fn count_divisors(mut n: usize) -> usize {
    if n == 1 {
        return 1;
    }

    let mut count = 1;

    // handle small primes first
    for &p in SMALL_PRIMES {
        if p * p > n {
            break;
        }
        let mut power = 0;
        while n % p == 0 {
            n /= p;
            power += 1;
        }
        if power > 0 {
            count *= power + 1;
        }
    }

    // handle remaining factors
    let mut i = 101;
    while i * i <= n {
        let mut power = 0;
        while n % i == 0 {
            n /= i;
            power += 1;
        }
        if power > 0 {
            count *= power + 1;
        }

        // skip even numbers after 2
        i += 2;
    }

    if n > 1 {
        count *= 2;
    }

    count
}

fn solve() -> Solution {
    let mut n = 8; // start from 8 because that's where examples end

    loop {
        // gcd(n, n + 1) = 1
        let divisors = if n % 2 == 0 {
            // n is even: t(n) = (n/2) * (n+1)
            count_divisors(n / 2) * count_divisors(n + 1)
        } else {
            // n is odd: t(n) = n * ((n+1)/2)
            count_divisors(n) * count_divisors((n + 1) / 2)
        };

        if divisors > 500 {
            return solution!(n * (n + 1) / 2);
        }

        n += 1;
    }
}

problem!(
    12,
    solve,
    "3e7be445b6c19e6db58c2482005c1f78cb74011a4279249ca632011a9f1b61a2"
);