Coding Style
Factor the Algorithm into Helper Functions
Right now, you’ve got two levels of nested if, several with else blocks, nested inside five levels of loops.
This could really benefit from some helper functions. Let’s say I’m giving you the code review and I say, “Oh, we have a function like this already. Maybe you could use that in your algorithm.”
/* Finds all pairs (a,b) such that a**3 + b**3 = sum.
*/
fn taxicab_pairs(sum: usize) -> Vec<(usize, usize)>
The code would get a whole lot simpler now, right? For example, your loop might now look something like
for i in 1..arguments.n {
let cube_pairs = taxicab_pairs(i);
if cube_pairs.len() > 1 {
// Print the pairs out.
}
}
Or if you just want a list of Ramanujan-Hardy numbers like you have now, you might do something like that with iterators.
Prefer Iterator Expressions to Mutable Objects
You currently initialize
let mut ramanujan_numbers = Vec::new();
and push numbers onto it, one at a time.
But you could also build this list of numbers at once, with a bit of functional programming, and make it immutable. That not only prevents entire categories of bugs, the compiler converts everything into static single assignments during its optimization passes, so you’re making the code easier to optimize, too.
That might look something like
let ramunujan_numbers: Vec<usize> = (1..arguments.n)
.filter(is_taxicab_number)
.collect();
Or if we have taxicab_pairs, maybe we’d rather keep the list of (a, b) and (c, d) pairs we calculate with that, instead of sending it to a print loop.
let sets_of_pairs: Vec<Vec<(usize, usize)>> = (1..arguments.n)
.map(taxicab_pairs) // Gives us a sequence of Vec<(usize, usize)>
.filter(move |v| v.len() > 1) // Removes all with fewer than two pairs
.collect();
Then we can keep the code at the end to handle the case where there aren’t any taxicab numbers in range.
You might also choose to remove the .collect() lines, and let the compiler infer the type, to obtain lazily-evaluated iterators instead of a strictly-evaluated Vec. This lets you generate the sequence as you calculate, and print each output immediately, rather than waiting for all the output to begin printing anything. You would then need to use a different method to see if there are any taxicab numbers in range (such as making it Peekable and peeking ahead to see whether the iterator immediately returns None).
let mut sets_of_pairs = (1..n)
.map(taxicab_pairs) // Gives us a sequence of Vec<(usize, usize)>
.filter(move |v| v.len() > 1) // Removes all with fewer than two pairs
.peekable();
if sets_of_pairs.peek().is_none() {
println!("No taxicab numbers less than {}.", n);
}
// No need for an else; the loop will just fall through in that case.
Make the Type of Each Variable Obvious
Right now, you declare a list like
let mut ramanujan_numbers = Vec::new();
One way this could be improved is that we can’t tell what’s in the vector. The compiler tries to infer it from elsewhere, but that’s very fragile to refactoring. Maybe the line that sets this tells the compiler the type moves out of scope, or maybe it also tries to infer the type out of context, or maybe there are multiple places this gets updated, and not all of them agree.
Even if the compiler can tell what the type of ramanujan_numbers is, it’s needlessly complicated for a human maintaining the code. So, annotate it when it’s declared, or (if you aren’t replacing this with a static single assignment) call Vec::<usize>::new() with the turbofish operator, or something else that makes it clear.
Simplify the Conditionals
The first_condition, second_condition and third_comdition block is unwieldy, although it can be factored out entirely.
The Command-Line Arguments
You might have chosen the way you did intentionally, but there is support for this in the standard library. You could use that to check for runtime errors and choose which message to print.
Performance
Prune the Search Space with Some Easy (Really!) Number Theory
Okay, let’s say we have two whole numbers, a and b. One thing we know about them already is that either a is bigger, b is bigger, or they’re equal. You already noticed that you can throw out all the cases where b > a, and cut your search time nearly in half. That’s a great idea, so let’s stick with it.
Here, we’re interested in an x and a y that add up to some number z. If x and y are equal, they’re both half of z. They can’t both be bigger than half of z, or they wouldn’t add up to z. So one is bigger than z/2 and one is smaller. If they aren’t equal to each other, and we just said that x isn’t bigger than y either, x must be the one that’s smaller than z/2 and y the one that’s bigger.
But, for this problem, we actually want x and y to be perfect cubes! So, x = a³ ≤ z/2 and y = b³ ≥ z/2. The most interesting part of that is a³ ≤ z/2. Since a is positive, we can take the cube root of both sides and solve for a. In other words, we only need to search up to the cube root of half of the target number for a, and we’ll be sure we’ve found every possible smaller cube that adds up with another to the right number.
Now, if we have a, we have x = a³, and we started with z, we can solve x + y = z for y = z - x. If y is also a perfect cube, we’re done. There are a few ways we chan check this, but one is to convert to floating-point, find the cube root, round off to an integer, and see if its cube is actually the right number.
Since the program specified that we only need to find out whether a number is the sum of two different pairs of positive cubes, not what all those pairs are, we could optimize further. (For example, we can prove that a+b is congruent to z, modulo 3, reducing the search space further.) But I’ll leave it there.
Putting It All Together
use std::{env, process};
/* Finds all pairs (a,b) such that a**3 + b**3 = sum.
*/
fn taxicab_pairs(sum: usize) -> Vec<(usize, usize)> {
/* If positive integers a**3 + b**3 = i, and WLOG a <= b,
* a <= pivot and b >= pivot.
*/
let pivot: usize = f64::floor(f64::powf(sum as f64 / 2.0, 1.0 / 3.0) + f64::EPSILON) as usize;
(1..=pivot)
.map(move |a| (a, sum - a * a * a))
.map(move |(a, b_cubed)| {
(
a,
f64::round(f64::powf(b_cubed as f64, 1.0 / 3.0)) as usize,
b_cubed,
)
})
.filter(move |&(_, b, b_cubed)| b * b * b == b_cubed)
.map(move |(a, b, _)| (a, b))
.collect()
}
pub fn main() {
const USAGE_MSG: &str = "Call this program with one command-line argument, N.\n";
let args: Vec<String> = env::args().collect();
let n: usize = if args.len() == 2 {
match args[1].parse::<usize>() {
Ok(n) => n,
_ => {
eprintln!("{}", USAGE_MSG);
process::exit(1)
}
}
} else {
eprintln!("{}", USAGE_MSG);
process::exit(1)
};
let sets_of_pairs: Vec<Vec<(usize, usize)>> = (1..n)
.map(taxicab_pairs) // Gives us a sequence of Vec<(usize, usize)>
.filter(move |v| v.len() > 1) // Removes all with fewer than two pairs
.collect();
if sets_of_pairs.is_empty() {
println!("No taxicab numbers less than {}.", n);
}
// No need for an else; the loop will just fall through in that case.
for cube_pairs in sets_of_pairs {
let (a, b) = cube_pairs[0]; // Safe, because we only added sets of at least two pairs.
let i = a * a * a + b * b * b;
let residue = i % 3;
print!("{}", i);
for (a, b) in cube_pairs {
assert_eq!(i, a * a * a + b * b * b);
assert_eq!(residue, (a + b) % 3); // You might prove this congruence.
print!(" = {}³ + {}³", a, b);
}
println!(".");
}
}
Links to the code on Godbolt,, and the OLIS sequence.
You might prefer the use of a helper function to a chain of map calls:
/* Finds all pairs (a,b) such that a**3 + b**3 = sum.
*/
fn taxicab_pairs(sum: usize) -> Vec<(usize, usize)> {
/* Given a and sum, finds b such that a**3 + b**3 == sum, if b exists.
* Returns either Some((a,b)) or None.
*/
fn find_dual(sum: usize, a: usize) -> Option<(usize, usize)> {
let b_cubed = sum - a*a*a;
let b = f64::round(f64::powf(b_cubed as f64, 1.0 / 3.0)) as usize;
if b*b*b == b_cubed {
Some((a, b))
} else {
None
}
}
/* If positive integers a**3 + b**3 = i, and WLOG a <= b,
* a <= pivot and b >= pivot.
*/
let pivot: usize = f64::floor(f64::powf(sum as f64 / 2.0, 1.0 / 3.0) + f64::EPSILON) as usize;
(1..=pivot)
.filter_map(move|a| find_dual(sum, a))
.collect()
}
