#![allow(dead_code)]

fn find_longest_recurrence(n: u64) -> u64 {
    (1..n).map(length_of_recurrence).max().unwrap_or(0)
}

fn length_of_recurrence(n: u64) -> u64 {
    for i in 1.. {
        let p = 10_u64.pow(i);
        let gcd = gcd(p - 1, n);
        if !has_infinite_recurrence(n/gcd) {
            return i as u64;
        };
    }

    0
}

fn gcd(mut a: u64, mut b: u64) -> u64 {
    while b != 0 {
        let tmp = b;
        b = a % b;
        a = tmp;
    }

    a
}

fn has_infinite_recurrence(n: u64) -> bool {
    primes_to_limit(n)
        .iter()
        .filter(|p| **p != 1 && **p != 2 && **p != 5)
        .find(|p| n % **p == 0)
        .is_some()
}

fn unit_fraction(n: u64) -> f64 {
    1.0 / n as f64
}

fn primes_to_limit(n: u64) -> Vec<u64> {
    let limit = (n as f32).sqrt() as usize;
    let mut primes = vec![true; n as usize - 1];

    for i in 2..limit + 1 {
        if primes[i - 2] {
            for j in (i * 2..=n as usize).step_by(i) {
                primes[j - 2] = false;
            }
        }
    }

    primes.iter().enumerate()
        .filter(|(_, &is_prime)| is_prime)
        .map(|(prime_index, _)| prime_index as u64 + 2)
        .collect()
}

#[test]
fn determines_longest_recurrence() {
    assert_eq!(find_longest_recurrence(1_00), 42);
}

#[test]
fn determines_lengths_of_recurrences() {
    assert_eq!(length_of_recurrence(3), 1);
    assert_eq!(length_of_recurrence(6), 1);
    assert_eq!(length_of_recurrence(7), 6);
    assert_eq!(length_of_recurrence(9), 1);
}

#[test]
fn determines_if_unit_fraction_has_infinite_recurrence() {
    assert!(!has_infinite_recurrence(2));
    assert!(has_infinite_recurrence(3));
    assert!(!has_infinite_recurrence(4));
    assert!(!has_infinite_recurrence(5));
    assert!(has_infinite_recurrence(6));
    assert!(has_infinite_recurrence(7));
    assert!(!has_infinite_recurrence(8));
    assert!(has_infinite_recurrence(9));
    assert!(!has_infinite_recurrence(10));
}

#[test]
fn unit_fractions_are_calculated() {
    assert_eq!(unit_fraction(2), 0.5);
    assert_eq!(unit_fraction(4), 0.25);
    assert_eq!(unit_fraction(5), 0.2);
}

#[test]
fn primes_are_generated() {
    assert_eq!(primes_to_limit(10), [2, 3, 5, 7])
}