Problem 51 "Prime digit replacements"
By replacing the 1st digit of the 2-digit number *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.
By replacing the 3rd and 4th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.
Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.
問 51 「素数の桁置換」
*3の第1桁を置き換えることで, 13, 23, 43, 53, 73, 83という6つの素数が得られる.
56**3の第3桁と第4桁を同じ数で置き換えることを考えよう. この5桁の数は7つの素数をもつ最初の例である: 56003, 56113, 56333, 56443, 56663, 56773, 56993. よって, この族の最初の数である56003は, このような性質を持つ最小の素数である.
桁を同じ数で置き換えることで8つの素数が得られる最小の素数を求めよ. (注:連続した桁でなくても良い)
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()), } } } struct Sieve { _sieve: Vec<bool>, _primes: Vec<usize>, _index: Index, _queue: std::collections::VecDeque<usize>, } impl Sieve { fn rule_out(&mut self, prime: usize) { for i in (prime * prime..self._sieve.len()).step_by(prime) { self._sieve[i] = false; } } fn rule_out_from_previous_position(&mut self, prime: usize, pp: usize) { use std::cmp::max; let begin = max((((pp - 1) / prime) + 1) * prime, prime * prime); for i in (begin..self._sieve.len()).step_by(prime) { self._sieve[i] = false; } } fn clean_sieve(&mut self) { let sqrt = (self._sieve.len() as f32).sqrt() as usize; while self._index.i <= sqrt { if self._sieve[self._index.i] { self._primes.push(self._index.i); self._queue.push_back(self._index.i); self.rule_out(self._index.i); } self._index.increment(); } while self._index.i < self._sieve.len() { if self._sieve[self._index.i] { self._primes.push(self._index.i); self._queue.push_back(self._index.i); } self._index.increment(); } } fn new(below: u32) -> Self { assert!(below > 4); let sieve = vec![true; below as usize]; let mut s = Self { _sieve: sieve, _primes: vec![], _index: Index::new(), _queue: std::collections::VecDeque::new(), }; s._queue.push_back(2); s._queue.push_back(3); s.clean_sieve(); s } fn extend(&mut self) { let previous_len = self._sieve.len(); self._sieve.extend(vec![true; previous_len]); for &p in &self._primes.clone() { self.rule_out_from_previous_position(p, previous_len); } self.clean_sieve(); } fn is_prime(&mut self, n: u32) -> bool { if n == 2 || n == 3 { return true; } if n == 0 || n == 1 || n % 2 == 0 || n % 3 == 0 { return false; } while n > self._sieve.len() as u32 - 1 { self.extend(); } self._sieve[n as usize] } fn next_prime(&mut self) -> u32 { loop { if let Some(p) = self._queue.pop_front() { return p as u32; } self.extend(); } } } fn appearance_frequency_excluding_tail(mut p: u32, frequency: &mut Frequency) { frequency.clear(); p /= 10; while p > 0 { let d = p % 10; frequency.0[d as usize] += 1; p /= 10; } } fn expand_wildcard(mut p: u32, wildcard: u8, expansion: &mut WildcardExpansion) { expansion.clear(); let mut dicimal_place = 1u32; let first_digit = p % 10; for n in &mut expansion.0 { *n += first_digit; } p /= 10; while p > 0 { dicimal_place *= 10; let d = (p % 10) as u8; let is_wildcard = d as u8 == wildcard; for (i, n) in expansion.0.iter_mut().enumerate() { *n += dicimal_place * if is_wildcard { i as u32 } else { d as u32 }; } p /= 10; } } fn digit_len_match(mut a: u32, mut b: u32) -> bool { while a > 0 && b > 0 { a /= 10; b /= 10; } a == b } struct Frequency([u8; 10]); impl Frequency { const BLANK: [u8; 10] = [0u8; 10]; fn clear(&mut self) { self.0.copy_from_slice(&Self::BLANK[..]); } fn new() -> Self { Frequency(Frequency::BLANK.clone()) } } struct WildcardExpansion([u32; 10]); impl WildcardExpansion { const BLANK: [u32; 10] = [0u32; 10]; fn clear(&mut self) { self.0.copy_from_slice(&Self::BLANK[..]); } fn new() -> Self { WildcardExpansion(WildcardExpansion::BLANK.clone()) } } fn smallest_prime_with_repetition_of_family(replacement: u8, family_length: u8) -> u32 { assert!(family_length > 4); let mut sieve = Sieve::new(10_000); let mut p = sieve.next_prime(); while p < 10 { p = sieve.next_prime(); } let mut frequency = Frequency::new(); let mut expansion = WildcardExpansion::new(); 'explorarion: loop { appearance_frequency_excluding_tail(p, &mut frequency); for (i, _) in frequency .0 .iter() .enumerate() .filter(|(_, &f)| f == replacement) { expand_wildcard(p, i as u8, &mut expansion); let mut family = expansion.0[1..] .iter() .map(|&n| n) .filter(|&n| sieve.is_prime(n)) .collect::<Vec<u32>>(); if sieve.is_prime(expansion.0[0]) && digit_len_match(expansion.0[0], p) { family.insert(0, expansion.0[0]); } if family.len() as u8 == family_length { println!("{:?}", &family); break 'explorarion family[0]; } } p = sieve.next_prime(); } } fn main() { { let p = smallest_prime_with_repetition_of_family(1, 6); assert_eq!(p, 13); } { let p = smallest_prime_with_repetition_of_family(2, 7); assert_eq!(p, 56003); } { let p = smallest_prime_with_repetition_of_family(3, 8); assert_eq!(p, 121313); } { // timeout with playground // https://www.hackerrank.com/contests/projecteuler/challenges/euler051/forum/comments/310849 // let p = smallest_prime_with_repetition_of_family(4, 6); // assert_eq!(p, 2422027); } { // timeout with playground // https://www.hackerrank.com/contests/projecteuler/challenges/euler051/forum/comments/592444 // let p = smallest_prime_with_repetition_of_family(4, 7); // assert_eq!(p, 80047003); } { // timeout with playground // https://projecteuler.net/action=quote;post_id=382609 // let p = smallest_prime_with_repetition_of_family(3, 9); // assert_eq!(p, 38000201); } }