Problem 26 "Reciprocal cycles"

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2= 0.5
1/3= 0.(3)
1/4= 0.25
1/5= 0.2
1/6= 0.1(6)
1/7= 0.(142857)
1/8= 0.125
1/9= 0.(1)
1/10= 0.1

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.

Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

問 26 「逆数の循環節 その1」

単位分数とは分子が1の分数である. 分母が2から10の単位分数を10進数で表記すると次のようになる.

0.1(6)は 0.166666... という数字であり, 1桁の循環節を持つ. 1/7 の循環節は6桁ある.

d < 1000 の条件で、 1/d の中で小数部の循環節が最も長くなるような d を求めよ.

1. Long division

struct UnitFraction {
    reciprocal: u32,
    repetend_length: u32,
}

fn is_recurring(mut n: u32) -> bool {
    if n % 2 != 0 && n % 5 != 0 {
        return true;
    }
    for &d in [2u32, 5].iter() {
        while n % d == 0 {
            n /= d;
        }
        if n == 1 {
            return false;
        }
    }
    true
}

fn repetend_length(n: u32, residue_history: &mut [u32]) -> u32 {
    assert!(residue_history.len() >= n as usize);
    let mut dividend = 1u32;
    for nth_time_around in 0u32.. {
        let residue = dividend % n;
        let last_time = residue_history[residue as usize];
        if last_time != 0 {
            return nth_time_around - last_time;
        }
        residue_history[residue as usize] = nth_time_around;
        dividend = residue * 10;
    }
    panic!("irrational number")
}

fn number_with_longest_recurring_cycle(below: u32) -> u32 {
    assert!(below > 3);
    let mut uf = UnitFraction {
        reciprocal: 1,
        repetend_length: 0,
    };
    let blank = vec![0u32; below as usize];
    let mut residue_history = vec![0u32; below as usize];
    for n in (1u32..below).rev() {
        if !is_recurring(n) {
            continue;
        }
        residue_history[..n as usize].copy_from_slice(&blank[..n as usize]);
        let length = repetend_length(n, &mut residue_history[0..n as usize]);
        if n - 1 == length {
            return n;
        }
        if length > uf.repetend_length {
            uf.repetend_length = length;
            uf.reciprocal = n;
        }
    }
    uf.reciprocal
}

fn main() {
    let num = number_with_longest_recurring_cycle(1000);
    println!("{}", num);
    assert_eq!(num, 983);

    assert_eq!(number_with_longest_recurring_cycle(10000), 9967);
    assert_eq!(number_with_longest_recurring_cycle(9968), 9967);
    assert_eq!(number_with_longest_recurring_cycle(5000), 4967);
    assert_eq!(number_with_longest_recurring_cycle(8), 7);
    assert_eq!(number_with_longest_recurring_cycle(20), 19);
    assert_eq!(number_with_longest_recurring_cycle(18), 17);
    assert_eq!(number_with_longest_recurring_cycle(25), 23);
    assert_eq!(number_with_longest_recurring_cycle(6), 3);
}

2. Prime numbers

struct Index {
    i: usize,
    _ite: Box<dyn Iterator<Item = usize>>,
}

impl Index {
    fn increment(&mut self) {
        self.i += self._ite.next().unwrap();
    }
    fn new() -> Self {
        Self {
            i: 5,
            _ite: Box::new(vec![2usize, 4].into_iter().cycle()),
        }
    }
}

fn rule_out(sieve: &mut Vec<bool>, prime: usize) {
    for i in (prime * prime..sieve.len()).step_by(prime) {
        sieve[i] = false;
    }
}

fn primes(below: u32) -> Vec<u32> {
    let mut primes: Vec<u32> = vec![2u32, 3u32];
    let mut sieve = vec![true; below as usize];
    let sqrt = (sieve.len() as f32).sqrt() as usize;
    let mut index = Index::new();
    while index.i <= sqrt {
        if sieve[index.i] {
            primes.push(index.i as u32);
            rule_out(&mut sieve, index.i);
        }
        index.increment();
    }
    while index.i < sieve.len() {
        if sieve[index.i] {
            primes.push(index.i as u32);
        }
        index.increment();
    }
    primes
}

fn repetend_length(n: u32) -> u32 {
    assert!(n % 2 != 0 && n % 5 != 0);
    let mut dividend = 10u32;
    for nth_time_around in 1u32.. {
        let residue = dividend % n;
        if residue == 1 {
            return nth_time_around
        }
        dividend = residue * 10;
    }
    panic!("irrational number")
}

