Metadata
aliases: [Project Euler Problem solutions]
shorthands: {}
created: 2022-05-29 11:59:02
modified: 2022-06-08 01:09:34
Project Euler is a website, containing a collection of hard computer science or mathematics problems, designed to be solved using computers.
This document contains solutions to some of the problems available on the website. These were written mostly in Rust.
The solutions were originally in separate documents, but then were gathered in a single place using the following Python script.
import re
from pathlib import Path
output = Path("Project Euler Solutions.md")
problem_files = list(Path(".").glob("Project Euler Problem*.md"))
problem_files.sort(key=lambda x: int(x.stem.split(" ")[3]))
out_str = ""
for file in problem_files:
title = file.stem.removesuffix(".md").removeprefix("Project Euler ")
out_str += f"## {title}\n\n"
content = file.read_text().replace("##", "###")
# Remove
# ---
# yaml: content
# some_yaml_stuff: here
# ---
# from the beginning of the file
content = re.sub(r"---\n.*?---\n", "", content, flags=re.DOTALL)
out_str += content + "\n"
output.write_text(out_str)
The answer is:
Written in Rust
fn main() {
let mut sum = 0;
for n in 1..1000 {
if (n % 3) == 0 || (n % 5) == 0 {
sum += n;
}
}
println!("The answer is: {}", sum); // 233168
}
The result is:
Written in Rust
fn main() {
let mut n1 = 1;
let mut n2 = 2;
let mut sum = 0;
while n2 <= 4_000_000 {
if (n2 % 2) == 0 {
sum += n2;
}
let temp = n2;
n2 = n2 + n1;
n1 = temp;
}
println!("The result is: {}", sum); // 4613732
}
The answer is:
Written in Rust
fn main() {
const ORIG_NUM: i64 = 600851475143;
let mut curr_prime: i64 = 2;
let mut div = ORIG_NUM;
while div != 1 {
if (div % curr_prime) != 0 {
next_prime(&mut curr_prime);
} else {
div = div / curr_prime;
}
}
println!("The result is: {}", curr_prime); // 6857
}
fn is_prime(num: i64) -> bool {
for a in 2..(num / 2) {
if (num % a) == 0 {
return false;
}
}
return true;
}
fn next_prime(num: &mut i64) {
loop {
(*num) = (*num) + 1;
if is_prime(*num) {
return;
}
}
}
The answer is:
Written in Rust
fn main() {
let mut max_val = 0;
for n1 in 100..1000 {
for n2 in 100..1000 {
if is_palindrome(n1 * n2) {
max_val = std::cmp::max(n1 * n2, max_val);
}
}
}
println!("The result is: {}", max_val); // 906609
}
fn is_palindrome(num: i32) -> bool {
let st: String = num.to_string();
let reversed: String = st.chars().rev().collect();
st == reversed
}
Primes are related to this problem.
The answer is:
Written in Rust
fn main() {
let mut factors: [i64; 8] = [0, 0, 0, 0, 0, 0, 0, 0];
let primes: [i64; 8] = [2, 3, 5, 7, 11, 13, 17, 19];
for nn in 2..21 {
for p in &primes {
let prime = *p;
let mut n = nn;
let mut factor: i64 = 0;
while n != 1 && prime <= n {
if (n % prime) == 0 {
n /= prime;
factor += 1;
}
let idx_option = primes.iter().position(|&s| s == prime);
match idx_option {
Some(idx) => {
if factor > factors[idx] {
println!("Factors of {} with {}: {}", nn, prime, factor);
}
factors[idx] = std::cmp::max(factors[idx], factor);
}
None => {}
}
if (n % prime) != 0 && prime <= n {
n = 1;
}
}
}
}
let mut res = 1;
for i in 0..8 {
println!("{} - {}", primes[i], factors[i]);
res *= primes[i].pow(factors[i] as u32);
}
println!("The result is: {}", res); // 232792560
}
fn get_factors(num: i32, prime: i32) -> i32 {
if num <= 0 {
return 0;
}
let mut n = num;
let mut f: i32 = 0;
loop {
if (n % prime) == 0 {
n /= prime;
f += 1;
} else {
break;
}
}
return f;
}
fn is_prime(num: i64) -> bool {
for a in 2..(num / 2) {
if (num % a) == 0 {
return false;
}
}
return true;
}
fn next_prime(num: &mut i64) {
loop {
(*num) = (*num) + 1;
if is_prime(*num) {
return;
}
}
}
The answer is:
Written in Rust
fn main() {
let mut sq_sum = 0;
let mut sum_sq = 0;
for n in 1..101 {
sq_sum += n * n;
sum_sq += n;
}
sum_sq = sum_sq * sum_sq;
println!("First one hundred natural numbers");
println!("The sum of the squares: {}", sq_sum); // 338350
println!("The square of the sum: {}", sum_sq); // 25502500
println!("The difference is: {}", sum_sq - sq_sum); // 25164150
}
The answer is:
Written in Rust
fn main() {
let mut prime: i64 = 2;
for _n in 1..10002 {
next_prime(&mut prime);
}
println!("The result is: {}", prime); // 104743
}
fn is_prime(num: i64) -> bool {
for a in 2..(num / 2) {
if (num % a) == 0 {
return false;
}
}
return true;
}
fn next_prime(num: &mut i64) {
loop {
(*num) = (*num) + 1;
if is_prime(*num) {
return;
}
}
}
The answer is:
Written in Rust
fn main() {
let series = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
let nums: Vec<u64> = series.chars().map(|c| ((c as u8) - 48) as u64).collect();
let mut max_prod: u64 = 0;
for i in 0..nums.len() {
if i >= 12 {
let mut slice_prod: u64 = 1;
// nums[(i - 12)..(i + 1)].to_vec().into_iter().product();
for digs in &nums[(i - 12)..(i + 1)] {
slice_prod *= *digs;
}
max_prod = std::cmp::max(slice_prod, max_prod);
}
}
println!("The result is: {}", max_prod); // 23514624000
}
The answer is:
Written in Rust
fn main() {
for c in 200..550 {
let over = 1000 - c;
for b in 1..(over / 2) {
let a = over - b;
if (a * a + b * b) == (c * c) {
println!("a={}, b={}, c={}", a, b, c);
println!("The result is: {}", a * b * c); // 31875000
}
}
}
}
The answer is:
Written in Rust
fn main() {
// Do Erastothenes' sieve
let mut sieve: [bool; 2000001] = [true; 2000001];
sieve[0] = false;
sieve[1] = false;
let max_divisor = (sieve.len() as f64).sqrt() as i64 + 1;
for i in 2..max_divisor {
let mut j = 2;
while j * i < 2000001 {
sieve[(j * i) as usize] = false;
j += 1;
}
}
let mut sum = 0;
for i in 0..sieve.len() {
if sieve[i] {
sum += i;
}
}
println!("The result is: {}", sum); // 142913828922
}
The answer is:
Written in Rust
const GRID_WIDTH: usize = 20;
const ADJ_LEN: usize = 4;
struct NumberGrid {
numbers: [[i32; GRID_WIDTH]; GRID_WIDTH],
}
#[derive(Debug)]
struct ProductResult {
product: i32,
position: (i32, i32),
typ: String,
}
impl NumberGrid {
pub fn new(init_val: i32) -> Self {
Self {
numbers: [[init_val; GRID_WIDTH]; GRID_WIDTH],
}
}
pub fn get(&self, x: usize, y: usize) -> i32 {
self.numbers[x][y]
}
pub fn set(&mut self, x: usize, y: usize, num: i32) {
self.numbers[x][y] = num;
}
pub fn load_from_string(&mut self, num_str: &String) -> Result<&str, &str> {
if num_str.len() < 800 {
return Err("The string's length is too short");
}
for i in 0..GRID_WIDTH {
for j in 0..GRID_WIDTH {
let pos = 2 * i + (j * 40);
self.set(i, j, num_str[pos..pos + 2].parse().unwrap());
}
}
return Ok("Numbers loaded from string");
}
pub fn print_grid(&self) {
for i in 0..GRID_WIDTH {
for j in 0..GRID_WIDTH {
print!("{:#02} ", self.get(j, i));
}
print!("\n");
}
}
pub fn get_prod_right(&self, x: usize, y: usize) -> i32 {
let mut product: i32 = 1;
for i in 0..ADJ_LEN {
product *= self.get(x + i, y);
}
product
}
pub fn get_prod_down(&self, x: usize, y: usize) -> i32 {
let mut product: i32 = 1;
for i in 0..ADJ_LEN {
product *= self.get(x, y + i);
}
product
}
pub fn get_prod_diag(&self, x: usize, y: usize) -> i32 {
let mut product: i32 = 1;
for i in 0..ADJ_LEN {
product *= self.get(x + i, y + i);
}
product
}
pub fn get_prod_diag_left(&self, x: usize, y: usize) -> i32 {
let mut product: i32 = 1;
for i in 0..ADJ_LEN {
product *= self.get(x + ADJ_LEN - 1 - i, y + i);
}
product
}
pub fn get_max_prod(&self) -> ProductResult {
let mut max_prod = 0;
let mut pos: (i32, i32) = (0, 0);
let mut typ: &str = "none";
for i in 0..(GRID_WIDTH - ADJ_LEN + 1) {
for j in 0..(GRID_WIDTH - ADJ_LEN + 1) {
let mut new_prod = self.get_prod_down(i, j);
if new_prod > max_prod {
max_prod = new_prod;
pos = (i as i32, j as i32);
typ = "down";
}
new_prod = self.get_prod_right(i, j);
if new_prod > max_prod {
max_prod = new_prod;
pos = (i as i32, j as i32);
typ = "right";
}
new_prod = self.get_prod_diag(i, j);
if new_prod > max_prod {
max_prod = new_prod;
pos = (i as i32, j as i32);
typ = "diag";
}
new_prod = self.get_prod_diag_left(i, j);
if new_prod > max_prod {
max_prod = new_prod;
pos = (i as i32, j as i32);
typ = "diag_left";
}
}
}
return ProductResult {
product: max_prod,
position: pos,
typ: String::from(typ),
};
}
}
fn main() {
let mut numbers_str = String::from(
"08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48",
);
numbers_str = numbers_str.replace("\n", "");
numbers_str = numbers_str.replace(" ", "");
let mut numbers = NumberGrid::new(0);
match numbers.load_from_string(&numbers_str) {
Ok(_message) => {}
Err(err_message) => {
println!("Problem with the string: {}", err_message);
}
};
println!("The numbers in the grid");
numbers.print_grid();
let max_prod = numbers.get_max_prod();
println!(
"The greatest product of length 4 in the grid is: {:?}",
max_prod
); // 70600674
}
The result:
The
Written in Rust
fn main() {
let min_divs = 500;
let start = 12350;
let len = 50;
let every = 4;
let child = std::thread::spawn(move || {
let offset = 0;
for n in (start..(len + start)).step_by(every) {
let nn = n + offset;
if divisors(nn) * divisors(nn + 1) < 500 {
continue;
}
let tri_num = triangle_num(nn);
let divs = divisors(tri_num);
if divs > min_divs {
println!(
"The #{} triangle number is {} and it's number of divisors is {}. This is the first triangle number with over 500 divisors.",
nn, tri_num, divs
);
return (nn, tri_num, divs);
}
}
(0, 0, 0)
});
let child2 = std::thread::spawn(move || {
let offset = 1;
for n in (start..(len + start)).step_by(every) {
let nn = n + offset;
if divisors(nn) * divisors(nn + 1) < 500 {
continue;
}
let tri_num = triangle_num(nn);
let divs = divisors(tri_num);
if divs > min_divs {
println!(
"The #{} triangle number is {} and it's number of divisors is {}. This is the first triangle number with over 500 divisors.",
nn, tri_num, divs
);
return (nn, tri_num, divs);
}
}
(0, 0, 0)
});
let child3 = std::thread::spawn(move || {
let offset = 2;
for n in (start..(len + start)).step_by(every) {
let nn = n + offset;
if divisors(nn) * divisors(nn + 1) < 500 {
continue;
}
let tri_num = triangle_num(nn);
let divs = divisors(tri_num);
if divs > min_divs {
println!(
"The #{} triangle number is {} and it's number of divisors is {}. This is the first triangle number with over 500 divisors.",
nn, tri_num, divs
);
return (nn, tri_num, divs);
}
}
(0, 0, 0)
});
let child4 = std::thread::spawn(move || {
let offset = 3;
for n in (start..(len + start)).step_by(every) {
let nn = n + offset;
if divisors(nn) * divisors(nn + 1) < 500 {
continue;
}
let tri_num = triangle_num(nn);
let divs = divisors(tri_num);
if divs > min_divs {
println!(
"The #{} triangle number is {} and it's number of divisors is {}. This is the first triangle number with over 500 divisors.",
nn, tri_num, divs
);
return (nn, tri_num, divs);
}
}
(0, 0, 0)
});
let mut _res1 = child.join();
let mut _res2 = child2.join();
let mut _res3 = child3.join();
let mut _res4 = child4.join();
// The result: 76576500
// The 12375th triangle number is 76576500 and it's number of divisors is 576. This is the first triangle number with over 500 divisors.
}
#[inline(always)]
fn divisors(n: i64) -> i64 {
let mut divs: i64 = 2;
for i in 2..(n) {
if n % i == 0 {
divs += 1;
}
}
divs
}
#[inline(always)]
fn triangle_num(place: i64) -> i64 {
place * (place + 1) / 2
}
The result is:
5537376230390876637302048746832985971773659831892672 is the sum
Written in Rust, using the crate num-bigint, in the Cargo.toml:
[dependencies]
num-bigint = "0.4.0"
num-traits = "0.2"
The code:
extern crate num_bigint;
use num_bigint::BigUint;
use num_traits::{One, Zero};
fn main() {
let mut numbers_str = String::from(
"37107287533902102798797998220837590246510135740250
46376937677490009712648124896970078050417018260538
74324986199524741059474233309513058123726617309629
91942213363574161572522430563301811072406154908250
23067588207539346171171980310421047513778063246676
89261670696623633820136378418383684178734361726757
28112879812849979408065481931592621691275889832738
44274228917432520321923589422876796487670272189318
47451445736001306439091167216856844588711603153276
70386486105843025439939619828917593665686757934951
62176457141856560629502157223196586755079324193331
64906352462741904929101432445813822663347944758178
92575867718337217661963751590579239728245598838407
58203565325359399008402633568948830189458628227828
80181199384826282014278194139940567587151170094390
35398664372827112653829987240784473053190104293586
86515506006295864861532075273371959191420517255829
71693888707715466499115593487603532921714970056938
54370070576826684624621495650076471787294438377604
53282654108756828443191190634694037855217779295145
36123272525000296071075082563815656710885258350721
45876576172410976447339110607218265236877223636045
17423706905851860660448207621209813287860733969412
81142660418086830619328460811191061556940512689692
51934325451728388641918047049293215058642563049483
62467221648435076201727918039944693004732956340691
15732444386908125794514089057706229429197107928209
55037687525678773091862540744969844508330393682126
18336384825330154686196124348767681297534375946515
80386287592878490201521685554828717201219257766954
78182833757993103614740356856449095527097864797581
16726320100436897842553539920931837441497806860984
48403098129077791799088218795327364475675590848030
87086987551392711854517078544161852424320693150332
59959406895756536782107074926966537676326235447210
69793950679652694742597709739166693763042633987085
41052684708299085211399427365734116182760315001271
65378607361501080857009149939512557028198746004375
35829035317434717326932123578154982629742552737307
94953759765105305946966067683156574377167401875275
88902802571733229619176668713819931811048770190271
25267680276078003013678680992525463401061632866526
36270218540497705585629946580636237993140746255962
24074486908231174977792365466257246923322810917141
91430288197103288597806669760892938638285025333403
34413065578016127815921815005561868836468420090470
23053081172816430487623791969842487255036638784583
11487696932154902810424020138335124462181441773470
63783299490636259666498587618221225225512486764533
67720186971698544312419572409913959008952310058822
95548255300263520781532296796249481641953868218774
76085327132285723110424803456124867697064507995236
37774242535411291684276865538926205024910326572967
23701913275725675285653248258265463092207058596522
29798860272258331913126375147341994889534765745501
18495701454879288984856827726077713721403798879715
38298203783031473527721580348144513491373226651381
34829543829199918180278916522431027392251122869539
40957953066405232632538044100059654939159879593635
29746152185502371307642255121183693803580388584903
41698116222072977186158236678424689157993532961922
62467957194401269043877107275048102390895523597457
23189706772547915061505504953922979530901129967519
86188088225875314529584099251203829009407770775672
11306739708304724483816533873502340845647058077308
82959174767140363198008187129011875491310547126581
97623331044818386269515456334926366572897563400500
42846280183517070527831839425882145521227251250327
55121603546981200581762165212827652751691296897789
32238195734329339946437501907836945765883352399886
75506164965184775180738168837861091527357929701337
62177842752192623401942399639168044983993173312731
32924185707147349566916674687634660915035914677504
99518671430235219628894890102423325116913619626622
73267460800591547471830798392868535206946944540724
76841822524674417161514036427982273348055556214818
97142617910342598647204516893989422179826088076852
87783646182799346313767754307809363333018982642090
10848802521674670883215120185883543223812876952786
71329612474782464538636993009049310363619763878039
62184073572399794223406235393808339651327408011116
66627891981488087797941876876144230030984490851411
60661826293682836764744779239180335110989069790714
85786944089552990653640447425576083659976645795096
66024396409905389607120198219976047599490197230297
64913982680032973156037120041377903785566085089252
16730939319872750275468906903707539413042652315011
94809377245048795150954100921645863754710598436791
78639167021187492431995700641917969777599028300699
15368713711936614952811305876380278410754449733078
40789923115535562561142322423255033685442488917353
44889911501440648020369068063960672322193204149535
41503128880339536053299340368006977710650566631954
81234880673210146739058568557934581403627822703280
82616570773948327592232845941706525094512325230608
22918802058777319719839450180888072429661980811197
77158542502016545090413245809786882778948721859617
72107838435069186155435662884062257473692284509516
20849603980134001723930671666823555245252804609722
53503534226472524250874054075591789781264330331690",
);
numbers_str = numbers_str.replace(" ", "");
numbers_str = numbers_str.replace("\n", "");
let mut numbers: Vec<BigUint> = vec![];
for i in 0..100 {
let a = numbers_str[(i * 50)..(i * 50 + 50)]
.parse::<BigUint>()
.unwrap();
numbers.push(a);
}
let mut sum = BigUint::zero();
for i in 0..100 {
sum = sum + &(numbers[i]);
}
println!("{} is the sum", sum); // 5537376230390876637302048746832985971773659831892672
println!(
"The first ten digits: {}",
sum.to_str_radix(10)[0..10].parse::<String>().unwrap()
); // 5537376230
}
The result is:
The starting number for the longest sequence is
Written in Rust
fn main() {
let mut longest = 1;
let mut longest_len = 1;
for i in 2..1_000_001 {
let len = collatz_len(i);
if len > longest_len {
longest = i;
longest_len = len;
}
}
println!(
"The starting number for the longest sequence is {} and the length of the sequence is {}!",
longest, longest_len
);
// The starting number for the longest sequence is 837799 and the length of the sequence is 525
}
fn collatz_len(starting_num: i64) -> i64 {
if starting_num == 1 {
return 1;
}
if starting_num % 2 == 0 {
collatz_len(starting_num / 2) + 1
} else {
collatz_len(3 * starting_num + 1) + 1
}
}
The result is:
Code is not needed to solve this problem, just use an nCk calculator:
Reason: for a
The answer is:
Written in Rust, using some dependencies. Put this in the Cargo.toml:
[dependencies]
num-bigint = "0.4.0"
num-traits = "0.2.14"
apint = "0.1.0"
rug = "1.12.0"
The code:
use apint::ApInt;
use apint::Radix;
use num_bigint::BigInt;
use num_traits::{One, Zero};
use rug::{Assign, Integer};
fn main() {
let mut power: Integer = Integer::from(1);
let mult = Integer::from(2);
for _ in 0..1000 {
power *= &mult;
}
let num_str = power.to_string_radix(10);
println!("The power is {}", num_str); // 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
// Sum up the power
let mut sum = 0;
for c in num_str.chars() {
let digit = c.to_digit(10);
match digit {
Some(n) => {
sum += n;
}
None => {}
}
}
println!("The result is: {}", sum); // 1366
}
The answer is:
Written in Rust
const NUMS_STR: [&str; 21] = [
"zero",
"one",
"two",
"three",
"four",
"five",
"six",
"seven",
"eight",
"nine",
"ten",
"eleven",
"twelve",
"thirteen",
"fourteen",
"fifteen",
"sixteen",
"seventeen",
"eighteen",
"nineteen",
"twenty",
];
const TENS_STR: [&str; 10] = [
"zero", "ten", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety",
];
const HUND: &str = "hundred";
const THOUS: &str = "thousand";
fn main() {
let mut sum: usize = 0;
for i in 1..1001 {
sum += chars_in_num(i);
}
println!("The result is: {}", sum);
}
fn chars_in_num(mut n: u32) -> usize {
let n_str: String = n.to_string();
let mut ret: usize = 0;
if n >= 1000 {
return THOUS.len() + "one".len();
}
let mut hundred_part = 0;
let mut tens_part = 0;
let mut ones_part = 0;
if n >= 100 {
hundred_part = n_str.chars().next().unwrap().to_digit(10).unwrap();
ret += NUMS_STR[hundred_part as usize].len();
ret += HUND.len();
tens_part = n_str.chars().nth(1).unwrap().to_digit(10).unwrap();
ones_part = n_str.chars().nth(2).unwrap().to_digit(10).unwrap();
if tens_part > 0 || ones_part > 0 {
ret += "and".len();
}
} else if n >= 10 {
tens_part = n_str.chars().nth(0).unwrap().to_digit(10).unwrap();
ones_part = n_str.chars().nth(1).unwrap().to_digit(10).unwrap();
} else {
ones_part = n_str.chars().nth(0).unwrap().to_digit(10).unwrap();
}
n = tens_part * 10 + ones_part;
if n <= 20 && n > 0 {
ret += NUMS_STR[n as usize].len();
} else {
if tens_part != 0 {
ret += TENS_STR[tens_part as usize].len();
}
if ones_part != 0 {
ret += NUMS_STR[ones_part as usize].len();
}
}
ret
}
NOTE: Project Euler Problem 67 - Maximum path sum II, is the same challenge, but with much more possibilities, so brute force is not possible for that. We need to use a smarter method there.
The answer is:
Written in Rust
fn main() {
let nums: Vec<i32> = "75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23"
.split_whitespace()
.collect::<Vec<&str>>()
.into_iter()
.map(|s| s.parse::<i32>().unwrap())
.collect();
let mut lines = vec![(&nums[0..1]).to_vec()];
for i in 1..=14 {
lines.push((&nums[sums(i)..sums(i + 1)]).to_vec());
}
lines.reverse();
while lines.len() > 1 {
for i in 0..lines[1].len() {
let v1 = lines[0][i];
let v2 = lines[0][i + 1];
lines[1][i] += std::cmp::max(v1, v2);
}
lines.remove(0);
}
println!("The result is: {}", lines[0][0]); // 1074
}
fn sums(n: i32) -> usize {
let mut ret: usize = 0;
for i in 1..=n {
ret += i as usize;
}
ret
}
The answer is:
Written in Rust
const MONTHLENS: [i16; 12] = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];
const MONTHLENS_LEAP: [i16; 12] = [31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];
#[derive(Debug)]
struct Date {
year: i16,
month: i16,
day: i16,
weekday: i16,
}
impl Date {
fn new() -> Date {
return Date {
year: 1900,
day: 0,
month: 0,
weekday: 0,
};
}
fn increment(&mut self) {
self.increment_day();
self.increment_weekday();
}
fn increment_month(&mut self) {
self.month += 1;
if self.month >= 12 {
self.month = 0;
self.year += 1;
}
}
fn increment_day(&mut self) {
let past_day = self.day;
self.day += 1;
self.day %= self.current_month_lenght();
if self.day < past_day {
self.increment_month();
}
}
fn increment_weekday(&mut self) {
self.weekday = (self.weekday + 1) % 7;
}
fn is_first_day_of_month(&self) -> bool {
self.day == 0
}
fn is_sunday(&self) -> bool {
self.weekday == 6
}
fn current_month_lenght(&self) -> i16 {
if self.is_leap() {
return MONTHLENS_LEAP[self.month as usize];
}
return MONTHLENS[self.month as usize];
}
fn is_leap(&self) -> bool {
if (self.year % 400) == 0 {
return true;
}
if (self.year % 100) == 0 {
return false;
}
if (self.year % 4) == 0 {
return true;
}
false
}
}
fn main() {
let mut day = Date::new();
let mut dd = 0;
while day.year < 2001 {
day.increment();
if day.is_sunday() && day.is_first_day_of_month() && day.year > 1900 {
dd += 1;
}
}
println!("The result is: {}", dd); // 171
}
The answer is:
Written in JavaScript
let s = 1n;
for(let i = 1n;i<=100n;i++){
s*=i;
}
console.log("The result is: " + s.toString().split('').reduce((prev, curr)=>(Number.parseInt(curr)+prev), 0));
// 648
The answer is:
Written in Rust
fn main() {
let mut sum = 0;
for i in 1..=10000 {
if isAmicable(i) {
sum += i;
}
}
println!("The result is: {}", sum); // 31626
}
fn d(a: i32) -> i32 {
let mut sum: i32 = 0;
for i in 1..=(a / 2) {
if a % i == 0 {
sum += i;
}
}
sum
}
fn isAmicable(a: i32) -> bool {
let b = d(a);
let db = d(b);
b != a && db == a
}
The answer is:
Written in Rust
fn main() {
let mut names = vec![
"MARY",
"PATRICIA",
"LINDA",
"BARBARA",
"ELIZABETH",
"JENNIFER",
// .............
// Most of the names are omitted here, in order to not increase file size
"DARELL",
"BRODERICK",
"ALONSO",
];
names.sort();
let mut sum: u64 = 0;
for i in 0..names.len() {
let mut sub_sum: u64 = 0;
for c in names[i].chars() {
sub_sum += ((c as u8) - 64) as u64;
}
sum += sub_sum * ((i as u64) + 1);
}
println!("The result is: {}", sum); // 871198282
}
The answer is:
Written in Rust
const MAX_TO_FIND: u32 = 28123;
fn main() {
let mut abundantness = [false; MAX_TO_FIND as usize];
for i in 0..MAX_TO_FIND {
let a: u32 = i + 1;
abundantness[i as usize] = is_abundant(a);
}
let mut abundants = Vec::<u32>::new();
for i in 0..MAX_TO_FIND {
if abundantness[i as usize] {
abundants.push(i + 1);
}
}
println!("Abundant numbers determined, {} found", abundants.len());
let mut is_sum_of_abundants = [false; MAX_TO_FIND as usize];
for i in 0..abundants.len() {
for j in i..abundants.len() {
let n = abundants[i] + abundants[j];
if n <= MAX_TO_FIND {
is_sum_of_abundants[(n - 1) as usize] = true;
}
}
}
let mut sum: u32 = 0;
for i in 0..MAX_TO_FIND {
if !is_sum_of_abundants[i as usize] {
sum += i + 1;
}
}
println!("The result is: {}", sum); // 4179871
}
fn is_perfect(a: u32) -> bool {
let divisors = get_divisors(a);
let mut sum: u32 = 0;
for i in divisors {
sum += i;
}
sum == a
}
fn is_abundant(a: u32) -> bool {
let divisors = get_divisors(a);
let mut sum: u32 = 0;
for i in divisors {
sum += i;
}
sum > a
}
fn is_deficient(a: u32) -> bool {
let divisors = get_divisors(a);
let mut sum: u32 = 0;
for i in divisors {
sum += i;
}
sum > a
}
fn get_divisors(a: u32) -> Vec<u32> {
let mut ret = Vec::<u32>::new();
for i in 1..=(a / 2) {
if (a % i) == 0 {
ret.push(i);
}
}
ret
}
The answer is:
Written in Rust, using the itertools crate. Dependencies in Cargo.toml:
[dependencies]
itertools = "0.10.2"
The code:
use itertools::Itertools;
fn main() {
let items = vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
let mut i: u32 = 0;
for perm in items.iter().permutations(items.len()).unique() {
i = i + 1;
if i == 1_000_000 {
println!("The millionth lexiographic permutation is: {:?}", perm);
println!(
"Short form: {:?}",
perm.iter().fold(String::from(""), |accum, item| {
accum + (format!("{a}", a = item)).as_str() // 2783915460
})
);
break;
}
}
}
The answer is:
Written in Rust
fn main() {
let mut fibos: Vec<Vec<u8>> = vec![vec![1], vec![1]];
let mut idx = 2;
while fibos.last().unwrap().len() < 1000 {
fibos.push(add_strs_as_ints(
&fibos[fibos.len() - 1],
&fibos[fibos.len() - 2],
));
idx += 1;
}
println!(
"The index of the Fibonacci number is {}, with a length {}",
fibos.len() - 1,
fibos.last().unwrap().len()
);
}
// Will only work with positive ints
fn add_strs_as_ints(a: &[u8], b: &[u8]) -> Vec<u8> {
let mut a: Vec<u8> = a.to_vec();
let mut b: Vec<u8> = b.to_vec();
while a.len() < b.len() || a[0] != 0 {
a.insert(0, 0);
}
while a.len() > b.len() {
b.insert(0, 0);
}
let mut result: Vec<u8> = vec![0];
while result.len() < b.len() {
result.insert(0, 0);
}
for i in 0..a.len() {
result[i] = a[i] + b[i];
}
for i in (0..result.len()).rev() {
while result[i] > 10 {
result[i] -= 10;
result[i - 1] += 1;
}
}
while result[0] == 0 {
result.remove(0);
}
result
}
fn char_to_num(c: char) -> u8 {
match c {
'0' => 0,
'1' => 1,
'2' => 2,
'3' => 3,
'4' => 4,
'5' => 5,
'6' => 6,
'7' => 7,
'8' => 8,
'9' => 9,
_ => 0,
}
}
The answer is:
Written in Rust
use std::ops::Index;
fn is_prime(n: u64) -> bool {
for i in 2..(n / 2) {
if n % i == 0 {
return false;
}
}
true
}
fn manual_1_over_cycle_length(d: u64) -> u64 {
let mut results: Vec<(u64, u64)> = vec![];
let mut num = 1;
while num != 0 {
let digit = num / d;
num = num - digit * d;
let next_result = (digit, num);
if results
.iter()
.any(|re| re.0 == next_result.0 && re.1 == next_result.1)
{
let idx = results
.iter()
.position(|re| re.0 == next_result.0 && re.1 == next_result.1)
.unwrap();
return (results.iter().count() - idx).try_into().unwrap();
}
results.push(next_result);
num *= 10;
}
0
}
fn main() {
let repeating_lens = (1..1000)
.map(|d| (manual_1_over_cycle_length(d), d))
.max()
.unwrap();
println!("The number with the longest repeating sequence is {} and the length of the sequence is {}!", repeating_lens.1, repeating_lens.0);
}
The answer is:
Written in Rust
use itertools::Itertools;
const PRIME_SIEVE_SIZE: usize = 1_000_000;
fn main() {
let mut primes: [bool; PRIME_SIEVE_SIZE] = [true; PRIME_SIEVE_SIZE];
let mut n = 2;
while n <= (PRIME_SIEVE_SIZE / 2) {
let mut i = 2 * n;
while i < PRIME_SIEVE_SIZE {
primes[i] = false;
i += n;
}
n += 1;
}
let is_prime = |num: usize| {
if num < PRIME_SIEVE_SIZE {
return primes[num];
} else {
return !(2..(num / 2)).any(|div| num % div == 0);
}
};
let (a_max, b_max, n_max) = (-999i64..1000)
.cartesian_product(-1000..1001)
.map(|(a, b)| {
let mut n = 0;
let mut curr = n * n + a * n + b;
if curr <= 0 {
return (a, b, 0);
}
while is_prime(curr as usize) {
n += 1;
curr = n * n + a * n + b;
if curr <= 0 {
return (a, b, 0);
}
}
(a, b, n)
})
.max_by(|(_, _, n1), (_, _, n2)| n1.cmp(n2))
.unwrap();
println!("The sequence with the biggest number of consecutive primes: a={}, b={}, number of primes={}", a_max, b_max, n_max);
println!("a * b = {}", a_max * b_max)
}
The answer is:
Written in Rust
fn main() {
let mut square_width = 3;
let max_square_width = 1001;
let mut corner_num = 1;
let mut sum = 0;
while square_width <= max_square_width {
for _ in 0..4 {
sum += corner_num;
println!("{}", corner_num);
corner_num += square_width - 1;
}
square_width += 2;
}
sum += corner_num;
println!("The result is: {}", sum); // 669171001
}
The answer is:
Written in Rust, using the itertools crate. Put this in Cargo.toml:
[dependencies]
itertools = "0.10.3"
The code:
use itertools::Itertools;
const FIRST_PRIMES: [u32; 25] = [
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,
];
#[derive(PartialEq, Clone, Eq, Hash, Debug)]
struct PrimeExp {
prime_coeffs: [u32; 25],
}
impl PrimeExp {
fn from(mut num: u32) -> PrimeExp {
let mut coeffs: [u32; 25] = [0; 25];
for (i, prime) in FIRST_PRIMES.iter().enumerate() {
while num % prime == 0 {
num /= prime;
coeffs[i] += 1;
}
if num == 1 {
break;
}
}
Self {
prime_coeffs: coeffs,
}
}
fn pow(&self, exp: u32) -> Self {
let mut coeffs: [u32; 25] = [0; 25];
for (i, c) in self.prime_coeffs.iter().enumerate() {
coeffs[i] = c * exp;
}
Self {
prime_coeffs: coeffs,
}
}
}
fn main() {
let prods: Vec<PrimeExp> = (2..=100)
.map(|n| PrimeExp::from(n))
.cartesian_product(2..=100)
.map(|(a, b)| a.pow(b))
.unique()
.collect();
println!("The number of distinct terms: {}", prods.len()); // 9183
}
The answer is:
Written in Rust
#[inline(always)]
fn to_digits(num: u32) -> [u32; 6] {
let mut result: [u32; 6] = [0; 6];
result[0] = num % 10;
result[1] = (num % 100) / 10;
result[2] = (num % 1000) / 100;
result[3] = (num % 10000) / 1000;
result[4] = (num % 100000) / 10000;
result[5] = (num % 1000000) / 100000;
result
}
#[inline(always)]
fn to_sum_of_5powers(num: u32) -> u32 {
let mut result: u32 = 0;
result += (num % 10).pow(5);
result += ((num % 100) / 10).pow(5);
result += ((num % 1000) / 100).pow(5);
result += ((num % 10000) / 1000).pow(5);
result += ((num % 100000) / 10000).pow(5);
result += ((num % 1000000) / 100000).pow(5);
result
}
fn main() {
// It is certainly enough to go until 355_000 (since 9^5 times 6 < 355k)
// So we need to consider 6 digits
let sum = (2u32..355_000)
.filter(|num| *num == to_sum_of_5powers(*num))
.sum::<u32>();
println!("The result is: {}", sum); // 443839
}
The answer is:
Written in Rust, using the itertools crate. Put this in Cargo.toml:
[dependencies]
itertools = "0.10.3"
The code:
use itertools::Itertools;
const VALUES: [u16; 8] = [1, 2, 5, 10, 20, 50, 100, 200];
fn main() {
let ways = VALUES
.iter()
.map(|val| 0..(200 / val))
.multi_cartesian_product()
.filter(|coins| {
coins
.iter()
.zip(VALUES.iter())
.map(|(a1, a2)| a1 * a2)
.sum::<u16>()
== 200
})
.count()
+ 8;
println!("The result is: {}", ways); // 73682
}
The answer is:
List of the products:
Written in Rust, using the itertools crate. Put this in Cargo.toml:
[dependencies]
itertools = "0.10.3"
The code:
use itertools::Itertools;
fn main() {
let digits_char = ['1', '2', '3', '4', '5', '6', '7', '8', '9'];
let sum_iter = digits_char
.into_iter()
.permutations(9)
.map(|num| {
let string_ver: String = num.iter().collect();
let (start, prod_str) = string_ver.split_at(5);
let prod = prod_str.parse::<usize>().unwrap();
let (p1, p2) = start.split_at(2);
if p1.parse::<usize>().unwrap() * p2.parse::<usize>().unwrap() == prod {
return prod;
}
let (p1, p2) = start.split_at(3);
if p1.parse::<usize>().unwrap() * p2.parse::<usize>().unwrap() == prod {
return prod;
}
let (p1, p2) = start.split_at(1);
if p1.parse::<usize>().unwrap() * p2.parse::<usize>().unwrap() == prod {
return prod;
}
let (p1, p2) = start.split_at(4);
if p1.parse::<usize>().unwrap() * p2.parse::<usize>().unwrap() == prod {
return prod;
}
return 0;
})
.filter(|n| *n != 0)
.chain({
digits_char
.into_iter()
.permutations(9)
.map(|num| {
let string_ver: String = num.iter().collect();
let (start, prod_str) = string_ver.split_at(4);
let prod = prod_str.parse::<usize>().unwrap();
let (p1, p2) = start.split_at(2);
if p1.parse::<usize>().unwrap() * p2.parse::<usize>().unwrap() == prod {
return prod;
}
let (p1, p2) = start.split_at(1);
if p1.parse::<usize>().unwrap() * p2.parse::<usize>().unwrap() == prod {
return prod;
}
let (p1, p2) = start.split_at(3);
if p1.parse::<usize>().unwrap() * p2.parse::<usize>().unwrap() == prod {
return prod;
}
return 0;
})
.filter(|n| *n != 0)
})
.chain({
digits_char
.into_iter()
.permutations(9)
.map(|num| {
let string_ver: String = num.iter().collect();
let (start, prod_str) = string_ver.split_at(6);
let prod = prod_str.parse::<usize>().unwrap();
for i in 1..6 {
let (p1, p2) = start.split_at(i);
if p1.parse::<usize>().unwrap() * p2.parse::<usize>().unwrap() == prod {
return prod;
}
}
return 0;
})
.filter(|n| *n != 0)
})
.unique();
println!(
"The products are: {:?}",
sum_iter.clone().collect::<Vec<usize>>()
); // [5796, 4396, 7632, 6952, 5346, 7254, 7852]
let sum = sum_iter.sum::<usize>();
println!("Their sum is: {}", sum); // 45228
}
The result is:
Written in Rust, using the itertools package, by putting this into the Cargo.toml file:
[dependencies]
itertools = "0.10.3"
The code:
use itertools::Itertools;
const PRIMES: [isize; 25] = [
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 to_prime_factors(mut num: isize) -> [usize; 25] {
let mut factors: [usize; 25] = [0; 25];
let mut idx = 0;
while idx < factors.len() {
let fact = PRIMES[idx];
while num % fact == 0 {
factors[idx] += 1;
num /= fact;
}
idx += 1;
}
factors
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
struct Rational {
num: isize,
den: isize,
}
impl Rational {
fn new(num: isize, den: isize) -> Self {
Self { num, den }
}
fn simplify(&self) -> Self {
let mut num_factors = to_prime_factors(self.num);
let mut den_factors = to_prime_factors(self.den);
num_factors
.iter_mut()
.zip(den_factors.iter_mut())
.for_each(|(num_fact, den_fact)| {
let min_fact = std::cmp::min(*num_fact, *den_fact);
*num_fact -= min_fact;
*den_fact -= min_fact;
});
let num = num_factors
.iter()
.enumerate()
.map(|(idx, f)| PRIMES[idx].pow(*f as u32))
.fold(1, |curr, prev| curr * prev);
let den = den_factors
.iter()
.enumerate()
.map(|(idx, f)| PRIMES[idx].pow(*f as u32))
.fold(1, |curr, prev| curr * prev);
Self { num, den }
}
fn simplify_digits(&self) -> Self {
let mut num_digits = [self.num / 10, self.num % 10];
let mut den_digits = [self.den / 10, self.den % 10];
for digit in [1isize, 2, 3, 4, 5, 6, 7, 8, 9].iter() {
while num_digits.contains(digit) && den_digits.contains(digit) {
let pos = num_digits.iter().position(|a| *a == *digit);
if pos.is_some() {
num_digits[pos.unwrap()] = 1234;
}
let pos = den_digits.iter().position(|a| *a == *digit);
if pos.is_some() {
den_digits[pos.unwrap()] = 1234;
}
}
}
let new_num = num_digits
.into_iter()
.filter(|a| *a != 1234)
.rev()
.enumerate()
.map(|(idx, dig)| dig * 10_isize.pow(idx as u32))
.sum::<isize>();
let new_den = den_digits
.into_iter()
.filter(|a| *a != 1234)
.rev()
.enumerate()
.map(|(idx, dig)| dig * 10_isize.pow(idx as u32))
.sum::<isize>();
let ret = Self {
num: new_num,
den: new_den,
};
if ret.num == 0 || ret.den == 0 {
return *self;
}
ret
}
fn enum_bigger(&self) -> Self {
if self.num < self.den {
return Self {
num: self.den,
den: self.num,
};
} else {
return *self;
}
}
fn enum_smaller(&self) -> Self {
if self.num > self.den {
return Self {
num: self.den,
den: self.num,
};
} else {
return *self;
}
}
fn mult(&self, other: &Self) -> Self {
Self {
num: self.num * other.num,
den: self.den * other.den,
}
}
fn to_pretty_string(&self) -> String {
format!("{}/{}", self.num, self.den)
}
}
fn main() {
let result = (10..=99)
.cartesian_product(10..=99)
.map(|(a, b)| Rational::new(a, b))
.filter(|rat| {
*rat != rat.simplify_digits() && rat.simplify() == rat.simplify_digits().simplify()
})
.map(|r| Rational::enum_smaller(&r))
.unique()
.fold(Rational { num: 1, den: 1 }, |prev, next| prev.mult(&next));
println!(
"The rationals that simplify both ways are: {:?}",
(10..=99)
.cartesian_product(10..=99)
.map(|(a, b)| Rational::new(a, b))
.filter(|rat| {
*rat != rat.simplify_digits() && rat.simplify() == rat.simplify_digits().simplify()
})
.map(|r| Rational::enum_smaller(&r))
.unique()
.map(|r| r.to_pretty_string())
.collect::<Vec<String>>()
); // ["16/64", "19/95", "26/65", "49/98"]
println!("Their product: {}", result.to_pretty_string()); // 387296/38729600
println!("Simplified: {}", result.simplify().to_pretty_string()); // 1/100
println!("The result: {}", result.simplify().den); // 100
}
The answer is:
Written in Rust
#[inline(always)]
fn digit_factorial(digit: usize) -> usize {
match digit {
0 => 1,
1 => 1,
2 => 2,
3 => 6,
4 => 24,
5 => 120,
6 => 720,
7 => 5040,
8 => 40320,
9 => 362880,
_ => 0,
}
}
fn into_digits(num: usize) -> [usize; 7] {
let mut ret: [usize; 7] = [0; 7];
ret[0] = num / 1_000_000;
ret[1] = (num % 1_000_000) / 100_000;
ret[2] = (num % 100000) / 10000;
ret[3] = (num % 10000) / 1000;
ret[4] = (num % 1000) / 100;
ret[5] = (num % 100) / 10;
ret[6] = num % 10;
let mut sum = ret[0];
let mut idx = 0;
while sum == 0 {
ret[idx] = 100;
idx += 1;
sum += ret[idx];
}
ret
}
fn main() {
let curius_numbers: Vec<usize> = (10..2_500_000)
.filter(|num| {
into_digits(*num)
.map(|digit| digit_factorial(digit))
.iter()
.sum::<usize>()
== *num
})
.collect();
println!("The curious numbers: {:?}", curius_numbers); // [145, 40585]
println!("The result is: {:?}", curius_numbers.iter().sum::<usize>()); // 40730
}
The result is:
Written in Rust
const fn create_prime_table() -> [bool; 1_000_000] {
let mut prime_table: [bool; 1_000_000] = [true; 1_000_000];
prime_table[0] = false;
prime_table[1] = false;
// prime_table[2] = true;
let mut i = 2;
while i < 500_000 {
if !prime_table[i] {
i += 1;
continue;
}
let mut cc = 2 * i;
while cc < 1_000_000 {
prime_table[cc] = false;
cc += i;
}
i += 1;
}
prime_table
}
fn cyc_rotate(input: &String) -> String {
let tmp_last = input.chars().last().unwrap();
tmp_last.to_string() + &input.get(0..(input.len() - 1)).unwrap().to_string()
}
fn is_circular_prime(num: usize, prime_table: &[bool; 1_000_000]) -> bool {
let as_str = num.to_string();
let mut rotated = cyc_rotate(&as_str);
let mut rots = vec![as_str.clone(), rotated.clone()];
while as_str.ne(&rotated) {
rotated = cyc_rotate(&rotated);
rots.push(rotated.clone());
}
rots.iter().all(|str| {
let num = str.parse::<usize>().unwrap();
prime_table[num]
})
}
fn main() {
let prime_table: [bool; 1_000_000] = create_prime_table();
let prime_list: Vec<usize> = prime_table
.iter()
.enumerate()
.filter_map(|(idx, is_prime)| {
if *is_prime {
return Some(idx);
} else {
return None;
}
})
.filter(|prime| is_circular_prime(*prime, &prime_table))
.collect();
println!("The list of circular primes: {:?}", prime_list); // [2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 197, 199, 311, 337, 373, 719, 733, 919, 971, 991, 1193, 1931, 3119, 3779, 7793, 7937, 9311, 9377, 11939, 19391, 19937, 37199, 39119, 71993, 91193, 93719, 93911, 99371, 193939, 199933, 319993, 331999, 391939, 393919, 919393, 933199, 939193, 939391, 993319, 999331]
println!("The result is: {}", prime_list.len()); // 55
}
The answer is:
Written in Rust
fn is_doublebase_palindrome(n: usize) -> bool {
let bin_string = format!("{n:b}");
let decimal_string = format!("{n}");
bin_string == bin_string.chars().rev().collect::<String>()
&& decimal_string == decimal_string.chars().rev().collect::<String>()
}
fn main() {
let sum = (1..=1_000_000)
.filter_map(|num| {
let is_it = is_doublebase_palindrome(num);
if is_it {
return Some(num);
}
None
})
.sum::<usize>();
println!("{}", sum); // 872187
}
The answer is:
Written in C++:
#include <cmath>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
const unsigned int MAX = 1000000;
bool primeTable[MAX];
bool isPrime(unsigned int n) {
if (n < MAX) {
return primeTable[n];
}
for (unsigned int i = 2; i <= sqrt(n); ++i) {
if (n % i == 0) {
return false;
}
}
return true;
}
bool isTruncatablePrime(unsigned int n) {
if (!isPrime(n))
return false;
string asStr = to_string(n);
for (unsigned int i = 1; i < asStr.size(); i++) {
if (!isPrime(stoi(asStr.substr(i))) || !isPrime(stoi(asStr.substr(0, i))))
return false;
}
return true;
}
int main() {
fill(primeTable, primeTable + MAX, true);
primeTable[0] = false;
primeTable[1] = false;
for (int i = 2; i < MAX; i++) {
for (int j = i + i; j < MAX; j += i) {
primeTable[j] = false;
}
}
auto truncatablePrimes = vector<unsigned int>();
unsigned int at = 11;
while (truncatablePrimes.size() < 11) {
if (isTruncatablePrime(at)) {
truncatablePrimes.push_back(at);
}
at++;
}
auto sum = accumulate(truncatablePrimes.begin(), truncatablePrimes.end(), 0);
cout << sum << endl; // 748317
}
The answer is: 932718654
Written in C++:
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>
// Returns the pandigital product if it exists, otherwise 0.
uint64_t getPandigital(const uint32_t n) {
auto num = n;
std::string s = std::to_string(num);
while (s.length() < 9) {
num += n;
s += std::to_string(num);
}
if (s.length() != 9)
return 0;
bool digits[9] = {false, false, false, false, false,
false, false, false, false};
for (const auto c : s) {
if (c == '0')
return 0;
if (digits[c - '1'])
return 0;
digits[c - '1'] = true;
}
return std::stoull(s);
}
int main() {
std::vector<uint64_t> pandigitals;
for (uint32_t i = 1; i < 100000; i++) {
auto p = getPandigital(i);
if (p != 0)
pandigitals.push_back(p);
}
std::sort(pandigitals.begin(), pandigitals.end());
std::cout << pandigitals.back() << std::endl; // 932718654
}
The answer is:
Written in C++:
#include <algorithm>
#include <array>
#include <iostream>
#include <vector>
int main() {
std::array<uint32_t, 800> squares;
for (auto i = 0; i < 800; i++)
squares[i] = i * i;
auto p_sol = std::array<uint16_t, 10000>();
for (auto a = 0; a < 400; a++) {
for (auto b = a; b < 400; b++) {
auto sqprod = a * a + b * b;
auto ptr = std::find(squares.begin(), squares.end(), sqprod);
if (ptr == squares.end())
continue;
auto sqrtprod = std::distance(squares.begin(), ptr);
p_sol[a + b + sqrtprod] += 1;
}
}
auto maxPtr = std::max_element(p_sol.begin(), p_sol.end());
auto maxIdx = std::distance(p_sol.begin(), maxPtr);
std::cout << "The p with max solutions is p=" << maxIdx << '\n'; // 840
}
The answer is:
Written in C++:
#include <algorithm>
#include <iostream>
#include <string>
int main() {
std::string fracDigits("");
auto n = 0;
while (fracDigits.size() <= 1000000) {
fracDigits += std::to_string(n);
n++;
}
auto place = 1;
long long result = 1;
while (place <= 1000000) {
result *= (fracDigits[place] - '0');
place *= 10;
}
std::cout << result << '\n'; // 210
}
The answer is:
Written in C++:
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
const long MAX = 10000000; // Enough to go until 10 million, since pandigitals
// over it are guarateed to be divisible with 9 and 3
bool isPandigital(size_t num) {
std::string digits = std::to_string(num);
std::sort(digits.begin(), digits.end(), std::greater_equal<char>());
if (digits[digits.length() - 1] != '1')
return false;
for (auto i = 1; i < digits.size(); i++)
if (digits[i - 1] - digits[i] != 1)
return false;
return true;
}
int main() {
std::vector<bool> table(MAX);
std::fill(table.begin(), table.end(), true);
table[0] = table[1] = false;
for (auto i = 2; i < MAX / 2; i++)
for (auto j = i + i; j < MAX; j += i)
table[j] = false;
std::vector<size_t> primes;
for (auto i = 0; i < table.size(); i++)
if (table[i])
primes.push_back(i);
for (auto i = primes.rbegin(); i != primes.rend(); i++) {
auto prime = *i;
if (isPandigital(prime)) {
std::cout << "The following is the biggest pandigital prime: " << prime
<< '\n';
break;
}
}
}
The answer is:
Written in C++:
#include <algorithm>
#include <cmath>
#include <fstream>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
bool isTriangleNumber(int32_t num) {
int32_t lower = std::sqrt((double)num * 2);
return ((lower * (lower + 1)) / 2) == num;
}
int main() {
std::ifstream input("words.txt");
std::string fileText;
input >> fileText;
input.close();
std::vector<int32_t> values;
bool isInWord = false;
for (char c : fileText) {
if (c == '"') {
if (!isInWord) {
values.push_back(0);
c = 'A' - 1;
isInWord = true;
} else {
isInWord = false;
}
}
if (isInWord)
values[values.size() - 1] += (c - 'A' + 1);
}
std::vector<int32_t> filtered;
std::copy_if(values.begin(), values.end(), std::back_inserter(filtered),
isTriangleNumber);
std::cout << filtered.size() << '\n'; // 162
}
The answer is:
Written in C++:
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <vector>
bool isEligible(const std::array<uint8_t, 10> &digits) {
if (digits[0] == 0)
return false;
if (digits[3] % 2 != 0)
return false;
if ((digits[2] + digits[3] + digits[4]) % 3 != 0)
return false;
if (digits[5] != 5 && digits[5] != 0)
return false;
if ((digits[4] * 100 + digits[5] * 10 + digits[6]) % 7 != 0)
return false;
if ((digits[5] * 100 + digits[6] * 10 + digits[7]) % 11 != 0)
return false;
if ((digits[6] * 100 + digits[7] * 10 + digits[8]) % 13 != 0)
return false;
if ((digits[7] * 100 + digits[8] * 10 + digits[9]) % 17 != 0)
return false;
return true;
}
int main() {
std::array<uint8_t, 10> cs{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
std::sort(cs.begin(), cs.end());
long sum = 0;
do {
if (isEligible(cs)) {
std::string other;
std::copy(cs.begin(), cs.end(), std::back_inserter(other));
std::transform(other.begin(), other.end(), other.begin(),
[](uint8_t v) { return v + '0'; });
sum += std::stol(other);
}
} while (std::next_permutation(cs.begin(), cs.end()));
std::cout << sum << '\n';
}
The answer is:
Written in C++:
#include <algorithm>
#include <array>
#include <iostream>
#include <vector>
const size_t AMOUNT = 10000;
int main() {
std::array<int64_t, AMOUNT> pentagonals;
for (auto i = 1; i < AMOUNT; i++)
pentagonals[i] = (i * (3 * i - 1)) / 2;
std::vector<bool> pentagonalTable(pentagonals[pentagonals.size() - 1]);
std::fill(pentagonalTable.begin(), pentagonalTable.end(), false);
for (auto i = 1; i < AMOUNT; i++)
pentagonalTable[pentagonals[i]] = true;
/*
for (auto i = 1; i < AMOUNT; i++)
for (auto j = i + 1; j < AMOUNT - i; j++)
if (std::find(pentagonals.begin(), pentagonals.end(),
pentagonals[i] + pentagonals[j]) != pentagonals.end() &&
std::find(pentagonals.begin(), pentagonals.end(),
std::abs(pentagonals[i] - pentagonals[j])) !=
pentagonals.end())
std::cout << "D = " << std::abs(pentagonals[i] - pentagonals[j])
<< ", with i = " << i << " and j = " << j << '\n'; // D =
5482660, with i = 1020 and j = 2167
*/
auto minD = 0;
[&] {
for (auto i = 1; i < AMOUNT; i++)
for (auto j = i + 1; j < AMOUNT - i; j++)
if (pentagonalTable[pentagonals[i] + pentagonals[j]] &&
pentagonalTable[std::abs(pentagonals[i] - pentagonals[j])])
if (minD > std::abs(pentagonals[i] - pentagonals[j]) || minD == 0) {
minD = std::abs(pentagonals[i] - pentagonals[j]);
std::cout << "D = " << std::abs(pentagonals[i] - pentagonals[j])
<< ", with i = " << i << " and j = " << j << '\n';
return;
}
}();
std::cout << minD << '\n'; // 5482660
}
The answer is:
Written in C++:
#include <algorithm>
#include <iostream>
template <typename T> inline T triangle(T n) { return (n * (n + 1)) / 2; }
template <typename T> inline T pentagonal(T n) { return (n * (3 * n - 1)) / 2; }
template <typename T> inline T hexagonal(T n) { return (n * (2 * n - 1)); }
int main() {
long triIdx = 1, pentIdx = 1, hexIdx = 1;
for (long i = 0; i < 1000000; i++) {
auto tri = triangle(triIdx);
auto pent = pentagonal(pentIdx);
auto hex = hexagonal(hexIdx);
if (tri == pent && tri == hex) {
std::cout << tri << '\n';
triIdx++;
pentIdx++;
hexIdx++;
} else if (tri <= pent && tri <= hex)
triIdx++;
else if (pent <= tri && pent <= hex)
pentIdx++;
else if (hex <= tri && hex <= pent)
hexIdx++;
}
// The third number printed will be the solution
}
The answer is:
Written in C++:
#include <algorithm>
#include <array>
#include <iostream>
#include <vector>
const size_t TABLESIZE = 1000000;
const size_t SQUAREAMOUNT = 10000;
int main() {
std::vector<bool> primeT(TABLESIZE);
std::fill(primeT.begin(), primeT.end(), true);
primeT[0] = primeT[1] = false;
for (auto i = 2; i < TABLESIZE / 2; i++) {
for (auto j = i * i; j < TABLESIZE; j += i)
primeT[j] = false;
}
std::vector<uint64_t> primes;
for (auto i = 2; i < TABLESIZE; i++)
if (primeT[i])
primes.push_back(i);
std::vector<uint64_t> squares;
for (auto i = 1; i < SQUAREAMOUNT; i++) {
squares.push_back(2 * i * i);
}
for (auto i = 9; i < 10000; i += 2) {
if (primeT[i])
continue;
if (!([&] {
for (auto j = 0; primes[j] <= i; j++)
for (auto k = 0; squares[k] + primes[j] <= i; k++)
if (primes[j] + squares[k] == i)
return true;
return false;
})()) {
std::cout << i << '\n'; // 5777
break;
};
}
}
The answer is:
Written in C++:
#include <array>
#include <iostream>
#include <optional>
#include <set>
#include <vector>
const size_t TABLESIZE = 1000000;
std::array<bool, TABLESIZE> primeTable() {
std::array<bool, TABLESIZE> primeT;
for (auto i = 0; i < primeT.size(); i++)
primeT[i] = true;
primeT[0] = primeT[1] = false;
for (auto i = 2; i < primeT.size() / 2; i++)
for (auto j = i + i; j < primeT.size(); j += i)
primeT[j] = false;
return primeT;
}
std::array<bool, TABLESIZE> primeT;
std::vector<uint32_t> primes;
std::optional<std::array<uint32_t, 4>> quadFactors(uint32_t num) {
std::vector<uint32_t> results;
for (auto i = 0; primes[i] < num / 2 && results.size() < 5; i++) {
if (num % primes[i] == 0)
results.push_back(primes[i]);
}
if (results.size() == 4)
return std::optional<std::array<uint32_t, 4>>(
{results[0], results[1], results[2], results[3]});
return std::nullopt;
}
int main() {
primeT = primeTable();
for (auto i = 2; i < primeT.size(); i++)
if (primeT[i])
primes.push_back(i);
auto conseqCount = 0;
for (auto i = 1; i < 1000000; i++) {
auto ret = quadFactors(i);
if (ret) {
conseqCount++;
} else
conseqCount = 0;
if (conseqCount == 4) {
std::cout << i - 3 << '\n'; // 134043
break;
}
}
}
The answer is:
Written in C++:
#include <iostream>
int main() {
uint64_t result = 0;
for (auto i = 1; i <= 1000; i++) {
uint64_t subres = 1;
for (auto j = 0; j < i; j++) {
subres *= i;
subres %= 10000000000;
}
result += subres;
result %= 10000000000;
}
std::cout << result % 10000000000 << '\n'; // 9110846700
}
The answer is:
Written in C++:
#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <string>
#include <vector>
const size_t TABLESIZE = 11000;
int main() {
std::array<bool, TABLESIZE> primeT;
std::fill(primeT.begin(), primeT.end(), true);
primeT[0] = primeT[1] = false;
for (auto i = 2; i < TABLESIZE / 2; i++) {
for (auto j = i * i; j < TABLESIZE; j += i)
primeT[j] = false;
}
std::vector<int> primes;
std::vector<std::string> primesStr;
for (auto i = 2; i < TABLESIZE; i++)
if (primeT[i] && i > 999 && i < 10000) {
primes.push_back(i);
primesStr.push_back(std::to_string(i));
}
for (auto i = 0; i < primes.size(); i++) {
std::vector<int> seq = {std::stoi(primesStr[i])};
while (std::next_permutation(primesStr[i].begin(), primesStr[i].end()))
if (primeT[std::stoi(primesStr[i])])
seq.push_back(std::stoi(primesStr[i]));
std::sort(seq.begin(), seq.end());
if (seq.size() == 3 && seq[0] - seq[1] == seq[1] - seq[2]) {
std::cout << seq[0] << seq[1] << seq[2] << '\n'; // 296962999629
}
}
}
The answer is:
Written in C++:
#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <string>
#include <vector>
const size_t TABLESIZE = 1000000;
int main() {
std::vector<bool> primeT(TABLESIZE);
std::fill(primeT.begin(), primeT.end(), true);
primeT[0] = primeT[1] = false;
for (auto i = 2; i < TABLESIZE / 2; i++)
for (auto j = i * i; j < TABLESIZE; j += i)
primeT[j] = false;
std::vector<int> primes;
for (auto i = 2; i < TABLESIZE; i++)
if (primeT[i])
primes.push_back(i);
auto conse = 12;
auto which = 92;
auto conseTry = 13;
while (conseTry <= 1000) {
auto sum = std::accumulate(primes.begin(), primes.begin() + conseTry, 0);
for (auto i = 0; i < primes.size() - conseTry; i++) {
if (sum > TABLESIZE)
break;
if (i != 0)
sum = std::accumulate(primes.begin() + i, primes.begin() + i + conseTry,
0);
if (primeT[sum]) {
conse = conseTry;
which = sum;
break;
}
}
conseTry++;
}
std::cout << conse
<< " is the number of consecutive and the result is: " << which
<< '\n'; // 997651
}
The answer is:
Written in C++:
#include <algorithm>
#include <array>
#include <iostream>
#include <string>
#include <vector>
constexpr size_t tableSize = 1000000;
std::array<bool, tableSize> primeTable;
std::vector<int> primes;
void initPrimeTable() {
std::fill(primeTable.begin(), primeTable.end(), true);
primeTable[0] = primeTable[1] = false;
primeTable[2] = true;
for (size_t i = 2; i < primeTable.size(); i++)
for (auto k = i * 2; k < primeTable.size(); k += i)
primeTable[k] = false;
for (size_t i = 0; i < primeTable.size(); i++)
if (primeTable[i])
primes.push_back(i);
}
template <typename T> bool isPrime(const T num) { return primeTable[num]; }
bool isPrime(const std::string &n) { return primeTable[std::atol(n.c_str())]; }
bool isPrime(const char *num) { return primeTable[std::atol(num)]; }
bool areSameInMask(const std::string &mask, const std::string &num) {
size_t indices[15];
size_t idxCount = 0;
for (auto i = 0; i < mask.size(); i++)
if (mask[i] == '1')
indices[idxCount++] = i;
for (auto i = 0; i < idxCount - 1; i++)
if (num[indices[i]] != num[indices[i + 1]])
return false;
return true;
}
int familySize(int p) {
auto pStr = std::to_string(p);
int maxFamilySize = 0;
for (auto c1 = 1; c1 < pStr.size() - 1; c1++) {
std::string mask(pStr.size(), '0');
std::fill_n(mask.begin(), c1, '1');
std::sort(mask.begin(), mask.end());
do {
if (!areSameInMask(mask, pStr))
continue;
int familySize = 0;
auto ps = pStr;
for (auto i = 0; i < 10; i++) {
for (auto k = 0; k < ps.size(); k++) {
if (mask[k] == '1')
ps[k] = '0' + i;
}
if (ps[0] != '0' && isPrime(ps))
familySize++;
}
maxFamilySize = std::max(maxFamilySize, familySize);
} while (std::next_permutation(mask.begin(), mask.end()));
}
return maxFamilySize;
}
std::string bestMask(int p) {
auto pStr = std::to_string(p);
int maxFamilySize = 0;
std::string bestMask(pStr.size(), '0');
for (auto c1 = 1; c1 < pStr.size() - 1; c1++) {
std::string mask(pStr.size(), '0');
std::fill_n(mask.begin(), c1, '1');
std::sort(mask.begin(), mask.end());
do {
if (!areSameInMask(mask, pStr))
continue;
int familySize = 0;
auto ps = pStr;
for (auto i = 0; i < 10; i++) {
for (auto k = 0; k < ps.size(); k++) {
if (mask[k] == '1')
ps[k] = '0' + i;
}
if (ps[0] != '0' && isPrime(ps))
familySize++;
}
maxFamilySize = std::max(maxFamilySize, familySize);
if (maxFamilySize == familySize)
bestMask = mask;
} while (std::next_permutation(mask.begin(), mask.end()));
}
return bestMask;
}
int main() {
initPrimeTable();
for (auto p : primes) {
auto famSize = familySize(p);
if (famSize == 8) {
std::cout << p << std::endl; // 121313
break;
}
}
}
The answer is:
Written in C++:
#include <algorithm>
#include <iostream>
#include <numeric>
#include <string>
template <typename T> bool condition(T n) {
std::string prev = std::to_string(n);
std::sort(prev.begin(), prev.end());
for (auto i = 2; i <= 6; i++) {
std::string s = std::to_string(n * i);
std::sort(s.begin(), s.end());
if (s != prev)
return false;
prev = s;
}
return true;
}
int main() {
int n = 1;
while (!condition(n))
n++;
std::cout << n << std::endl;
}
The answer is:
Written in C++:
#include <algorithm>
#include <iostream>
#include <numeric>
int64_t nCr(const int64_t n, int64_t r) {
int64_t result = 1;
int64_t j = 1, k = 1;
for (int64_t i = 1; i <= n; i++) {
result *= i;
while (j <= r && result % j == 0) {
result /= j;
j++;
}
while (k <= n - r && result % k == 0) {
result /= k;
k++;
}
}
return result;
}
int64_t nCrOMult(const int64_t n, int64_t r) {
if (r >= n / 2)
r = n - r;
double res = 1;
for (int64_t i = 1; i <= r; i++) {
res *= double(n + 1 - i) / double(i);
}
return res;
}
bool nCrisOver1mil(const int64_t n, int64_t r) {
if (r >= n / 2)
r = n - r;
double res = 1;
for (int64_t i = 1; i <= r; i++) {
res *= double(n + 1 - i) / double(i);
if (res > 1000000.0)
return true;
}
return false;
}
int main() {
int64_t nMax = 100;
int64_t overCount = 0;
for (int64_t n = 1; n <= nMax; n++) {
for (int64_t r = 0; r <= n; r++) {
if (nCrisOver1mil(n, r))
overCount++;
}
}
std::cout << overCount << std::endl;
}
The answer is:
Written in C++:
#include <algorithm>
#include <array>
#include <fstream>
#include <iostream>
#include <numeric>
#include <string>
#include <variant>
#include <vector>
enum Suit { H, C, S, D };
struct Card {
int value = 2; // 2 3 4 5 6 7 8 9 10 Jack Queen King Ace (2-14)
Suit suit = H;
Card(const std::string &s) {
char valS = s[0];
if (valS >= '2' && valS <= '9')
value = valS - '0';
if (valS == 'T')
value = 10;
if (valS == 'J')
value = 11;
if (valS == 'Q')
value = 12;
if (valS == 'K')
value = 13;
if (valS == 'A')
value = 14;
char suitS = s[1];
if (suitS == 'H')
suit = H;
if (suitS == 'C')
suit = C;
if (suitS == 'S')
suit = S;
if (suitS == 'D')
suit = D;
}
friend std::ostream &operator<<(std::ostream &os, const Card &c) {
char valS = '0' + c.value;
if (valS > '9') {
if (c.value == 10)
valS = 'T';
if (c.value == 11)
valS = 'J';
if (c.value == 12)
valS = 'Q';
if (c.value == 13)
valS = 'K';
if (c.value == 14)
valS = 'A';
}
char suitS;
if (c.suit == H)
suitS = 'H';
if (c.suit == C)
suitS = 'C';
if (c.suit == S)
suitS = 'S';
if (c.suit == D)
suitS = 'D';
os << valS << suitS;
return os;
};
};
struct Hand {
std::array<Card, 5> cards;
Hand(const std::string &s)
: cards{s.substr(0, 2), s.substr(3, 2), s.substr(6, 2), s.substr(9, 2),
s.substr(12, 2)} {
std::sort(cards.begin(), cards.end(), [](const Card &c1, const Card &c2) {
return c1.value < c2.value;
});
}
friend std::ostream &operator<<(std::ostream &os, const Hand &h) {
os << h.cards[0] << ' ' << h.cards[1] << ' ' << h.cards[2] << ' '
<< h.cards[3] << ' ' << h.cards[4];
return os;
}
int maxValue() const { return cards.back().value; }
bool isPair() const {
for (auto i = cards.begin() + 1; i != cards.end(); i++)
if (i->value == (i - 1)->value)
return true;
return false;
}
bool isTwoPairs() const {
bool hasOnePair = false;
int valueOfFirstPair;
for (auto i = cards.begin() + 1; i != cards.end(); i++)
if (i->value == (i - 1)->value && !hasOnePair) {
{
valueOfFirstPair = i->value;
hasOnePair = true;
}
} else if (hasOnePair && i->value == (i - 1)->value &&
i->value != valueOfFirstPair)
return true;
return false;
}
bool isThreeOfAKind() const {
for (auto i = cards.begin() + 2; i != cards.end(); i++)
if (i->value == (i - 1)->value && i->value == (i - 2)->value)
return true;
return false;
}
bool isFourOfAKind() const {
for (auto i = cards.begin() + 3; i != cards.end(); i++)
if (i->value == (i - 1)->value && i->value == (i - 2)->value &&
i->value == (i - 3)->value)
return true;
return false;
}
bool isStraight() const {
for (auto i = cards.begin(); i != cards.end(); i++)
if (i->value + 1 != (i + 1)->value)
return false;
return true;
}
bool isFlush() const {
for (auto i = cards.begin() + 1; i != cards.end(); i++)
if (i->suit != (i - 1)->suit)
return false;
return true;
}
bool isStraightFlush() const { return isStraight() && isFlush(); }
bool isRoyalFlush() const {
return isStraightFlush() && cards.front().value == 10;
}
bool isFullHouse() const {
return (cards[0].value == cards[1].value &&
cards[2].value == cards[0].value &&
cards[4].value == cards[3].value &&
cards[0].value != cards[4].value) ||
(cards[4].value == cards[3].value &&
cards[2].value == cards[3].value &&
cards[0].value == cards[1].value &&
cards[0].value != cards[4].value);
}
int rank() const {
if (isRoyalFlush())
return 9;
else if (isStraightFlush())
return 8;
else if (isFourOfAKind())
return 7;
else if (isFullHouse())
return 6;
else if (isFlush())
return 5;
else if (isStraight())
return 4;
else if (isThreeOfAKind())
return 3;
else if (isTwoPairs())
return 2;
else if (isPair())
return 1;
return 0;
}
long long decisionRank() {
long long r = 0;
r += cards[0].value;
r += cards[1].value * 100;
r += cards[2].value * 10000;
r += cards[3].value * 1000000;
r += cards[4].value * 100000000;
long long rr = rank();
r += rr * 1000000000000LL;
long long secondary = 0;
if (isPair())
secondary = getMaxPairValue();
r += secondary * 10000000000LL;
return r;
}
int getMaxPairValue() const {
int maxVal = 0;
for (auto i = cards.begin() + 1; i != cards.end(); i++)
if (i->value == (i - 1)->value)
maxVal = std::max(maxVal, i->value);
return maxVal;
}
int getMinPairValue() const {
int minVal = 0;
for (auto i = cards.begin() + 1; i != cards.end(); i++)
if (i->value == (i - 1)->value)
minVal = std::min(minVal, i->value);
return minVal;
}
static bool standardDecideUnique(const Hand &h1, const Hand &h2) {
std::vector<Card> v1;
std::unique_copy(
h1.cards.begin(), h1.cards.end(), std::back_inserter(v1),
[](const Card &c1, const Card &c2) { return c1.value == c2.value; });
std::vector<Card> v2;
std::unique_copy(
h2.cards.begin(), h2.cards.end(), std::back_inserter(v2),
[](const Card &c1, const Card &c2) { return c1.value == c2.value; });
for (int i = std::min(v1.size(), v2.size()); i >= 0; i--) {
if (v1[i].value != v2[i].value) {
if (v1[i].value > v2[i].value)
return true;
else
return false;
}
}
return true;
}
static bool standardDecide(const Hand &h1, const Hand &h2) {
for (int i = 4; i >= 0; i--) {
if (h1.cards[i].value != h2.cards[i].value) {
if (h1.cards[i].value > h2.cards[i].value)
return true;
else
return false;
}
}
return true;
}
static bool firstWins(const Hand &h1, const Hand &h2) {
auto rank1 = h1.rank(), rank2 = h2.rank();
if (rank1 != rank2)
return rank1 > rank2;
auto rank = rank1;
if (rank == 9)
return true;
if (rank == 8) {
if (h1.cards[4].value == h2.cards[4].value) {
return standardDecide(h1, h2);
} else {
return h1.cards[4].value > h2.cards[4].value;
}
}
if (rank == 7) {
if (h1.cards[2].value == h2.cards[2].value)
return standardDecide(h1, h2);
else
return h1.cards[2].value > h2.cards[2].value;
}
if (rank == 6) {
if (h1.cards[2].value == h2.cards[2].value)
return standardDecide(h1, h2);
else
return h1.cards[2].value > h2.cards[2].value;
}
if (rank == 5)
return standardDecide(h1, h2);
if (rank == 4) {
if (h1.cards[4].value == h2.cards[4].value) {
return standardDecide(h1, h2);
} else {
return h1.cards[4].value > h2.cards[4].value;
}
}
if (rank == 3) {
if (h1.cards[2].value == h2.cards[2].value)
return standardDecide(h1, h2);
else
return h1.cards[2].value > h2.cards[2].value;
}
if (rank == 2) {
auto m1 = h1.getMaxPairValue(), m2 = h2.getMaxPairValue();
auto l1 = h1.getMinPairValue(), l2 = h2.getMinPairValue();
if (m1 == m2) {
if (l1 == l2)
return standardDecide(h1, h2);
else {
return l1 > l2;
}
} else
return m1 > m2;
}
if (rank == 1) {
auto m1 = h1.getMaxPairValue(), m2 = h2.getMaxPairValue();
if (m1 == m2)
return standardDecide(h1, h2);
else
return m1 > m2;
}
return standardDecide(h1, h2);
}
};
int main() {
/*std::cout << Hand::firstWins(Hand("5H 5C 6S 7S KD"), Hand("2C 3S 8S 8D TD"))
<< Hand::firstWins(Hand("5D 8C 9S JS AC"), Hand("2C 5C 7D 8S QH"))
<< Hand::firstWins(Hand("2D 9C AS AH AC"), Hand("3D 6D 7D TD QD"))
<< Hand::firstWins(Hand("4D 6S 9H QH QC"), Hand("3D 6D 7H QD QS"))
<< Hand::firstWins(Hand("2H 2D 4C 4D 4S"), Hand("3C 3D 3S 9S 9D"))
<< Hand::firstWins(Hand("8C TS KC 9H 4S"), Hand("7D 2S 5D 3S AC"))
<< std::endl; // Should be 010110*/
std::ifstream input("poker.txt");
int leftWins = 0;
int leftWins2 = 0;
while (!input.eof()) {
std::string line;
std::getline(input, line);
if (Hand::firstWins(Hand(line.substr(0, 14)), Hand(line.substr(15, 14))))
leftWins++;
if (Hand(line.substr(0, 14)).decisionRank() >=
Hand(line.substr(15, 14)).decisionRank())
leftWins2++;
}
std::cout << leftWins2 - 3 << std::endl; // 376
}
The answer is:
Written in C++:
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
class BigInt {
public:
std::vector<uint8_t> nums;
BigInt() { nums = {}; }
BigInt(unsigned long long n) {
nums = {};
while (n > 0) {
nums.push_back(n % 10);
n /= 10;
}
}
static BigInt add(BigInt &i1, BigInt &i2) {
while (i1.size() < i2.size())
i1.nums.push_back(0);
while (i2.size() < i1.size())
i2.nums.push_back(0);
BigInt n;
n.nums = {};
n.nums.reserve(i1.size());
for (size_t i = 0; i < i1.size(); i++) {
n.nums.push_back(i1.nums[i] + i2.nums[i]);
}
n.rake();
return n;
}
size_t size() { return nums.size(); }
void rake() {
for (size_t i = 0; i < size(); i++) {
while (nums[i] >= 10) {
if (nums.size() - 1 == i) {
nums.push_back(0);
}
nums[i] -= 10;
nums[i + 1] += 1;
}
}
while (nums.back() == 0)
nums.pop_back();
}
std::string to_string() {
std::string out;
out.reserve(nums.size());
for (size_t i = nums.size(); i > 0; i--) {
out.push_back('0' + nums[i - 1]);
}
return out;
}
void reverse() { std::reverse(nums.begin(), nums.end()); }
bool is_palindrome() {
for (size_t i = 0; i < nums.size(); i++) {
if (nums[i] != nums[nums.size() - 1 - i])
return false;
}
return true;
}
bool is_Lychrel(const size_t max_iter = 50) {
BigInt a = *this;
BigInt b = a;
b.reverse();
for (size_t i = 0; i < max_iter + 2; i++) {
a = BigInt::add(a, b);
b = a;
b.reverse();
if (a.is_palindrome())
return false;
}
return true;
}
};
int main() {
size_t count = 0;
for (size_t n = 1; n <= 10000; n++) {
BigInt i = n;
if (i.is_Lychrel()) {
count++;
}
}
std::cout << "The number of Lychrel numbers under 10K: "
<< std::to_string(count) << std::endl;
}