super-prime 0.1.0

Find the super prime number.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

use num_primes::{BigUint, Verification};
use num_traits::Pow;
use std::{
    collections::VecDeque,
    iter::from_generator,
    ops::{Div, Mul, Rem},
};

/// Insert 0-9 to number at given position
///
/// # Examples
///
/// ```
/// # use super_prime::{insert_digit, BigUint};
/// let start = BigUint::from(13usize);
/// for n in insert_digit(&start, 0, true) {
///     println!("{}", n); // 131, 137, 139
/// }
/// for n in insert_digit(&start, 1, true) {
///     println!("{}", n); // 103, 113, 167, 173, 193
/// }
/// for n in insert_digit(&start, 2, false) {
///     println!("{}", n); // 113, 313, 613
/// }
/// ```
pub fn insert_digit(n: &BigUint, position: usize, contains_zero: bool) -> impl Iterator<Item = BigUint> + '_ {
    debug_assert!(position <= n.to_string().len(), "position {} of {} is out of range", position, n);
    let start_index: u8 = if contains_zero { 0 } else { 1 };
    let pow = BigUint::from(10usize).pow(position);
    let lhs = n.div(&pow).mul(&pow).mul(10usize);
    let rhs = n.rem(&pow);
    from_generator(move || {
        for i in start_index..=9 {
            let digit = BigUint::from(i).mul(&pow);
            let new = digit + &lhs + &rhs;
            if Verification::is_prime(&new) {
                yield new;
            }
        }
    })
}

/// A super prime is a prime number that, when any of its digits is deleted, the remaining number is still prime.
///
/// This function returns a sequence of super primes, starting from a given number, with a given length.
///
/// eg:
/// - 1 -> 19 -> 199 -> 1999 -> 13999 -> ...
/// - 2 -> 29 -> 269 -> 2969 -> 25969 -> ...
///
/// ## Examples
///
/// ```
/// # use super_prime::{BigUint, super_prime};
/// let start = BigUint::from(2usize);
/// for n in super_prime(&start, 100).into_iter().rev() {
///     println!("{}", n);
/// }
/// ```
pub fn super_prime(start: &BigUint, iteration: usize) -> Vec<BigUint> {
    let seq = vec![start.clone()];
    let mut stack = VecDeque::new();
    stack.push_back(seq);
    // dfs search, return first stack reached max length
    'outer: while let Some(old_seq) = stack.pop_back() {
        let last = unsafe { old_seq.last().unwrap_unchecked() };
        let old_len = last.to_string().len();
        for i in 0..old_len {
            for number in insert_digit(last, i, i != old_len) {
                let mut new_seq = old_seq.clone();
                new_seq.push(number.clone());
                stack.push_back(new_seq);
                if old_len == iteration {
                    break 'outer;
                }
            }
        }
    }
    // nil means no such sequence
    stack.pop_back().unwrap_or_default()
}