fn number_with_longest_recurring_cycle(below: u32) -> u32 {
    if below < 7 {
        return 3;
    }
    let primes = primes(below);
    for &p in primes.iter().rev() {
        if repetend_length(p) == p - 1 {
            return p;
        }
    }
    panic!("couldn't find a point that n - 1 == repetend_length(n)")
}

fn main() {
    let num = number_with_longest_recurring_cycle(1000);
    println!("{}", num);
    assert_eq!(num, 983);

    assert_eq!(number_with_longest_recurring_cycle(10000), 9967);
    assert_eq!(number_with_longest_recurring_cycle(9968), 9967);
    assert_eq!(number_with_longest_recurring_cycle(5000), 4967);
    assert_eq!(number_with_longest_recurring_cycle(8), 7);
    assert_eq!(number_with_longest_recurring_cycle(20), 19);
    assert_eq!(number_with_longest_recurring_cycle(18), 17);
    assert_eq!(number_with_longest_recurring_cycle(25), 23);
    assert_eq!(number_with_longest_recurring_cycle(6), 3);
}

3. Divisors of p-1 and modular exponentiation

struct Index {
    i: usize,
    _ite: Box<dyn Iterator<Item = usize>>,
}

impl Index {
    fn increment(&mut self) {
        self.i += self._ite.next().unwrap();
    }
    fn new() -> Self {
        Self {
            i: 5,
            _ite: Box::new(vec![2usize, 4].into_iter().cycle()),
        }
    }
}

fn rule_out(sieve: &mut Vec<bool>, prime: usize) {
    for i in (prime * prime..sieve.len()).step_by(prime) {
        sieve[i] = false;
    }
}

fn primes(below: u32) -> Vec<u32> {
    let mut primes: Vec<u32> = vec![2u32, 3u32];
    let mut sieve = vec![true; below as usize];
    let sqrt = (sieve.len() as f32).sqrt() as usize;
    let mut index = Index::new();
    while index.i <= sqrt {
        if sieve[index.i] {
            primes.push(index.i as u32);
            rule_out(&mut sieve, index.i);
        }
        index.increment();
    }
    while index.i < sieve.len() {
        if sieve[index.i] {
            primes.push(index.i as u32);
        }
        index.increment();
    }
    primes
}

fn mod_pow(mut a: u32, mut exp: u32, m: u32) -> u32 {
    if m == 1 {
        return 0;
    }
    if exp == 0 {
        return 1;
    }
    let mut result = 1;
    a %= m;
    loop {
        if exp % 2 == 1 {
            result *= a;
            result %= m;
        }
        exp >>= 1;
        if exp == 0 {
            break;
        }
        a *= a;
        a %= m;
    }
    result
}

fn list_divisors(n: u32) -> Vec<u32> {
    let side = (n as f32).sqrt() as u32;
    let mut vec = vec![];
    for d in 1..=side {
        if n % d == 0 {
            vec.push(d);
            if d != side {
                vec.push(n / d);
            }
        }
    }
    vec.sort();
    vec
}

fn number_with_longest_recurring_cycle(below: u32) -> u32 {
    if below < 7 {
        return 3;
    }
    let primes = primes(below);
    'next_prime: for &p in primes.iter().rev() {
        let divisors = list_divisors(p - 1);
        for &d in &divisors[0..divisors.len() - 1] {
            if mod_pow(10, d, p) == 1 {
                continue 'next_prime;
            }
        }
        return p;
    }
    panic!("couldn't find a point that n - 1 == recurring_length(n)")
}

fn main() {
    let num = number_with_longest_recurring_cycle(1000);
    println!("{}", num);
    assert_eq!(num, 983);

    assert_eq!(number_with_longest_recurring_cycle(10000), 9967);
    assert_eq!(number_with_longest_recurring_cycle(9968), 9967);
    assert_eq!(number_with_longest_recurring_cycle(5000), 4967);
    assert_eq!(number_with_longest_recurring_cycle(8), 7);
    assert_eq!(number_with_longest_recurring_cycle(20), 19);
    assert_eq!(number_with_longest_recurring_cycle(18), 17);
    assert_eq!(number_with_longest_recurring_cycle(25), 23);
    assert_eq!(number_with_longest_recurring_cycle(6), 3);
}

Reference