Project Euler - Rust problem 12

 On the Project Euler site, which I highly recommend, they don't want anyone sharing answers over 100.  I'm cool with that.  Once I get there, I'll share other things.  I'm getting more comfortable with Rust so we'll see where that goes.

Problem 12 - Project Euler

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

 1: 1

 3: 1,2,3

 6: 1,2,3,6

10: 1,2,5,10

15: 1,3,5,15

21: 1,3,7,21

28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

There's a few ways to approach this.  I chose to go into this brute force style.  

[dependencies]

divisors = "0.2.1"

Here's my single dependency and the code.

use std::time::{Instant};

fn main() {

    let start_time = Instant::now();

    let mut final_num: u32 = 0;

    let mut divisor_count: u32 = 0;

    let mut count: u32 = 1;

    while divisor_count < 498{

        let triangle = get_tri(count);

        let divisors = divisors::get_divisors(triangle);

        divisor_count = divisors.len() as u32;

        final_num = triangle;

        count += 1;

    }

println!("time = {:?}, final number = {:?}", start_time.elapsed(), final_num);

}

fn get_tri(x: u32) -> u32 {

    let mut count = x;

    let mut sum = 0;

    while count > 0{

        sum += count;

        count -= 1;

    }

    sum

}

Here we go. Declaring the final_num, the divisor count, and the count.  Then the loop. While the divisor count is less than 498 the loop will run.

Why 498?  I used 498 as the threshold because it would return on divisor length being 499 and this particular crate doesn't count 1 as a divisor where most of the problems do consider it. So I always have to take that into consideration when I use this crate.

In the loop, we define the triangle based on the current count.  That count is incremented by 1 at the end of the loop.  We get the number of divisors for the triangle. Assign final number to the triangle and increment the count.

Once it reaches 499, it breaks the while and prints the answer.  

I included the time thing just for fun.  I did go back and change the let triangle = get_tri(count) to final_num = get_tri(count).  It works. It's not as efficient as some of the other answers in other languages but it does get the job done. 1.5 seconds.

Project Euler - Rust Problem 11

 Problem 11 

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

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

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

After all this time, I still haven't figured out a good way to import information from txt files.

So I hard coded it... as an array, a multidimensional array, a constant multidimensional array

const DATA: [[u32;20]; 20] = [

    [08, 02, 22, 97, 38, 15, 00, 40, 00, 75, 04, 05, 07, 78, 52, 12, 50, 77, 91, 08], ...

[01, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 01, 89, 19, 67, 48]];

So that worked out.  Obviously I cut the center out for this post but it is in the code. 

Once that was out of the way, I was able to focus on the logic.  Now, I separated much of the logic into different functions.  While I could pass the values through to them, since I'm not editing the grid, I decided to keep it immutable and as a constant. It honestly makes reading the code easier (for me) but I'm not sure if that's really the best way to go about it.  In this instance though, I think it's the best way.

Here's my main function:

fn main(){

    let mut max_sum: u32 = 0;

    for x in 0..DATA.len(){

        for y in 0..DATA[x].len(){

            let sum = eval(x as u32, y as u32);

            if sum > max_sum{max_sum = sum};

        }

    }

    println!("{}", max_sum);

}

I tried to keep my main function as brief as possible.  so the loop is pretty straight forward.

Loop through each line, then loop through each number.  I declared a sum and if that sum is greater than the max, it replaces it. If not continue to the next.  The sum is equal to the return of a function eval that passes in the x and y numbers (numerical locations in the grid).

So what does eval do?

fn eval(x: u32, y: u32) -> u32 {

    let data_vec: Vec<u32> = vec![eval_vertical(x,y), eval_right(x,y),

        eval_diag_r(x,y), eval_diag_l(x,y)];

    let ans = data_vec.iter().fold(std::u32::MIN, |a,b| a.max(*b));

    ans

}

As you can see it does a few things.  First, it creates a vector.  Then it sorts that vector and sets ans to the max value in that vector and returns that from the function.

The vector itself is set to the values of all these functions.  Each function does basically the same thing.  It multiplies the values of the number and then the 3 down for vertical, the 3 right for right and then the diags right and left. I even put in a requirement for x and y positions so it didn't error out by going over the index.

fn eval_vertical(x: u32, y: u32) -> u32{

    let x: usize = x as usize;

    let y: usize = y as usize;

    if x > 16 {

        return 0;

    }

    DATA[x][y] * DATA[x+1][y] * DATA[x+2][y] * DATA[x+3][y]

}

fn eval_right(x: u32, y: u32) -> u32{

    let x: usize = x as usize;

    let y: usize = y as usize;

    if y > 16{

        return 0;

    }

    DATA[x][y] * DATA[x][y+1] * DATA[x][y+2] * DATA[x][y+3]

}

fn eval_diag_r(x: u32, y: u32) -> u32{

    let x: usize = x as usize;

    let y: usize = y as usize;

    if y > 16 || x > 16 {

        return 0;

    }

    DATA[x][y] * DATA[x+1][y+1] * DATA[x+2][y+2] * DATA[x+3][y+3]

}

fn eval_diag_l(x: u32, y: u32) -> u32{

    let x: usize = x as usize;

    let y: usize = y as usize;

    if y < 3 || x > 16 {

        return 0;

    }

    DATA[x][y] * DATA[x+1][y-1] * DATA[x+2][y-2] * DATA[x+3][y-3]

}

As you can see, they're closely repetitive and could merit a rewrite using recursion and even a direction argument with a match case... shrug. But that's not what I did.

It could cut the code size in half though.

Anyways, that's the code.  

I didn't see any other rust answer.  To the next problem.

Project Euler - Rust Problem 10

Problem 10

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

I've been doing a lot of exploring through the crate.io website.  I've found much like the old apple istore catch phrase, there's a crate for that.

I utilized a library called prime_tools.  The library has a function that literally finds all prime numbers less than a given number.  It returns a vector as 32bit unsigned integers.  From there we could loop through using vector.init().sum() however, sum() isn't a function of u64 and the answer here exceeds the max of a u32. So I went with a for loop.  Someday I hope to learn a better way

Tmol file - 

[dependencies]

prime_tools = "0.3.4"

main.rs

fn main(){

let my_vec = prime_tools::get_primes_less_than_x(2000000);

let mut my_sum: u64 = 0;

for i in my_vec{

my_sum = my_sum + i as u64;

}

println!("{}", my_sum);

}

Now, this is kind of a cop out in someways but it gets the job done.  The alternative is to go through and brute force it. Alternatively, you could use a sieve until you got to or exceeded 2000000.  This was my go to.

There was another user that used rust and went with the sieve method. I won't go into that here as I've already covered it with a previous problem that addressed prime numbers.

User Hegemon8 used an interesting brute force method.

Slick. 0.64s fn main() { let mut vector:Vec<bool> = vec![false; 2_000_000]; for i in 2..1415 { if vector[i] == false { let mut j = i * i; while j < vector.len() { vector[j] = true; j = j + i; } } } let mut sum = 0; for (index, i) in vector.iter().enumerate() { if i == &false { sum = sum + index; } } println!("{}", sum - 1); }

He created a vector of 2000000 values of bools all set to false.  They he looped through all the values from 2 to 1415.  Then if the value of the loop in the vector was false, he multiplied it by itself and set it to true if that index existed.  The significance of 1415 is that squared it exceeds 20000000 and 1414 falls a little short.  If you square a number the resulting number can't be prime.  This is a clever sieve method that's more compact than other's I've seen.  He then sums up all the false indexes and returns the sum.

I was curious if we could clean this up.

Maybe?

Here's my rewrite for the for loop at the bottom

let sum: u64 = vector.into_iter().enumerate().fold(0, |s, (i, j)| s + eval(i as u64, j));    

println!("{}", sum);

Then I had to add a function.

fn eval(x: u64, y: bool) -> u64{

    match y { true => 0, false => x as u64}

}

Now. It seems that the reason I had to use u64 is cause the answer is soooo big.

I learned a lot about the fold method doing this (4 hours of head to desk before it worked).  I also learned that in a fold, you can't (or I couldn't find how) to use a filter/match/ifelse statement.  I tried but match wouldn't work....

As I write this, I had a facepalm moment.  Yup learning in real time now. :(

I went back and tried something. It worked.

let sum: u64 = vector.into_iter()

    .enumerate()

    .fold(0, |s, (i, j)| s + match j { true => 0, false => i as u64});

Yup, so the match did work. I realized when I tried earlier I didn't add to the s value which is the total sum.

Correct me if I'm wrong (please).
fold (starting value, |return value, value_i'm evaluating in the iter| formula evaluated and added to the return value)

That's my understanding anyways.

Project Euler - Rust Problem 9

Problem 9

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

Find the product abc.

Pythagorean triplets are whole numbers that work with the right triangle formula.  They also increase in value so none of them are the same. 

There's a whole system of mathematics that deals with equations like this where there are multiple unknowns and various answers that once known will solve all equations present.  These equations are known as Diophantine equations.  

Thanks wikipedia... but that doesn't help me.  However, there's some juicy information on PT's.

Here are some properties that must be satisfied that we can use.

a^2 + b^2 = c^2
a < b < c
((c * a)(c*b))/2 is always a square
(3,4,5) is the smallest known PT
At most only one of a,b,c is a square (more than 1 square they're not a set)
a or b is divisible by 3
a or b is divisible by 4
a or b or c is divisible by 5
the largest number that always divides abc is 60

Ok, so there's a few things that we can increment by and check by. as well as a starting point.

We could always do the brute force method.

for i in 1..1000, for j in 2..1000, for k in 3..1000 if i+j+k = 1000, check if i^2 + j^2 = k^2, if true return i,j,k

Psudo code but that's the basic brute force. I mean if only one of them is equal to 1000 and satisfies the formula then great. 

However, I wanted to try a different approach.  There's a relation to PT's and Fibonacci sequences that is pretty interesting.  The downside to our current problem is that while the Fib numbers do follow a predictive pattern, they do not encompass all the PT's in that range.  They skip quite a few.

Kind of a "all buicks are cars but not all cars are buicks".

Project Euler - Rust Problem 8

Problem 8

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

73167176531330624919225119674426574742355349194934

96983520312774506326239578318016984801869478851843

85861560789112949495459501737958331952853208805511

12540698747158523863050715693290963295227443043557

66896648950445244523161731856403098711121722383113

62229893423380308135336276614282806444486645238749

30358907296290491560440772390713810515859307960866

70172427121883998797908792274921901699720888093776

65727333001053367881220235421809751254540594752243

52584907711670556013604839586446706324415722155397

53697817977846174064955149290862569321978468622482

83972241375657056057490261407972968652414535100474

82166370484403199890008895243450658541227588666881

16427171479924442928230863465674813919123162824586

17866458359124566529476545682848912883142607690042

24219022671055626321111109370544217506941658960408

07198403850962455444362981230987879927244284909188

84580156166097919133875499200524063689912560717606

05886116467109405077541002256983155200055935729725

71636269561882670428252483600823257530420752963450

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

Well then.  Yeah, that's a thing.

Logically speaking... you would loop through the numbers starting with 0-3 and then ending -4:-1.  So... With Rust, it doesn't index the same way as python.  We should still be able to loop through it just fine.  The bigger issue, for me, is how do you get the input into the program.

You can hard code it.  Just put in the string of numbers manually into the code.  Sure why not? I would pull it in from a text file but... I'm still trying to figure that out. meh.

So I loaded the number string into a vector as integers. 

My code

fn main(){

        let mut my_vec = vec![7,3,(all the numbers from above),5,0];

let mut largest_multi = 0;

let mut first: u64 = my_vec.pop().unwrap();

let mut second: u64 = my_vec.pop().unwrap();

let mut third: u64 = my_vec.pop().unwrap();

let mut fourth: u64 = my_vec.pop().unwrap();

let mut fifth: u64 = my_vec.pop().unwrap();

let mut sixth: u64 = my_vec.pop().unwrap();

let mut seventh: u64 = my_vec.pop().unwrap();

let mut eighth: u64 = my_vec.pop().unwrap();

let mut ninth: u64 = my_vec.pop().unwrap();

let mut tenth: u64 = my_vec.pop().unwrap();

let mut eleventh: u64 = my_vec.pop().unwrap();

let mut twelvth: u64 = my_vec.pop().unwrap();

let mut thirteenth: u64 = my_vec.pop().unwrap();

while my_vec.len() > 0{

let mut x = first * second * third * fourth * fifth * sixth * seventh * eighth * ninth * tenth * eleventh * twelvth * thirteenth;

if x > largest_multi{

largest_multi = x;

}

println!("{}", my_vec.len());

first = second;

second = third;

third = fourth;

fourth = fifth;

fifth = sixth;

sixth = seventh;

seventh = eighth;

eighth = ninth;

ninth = tenth;

tenth = eleventh;

eleventh = twelvth;

twelvth = thirteenth;

thirteenth = my_vec.pop().unwrap();

}

println!("{:?}", largest_multi);

}

So after I hard coded the number string, I defined 13 variables.  Then I filled those with the first 13 popped values from the vector.  Then I created the loop based on the length of the vec.  If the vec is greater than 0 then there's still values in them.  So every loop, all 13 variables are multiplied together.

if the multiple is greater than the largest recorded value, it records the new value.  After all the values have been popped, the largest multiple is printed.

There's obviously ways to improve this.  filter out any iteration if 0 is in the variables. you know skip those.  Change how the slices of the vec are accessed.

I doubt this is the most effective method.

Other Guys Code

Minacode wrote:

The main idea is to not calculate the whole window at every step. Thus, we have to divide through the leftmost number we are "leaving" while moving the window to the next position, and then multiply with the new number on the right. Because there are zeros, we have to be careful. At the start and after every zero, we have to incrementally multiply enough numbers to make up a whole window of 13 numbers. This is why we keep track of a scope count which measures the current size of the window. Until we did not reach 13 elements, we do not update the max value. fn main() { let series = [ 7,3,(all the numbers in the list),5,0 ]; let length = series.len(); let scope = 13; let mut product: u64 = series[0]; let mut max = product; let mut i = 0; let mut scope_count = 1; while i < length-scope { let new = series[i + scope_count]; if new == 0 { i += scope_count; scope_count = 1; while i < length && series[i] == 0 { i += 1; } if i == length { break; } product = series[i]; } else { if scope_count == scope { let last = series[i]; product /= last; product *= new; if product > max { max = product; } i += 1; } else { scope_count += 1; product *= new; } } } println!("{}", max); }

So basically this code improves in all the ways that I had mentioned. It cycles through the list 13 at a time and multiplies them together. If it == 0 then it moves the cycle. He also uses an array instead of a vec. I will be looking into the benefits of using one over the other.

Project Euler - Rust Problem 7

 Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

Now this is interesting. Because we dealt with primes in an earlier problem.  There we cheaped out a little... and so why should this be any different.

This is literally an example in the primal crate documentation. add "primal = "0.2"" " to the tmol

// (.nth is zero indexed.)
let p = primal::Primes::all().nth(10001 - 1).unwrap();
println!("The 10001st prime is {}", p); // 104743

Boom prints the answer. No fuss no muss. 

Alternativly, there's some of the other approaches.

The other guys code

First answer comes from BitRake who is quickly becoming my favorite person on the answer forums.

He points out, look we have this website with all known primes on it. Prime pages.

Another user Frinzie did it manually.  Kudos to him for tackling this challenge in a more robust approach.

fn is_prime(num: i32) -> bool { // works for odd numbers in range [3, +inf) let ceil = (num as f64).sqrt() as i32; for i in (3..=ceil).step_by(2) { if num % i == 0 { return false; } } true } fn main() { let mut primes = vec![2]; let mut num = 3; while primes.len() < 10001 { if is_prime(num) { primes.push(num); } num += 2; } println!("{}", primes[10000]) }

First he creates a vector primes.  Got to have a place to store the answers.  Then a num variable starting at 3.  Primes after 2 can't be even by definition so he's only going to check odd numbers.  Start at 3 and add 2 with every iteration.

He sets the limit in the while loop, while the primes vector length is less than 10001 the loop will check all odd numbers and add them to the primes list until it has 10001.  Finally it prints out the 10000 index of the primes vector.  

Great approach using solid logic.

One last user did it the same way Frinzie approached it but without putting the function logic in the function.

Special note: 1 apparently isn't prime. shrug so I guess I'll take that into account when using the these libraries.

Project Euler - Rust Problem 6

 Problem 6

The sum of the squares of the first ten natural numbers is,

    1^2 + 2^2...+10^2 = 385

The square of the sum of the first ten natural numbers is,

    (1+2+...+10)^2 = 55^2 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is .

    3025 - 385 = 2640

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

This seems pretty straight forward.

we need a sum of squares function and a square of sums function and then subtract the two.

Sounds easy...

My approach

fn main() {

let test_u_limit = 100;

let x = square_of_sums(test_u_limit) - sum_of_squares(test_u_limit);

println!("{}", x);

}

Here's my main function. Straight forward.  Subtract the returns of two functions.

Let's tackle the sum of squares function. 

fn sum_of_squares(u_limit: i64) -> i64{

let mut ans = 0;

for x in 1..=u_limit{

ans = ans + (x^2);

}

println!("Sum of squares is {}", ans);

return ans

}

I went with i64 on the off chance that the value might exceed 2147483647.  It doesn't but I didn't know that.  I guess, I could refactor it to i32 since I have to refactor it to get it to work. 

Oh yeah, this doesn't work.  Fun fact... the ^ symbol doesn't raise to a power.  Nope.  It's a bitwise operator.  This doesn't work.

According to stack overflow, to raise to a power it should read x.pow(2).  pow takes an unsigned 32 bit int and returns a signed 32 bit int.

so the refined code reads...

fn sum_of_squares(u_limit: i64) -> i64{

let mut ans = 0;

for x in 1..=u_limit{

ans = ans + x.pow(2);

}

return ans

}

not a huge change but it works.  Unfortunately, I did the same thing with the square of sums function but I fixed it at the same time I did the previous refactor.

fn square_of_sums(u_limit: i64) -> i64{

let mut ans = 0;

for x in 1..=u_limit{

ans += x;

}

ans = ans.pow(2);

return ans

}

This works fine.  I learned how to raise things to a power.

what's interesting is this can work with raw numbers if you type them. I played around on the playground and found this works.

fn main(){

    let x: i32 = 7;

    println!("x to the 2 power is {}", x.pow(2));

    println!("5 to the 2 power is {}", 5i32.pow(2));

   

}

Other guys code

eathren had almost the same idea. except he approached the power issue manually.

doing i*i instead of i.pow(2)  

Still works but I wonder if he ran into the same issue I did with the ^ symbol.
He also opted for 1..n+1 instead of 1..=n  I wonder if there's a performance advantage to that.

Final thoughts

I'm discovering that there aren't alot of answers in Rust on these problem sites.  Most of the answers I'm seeing are from the last 4 months.  It seems like it's picking up steam.  I'm getting more comfortable with it.  I thought it would be a lot harder.  Not that it's easy just... it's easier than I had anticipated.  Till next time.

Project Euler - Rust Problem 5

Problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

This is an interesting problem.  There's a few things we can tell about the answer.

All numbers are evenly divisibly by 1. If it's divisible by 2 that means it's even.  If it's divisible by 20, then it's evenly divisible by 10 and 5.  

Our range is 2520..?

The most obvious direction would be to start at 2520, divide by all the digits with a Boolean trigger, if false then add 20 and do it again.

There prob is an easier way but this is what I went with.

Set up the loop.  I went with a while loop. I started 20 less than the starting number because if I put the increment after the bool test it will add 20 then evaluate the break criteria and the answer would be 20 more than the correct answer.  

I considered a for loop and if it had been c++ I would have but I don't know that you can set up the for loop any other way than x in range and I don't know the range... While for indefinite loop, for for definite, am I right? 

fn main() {

    let mut found: bool = false;

    let mut cur_num: i32 = 2500;

    while found == false{

    cur_num += 20;

    found = div_cur(cur_num);

    }

    println!("{}", cur_num);

}

That's the main function done.  I figure the actual calculation I can source out to a function for recursion.

fn div_cur(x:i32) -> bool{

let mut trigger = false;

let mut s_num = 20;

while s_num > 0{

trigger = even_div(x, s_num);

if trigger == false{

return false

}

s_num -= 1;

}

trigger

}

I considered putting some of this logic in the main while loop, and I could have but I opted to keep the math logic separate. I figured I could avoid a lot of nasty if then statements.

So this function takes in a number and returns a bool.  Default return value is false.  I started with 20 as a counter and am counting down.  I figured that it would be quicker to divide by 20, 19, 18 than 1, 2, 3 since if it would error out it's more likely to error out on the higher divisors in range.

we check the even divide and if false there's not reason to continue.  If it isn't then we're continuing the loop and so we increment. If all 20 in the divisor range return divisible it returns true.

fn even_div(x: i32, y: i32) -> bool{

return x % y == 0

}

This is function that gets called every time we want to test the division. Takes two numbers, the test number and the divisor and then returns true if it's evenly divisible and false if not.

Pretty straight forward.

Let's look at the other guys code.

Other Guy's Code

Weflown had a... different approach.

fn main() {

    let mut n: u128 = 4000000;

    while (n % 2) != 0 || (n % 3) != 0 || (n % 4) != 0 || (n % 5) != 0 || (n % 6) != 0 || (n % 7) != 0 || (n % 8) != 0 || (n % 9) != 0 || (n % 10) != 0 || (n % 11) != 0 || (n % 12) != 0 || (n % 13) != 0 || (n % 14) != 0 || (n % 15) != 0 || (n % 16) != 0 || (n % 17) != 0 || (n % 18) != 0 || (n % 19) != 0 || (n % 20) != 0 {

        n = n + 1;

    }

    println!("{}", n)

}

I'm not sure where he got the 4 million starting point but that's certainly a way to do it.

According to him, "this is the worst way to do this but I don't care"

This was the only other rust response.

Project Euler - Rust Problem 4

Project Euler

Problem 4 - in Rust

A palindromic number reads the same both ways. 

The largest palindrome made from the product 

of two 2-digit numbers is 9009 = 91 × 99. 

 

Find the largest palindrome made from the 

product of two 3-digit numbers.

Fun times.  Love palindromes.  Taco Cat... anyone? :)

What isn't fun? Strings in Rust.

They are the bane of my existence in programing with Rust. I don't know why they're so hard to mess with but they are.  So we can approach this just straight numbers or ... we can convert them to strings and compare...

Numbers. for sure.

Breakdown

I'm starting to get into a groove with analyzing these problems and my approach. I realize my approach might be complete crap but it works and it's mine so :P.

Seriously thought, first rule of fight clu... of answering these things.  <whistles innocently> First thing is breaking it down into managable pieces. 

So, what is it asking?

Find - we're looking for something
the largest - biggest number (quantifier)
Palindrome - something the same forward and backwards.
made from the product of 2 (3) digit numbers -... ok

so we're taking two 3 digit numbers, I assume they are both different, and we are multiplying them together.  If the answer is a palindrome and there's no other palindrome answer above it, then that's the answer...

Sure.

So what's the first question?

Can we narrow down the pool of numbers we're using? Get a range?

We can take the two smallest 3 digit numbers and multiply those for the low.  Then take the two largest 3 digit number and multiply those for the high.

100 * 101 = 10,100   This is not a palindrome but it is the lowest product of two 3 digit numbers.

999 * 998 = 997,002 this is also not a palindrome but is the highest product of two 3 digit numbers.

Now we have a range. [10,100..997,002].  The number we seek is in there.

so if we use the variable ans then the following is true:

10100 < ans < 997002

This gives us the starting point. 986902 different possibilities for a product

Recognize 

As the great Warren G once said, Recognize.  That's what we have to teach the computer to do. 

If we have a number, say 4516.  We can mod by 10 and get 6.  if we take the number and divide by 10, we get 451.6 (rounded down, aka flat) 451.  mod 10 = 1, divide by 10 = 45, mod 10 = 5, ... and if we add these mod's to a vec we now have the reverse value divided by each digit and in reverse order.

Also, if you have an even numbered value with a zero in the one's place, it will never by a palendrom.  143580 reversed is 085341.  The computer will drop the 0 and honestly, it would never add a leading 0 in the first place.  So this can be the first step in the logic of determining if it's a palendrome.

psuedo code

for loop - 

num = a*b

If num % 10 == 0 {

continue

}

function call to pal_check(num)

We will save a lot of time skipping over the values evenly divisible by 10.

pal_check function - pseduo code

pass in the value we're checking
declare two Vec's, one for forwards, one for back
for loop - break apart the number and add it to the array, one push and one insert to 0
then return true if both vecs match
else return false

rinse repeat

Project Euler - Rust Problem 3

 Project Euler

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Ok...  this is basically a question asking two questions.

First Question

What are all the factors of a given number?

I realize that it's asking specifically about 600,851,475,143.  However, when looking at these problems, it's best to start with the abstract and assume that at any given time, you'll be given a different input.  The reason for this is sometimes you will.  Not to mention it's great to approach it this way, allows you to get used to thinking in ways that takes the unknown into account.

So, how do we find the factors of a given number? And before we start, what is a factor?

A factor is defined as...

any number that can be multiplied by another to get the original number.  

For instance, factors of 4 are 1,2,4.  1*4 = 4, 2*2 = 4.  We won't deal with the negative numbers and fractions are never a factor.

So how do we find these numbers?

The brute force method is to loop through all the numbers 1 to the given number and divide the given number by them. If they divide evenly, they are a factor.  Add those to a Vec.  Test them all to filter out all the prime ones and return the largest. 

You could also loop through, divide evenly, test if prime, add prime to the vec and take the largest.

This is a perfectly valid and extremely long way to do this.

NOTE: Prime numbers are numbers that are evenly divisible by 1 and themselves and that is it.

another way would be to loop through the numbers 1 to N and test if they're prime first and then see if they're a factor.  You could also take a list of known prime numbers and start there.

Determining a prime number is first asking is it odd? Even number can't, by definition be prime outside of the number 2.  So you're Even? You're out... (sad face).  So it's odd.  Now start dividing that number by all numbers less than half of that number rounded down.  If you get an evenly dividable number (aka N%x == 0) then it's not prime.

How many factors does the number have?

In the process of finding all the prime numbers. We can locate the number of factors, which could help.

Using the following formulas.

Take the given number and the first 3 prime factors and the number of them as powers

N = Xa × Yb × Zc

40 would be 40 = 2 * 20.  20 isn't prime so we factor that further. 40 = 2 * (10 * 2). 10 isn't prime. 40 = 2 * 2 * 2 * 5. or N = 2^3 * 5^1 * 1^1

Total number of factors can be calculated using

N = (a+1)(b+1)(c+1)  

In the case of 40 there are 4 factors. 3+1*1+1*1+1

4*2*2 = 16... well not quite

we remove the factor of c because of the 1 to the 1st power.  but that leaves 8. we can see that there are only 4 elements.  Three of the 2 and one 5. 

well, we're forgetting the negatives.  So you divide by 2. That leaves 4 factors which is what we have.

Irrelevant 

Now this is great info to have.  However, it doesn't help us here.  I will tell you that the given number here has 4 prime factors.  That means it comes out to 1+1 * 1+1 * 1+1 or 8 then divide by 2 for the negative numbers.  That number was specifically picked as it has only 4 factors and all of them are prime.  This method could be used to check the answer to make sure that all cases have been found.  However, the first prime in this case is the 20th prime number 71.  So this strategy for this problem doesn't really help us.

So how will we approach this?

NOTE: I did find after I solved this that some people use a math principal called the Sieve of Eratosthenes   I was unaware this existed but it's an interesting read.

Rust has a crate for that.

primes

once we use the crate, we can then iterate through all the prime factors of a number.

use primes;

fn main() { 

     println!("{:?}", primes::factors(600851475143)); 

}

Boom. We have a return with 4 values.

we can even make a function to accept any value.

use primes;

fn main(){

pr_fac(600851475143)

}

fn pr_fac(x: u64){

println!("{:?}", primes::factors(x));

}

That works. 

We can go on.  Basically, what I learned from this is you don't have to reinvent the wheel.  We all have built on the people before us.  We extend their work.  While I can certainly make a brute force function that finds all the primes and loops through and ... Yeah that's how I approached it with python.

Nope, there's an app for that, there's a crate for that.  That isn't to say this is the best way.  I realize, it's kind of cheap and a little lazy.  Shrug.

EDIT: Btw if you just want the largest change the following

println!("{:?}", primes::factors(x));

to...

println!("{:?}", primes::factors(x).pop());

will return the last value in the Vec

Second EDIT: it comes after EDIT but before third edits...

so I forgot to look through and go over the answers in Rust that were posted before.

Most of them are as I described the brute force approach above.  They work just fine and there's no issue.  I also didn't time mine cause rust playground isn't fun and I know I could do it on my computer but I like there's as a common benchmark among all the answers on here. so... yeah

Other Users Responses

User davxy submitted this yesterday 1/2/21

const NUM: u64 = 600851475143;

fn main() {

    let mut val = NUM;

    // Fast div by two

    while val & 1 == 0 {

        val >>= 1;

    }

    let mut i = 3;

    while val != 1 {

        if val % i == 0 {

            val /= i;

        } else {

            i += 2;

        }

    }

    println!("{}", i);

}

NOTE: Writing this after evaluating this code. davxy knows a thing or two... just saying.

Not sure what's going on here at a glance. I'll start at the top.

He declares the constant NUM as the number in question. He then assigns the value of the constant to a variable he's made mutable. 

Next he "fast divide by two" --

while val & 1 == 0 do this thing... val >>=1

So I looked up val >>= 1 and it references variable >>= expression right-shift and assignment.

I've never seen this before.  According to stack overflow, left shift by 1 is equal to multiplying by base 2.  Right shift by 1 is equal to dividing by base 2.  So val >>= 1 is the same as val = val >> 1 which is the same as val / (2^1).   

the example they give is pretty neat. Basically, you take the binary value of a number say 16.  16 in binary is 10000.  or 1 in the 16th's place.  if you shift it to the right (divide) you pull it down to 1000 or 1 in the 8th's place.  You've divided it by 2.  That's what's going on here.  I didn't even know that was an option. That's awesome.

Back to the val & 1 == 0 thing.  It says it could be a few things but in this context looks like a bitwise AND.  Under bitwise opporators, it explains it as it performs a boolean and operation on each of the arguments.  So a & b will resolve true/false and then... operation? and then that is evaluated again against 0 which resolves to another boolean.

According to the wiki on bitwise opps, the & bitwise compares both equal length numbers in biary and compares the corresponding values to each other.

    0101 (decimal 5)
AND 0011 (decimal 3)
  = 0001 (decimal 1)

Each bit is multiplied together.  in this case 0 and 0 in the 8th's place resolve to 0.  the 1 (in decimal 5) multiplies by the 0 (in decimal 3), both in the 4's place, resolving to 0.  The 0 (in decimal 5) multiplies by 1 (in decimal 3), in the 2's place, resolving to 0.  Finally, the 1's (in both decimal 5 and 3) in the one's place resolve to 1.  So the bitwise AND value of 5 and 3 is 1.

Bring that back to our current discussion.

val & 1 == 0

val in binary is 

1000101111100101100010011110101011000111  ... and the binary value of 1 at equal length is 

000000000000000000000000000000000000001

So what this is saying is that while val & 1, in binary form, resolve the bitwise and function and resolve to 0, move the bits over to the right by 1, effectively dividing the whole number by 2.

This is interesting that he did this because it means he added it knowing that it needed to be a first step logically even though the given number resolves to 1 and never runs the while.

 The rest of this runs off the principal of the odd numbers can only be prime after 2. 

So there's a variable i that = 3.  if the val does not equal 1 then evaluate the bool for val divided by i has no remainder.  if it does then divide val by i.  if not then add 2 to i and repeat.  once you've reduced val to 1, you know have an i value equal to the largest prime number that is a factor of the given number.

Project Euler - Rust Problem 2

 https://projecteuler.net/problem=2

Problem 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Fibonacci sequences have always given me trouble.

The basic idea is that you are dealing with 3 terms at a time.

to start = 0,1,1

the first term 0 plus the second term 1 is equal to the third term 1.  Then we can move those along.  

If a is equal to the first term, b is equal to the second term, c is equal to the third term.  Now we have variables with names.

So we let mut a = 0;

let mut b = 1;

let mut c = 1;

To move through the terms, we need a loop of some kind.  We could use a for loop if we knew how many terms we would go through.  Since this isn't known, we ditch the for loop.  

Since the problem is giving us an upper limit, a while or do until loop would work great.  There is no do until loop in rust.  That leaves the while loop.

While c (the furthest term) is less than 4 million, do this code.

Here we can implement the basic logic needed to run through the Fibonacci sequence. I'm just glad that I don't have to store the values then go through them.  That would make this a bit more complex.

Loop

In the loop, we can just set a equal to b, b equal to c, and then c equal to a + b.  

This logic only goes through the sequence until c is greater than the upper limit.  

But that doesn't do anything.

Sum will still = 0.

We have to add c to the sum value.  But not every time.  only IF it's even, aka evenly divisible by 2.

So we add the if c % 2== 0{ sum += c;} logic and now all is right with the world.

 

fn main() {

    let mut sum: i32 = 0;

    let mut a: i32 = 0;

    let mut b: i32 = 1;

    let mut c: i32 = 1;

    

    while c < 4000000{

        a = b;

        b = c;

        c = a + b;

        if c %2 == 0{

            sum += c;

        }

        

    } 

    println!("{}", sum);

}

run time 1.05 seconds.

I would compare the other answers but honestly there's only one other rust answer it is very long and a bit complicated for reasons... I don't really understand.  I also couldn't get it to run in the playground.

I'm sure there are other ways to approach this.  I'm sure this isn't the greatest way to handle this.  We'll see, the more I learn.

Project Euler - Rust Problem 1

https://projecteuler.net/problem=1

 Project Euler is a site with challenges that people solve with programs and then submit that code to be commented on.  Normally, there's not a lot of comments unless you have a unique approach.  That's fine.

I've solved many of them in python but I'm going to go through them with Rust.

Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

The problem is asking that we find all of the natural numbers that are below 1000 that are multiples of 3 or 5. When we find them, add them together and then give the sum.

Natural Numbers are integers that are positive. So any whole number below 1000.

first we have to go through all those numbers.

for n in 0..1000 {}

A for loop will do the trick just fine.  0..1000 runs through all the numbers up to but not including 1000.  I could start at 3 instead of 0, 3..1000.  That would be fine as well since I know that 0, 1, and 2 aren't multiples of 3 or 5.

In the loop, we need to determine if the number (n) is divisible by 3 or 5.  One at a time, we can use simple if and else if statements.

if n%3 == 0{}

else if n%5 == 0{}

n % 3 == 0  

If we take n, the given number as we loop through, and divide it by 3, will it do so evenly or will there be a remainder?  If there's no remainder, we get 0.  The % used here will give us this answer.  The statement n%3 == 0 will result in a true or false.

The same is true of the else if statement.

Great! We have the logic for going through every number, 0 to 1000 and then figuring out if it's a multiple of 3 or 5.

We don't need an else statement.  If the given number (n) is not divisible by 3 or 5, then we will do nothing with it and can continue on.

Lastly, we need something to hold the sum of the values as we go through.

let mut sum: i32 = 0;

The variable sum is declared as mutable as we will need to change the value every time we find a multiple.

Finally, we need some way to see what the final value is.  We'll use the print to console macro for this.

The final code might look like this.

let mut sum: i32 = 0;

for n in 0..1000{

    if n%3 == 0{

        sum += n;

    }

    else if n%5 == 0{

        sum += n;

    }

}

println!("{}", sum);

 

Now I freely admit that this is not an inspired solution.  It doesn't take into account any kind of performance.  It's pretty brute force as it is but it's a beginner problem to highlight beginner problems in code.

This solution comes in at 1.29 seconds.

A more elegant approach

my friend showed me a way to make this a little more compact.

    let x = (0..1000).collect::<Vec<i32>>();

    let x: i32 = x.iter().filter(|&n| n%3 == 0 || n%5 == 0).sum();

    dbg!(x);

First, he declared a variable x as a vector collecting all the values from 0 to 1000.

Then he declared x as a number using shadowing.  Shadowing is convenient because it allows you to not only change the value of a variable but the type.  You're basically forcing the variable x as it exists to leave scope and release it's name and then assign it's name to a new value.  In this case, he used shadowing to iterate (iter()) through all the values in the vector and then filter out only the values that are divisble by 3 and 5 evenly.  Finally we added them altogether.

He did this in one line using what's called a Closure.  It's similar to a lambda in python.  
https://doc.rust-lang.org/rust-by-example/fn/closures.html

The dbg! macro is a debug macro that prints things to the console.  The rust documentation recommends that using this feature not be used, recommending the debug! macro from the log crate.  However, this is not a final release of a program and is simply a learning tool.

The logic is very elegant and works just the same as my code but it is smaller.  On Rust Playground it ran in 0.91 seconds versus the 1.3 seconds that my original code did.  It's not surprising really.  

Other solutions from other users -

Another user (forrin ) using Rust, posted this solution.

fn main() { println!("Result: {}", basic_solution(999)); } fn basic_solution(target: i32) -> i32 { let mut sum = 0; for n in 1..=target { if n % 3 == 0 || n % 5 == 0 { sum+= n; } } return sum; }

This solution is fine. It does basically what mine does except he isolated it into a function and filtered out the if/else if to a if this or that.

Runs 1.25seconds on Rust playground.

Another solution, similar to my friend's.

fn main() {

    let bound : i32 = 1000;

    println!("out {}", (1..bound).filter(|&n| n % 3 == 0 || n % 5 == 0).sum::<i32>().to_string())

}

This one filters the same but does all in the same line.  While I do like this solution and it runs at a 0.89 seconds on rust playground, it's hard to read and hard to understand at a glance what is going on.

Finally, another user (DMDM2 ) posted this solution, similar to my original answer.

let mut sum = 0; for x in 0..1000 { if (x % 3 == 0) | (x % 5 == 0) { sum += x; } } println!("Sum is: {}", sum);

This answer runs at 1.03 seconds. Faster than above, I assumed it's because the above user called another function.  However, if you remove the function call and put everything in the main scope, it still runs at 1.39, slower than above and slower than here.

let's compare the two answers from forrin and DMDM2 side by side.

Overall time is 1.25 seconds (forrin)  versus  1.03 seconds (DMDM2)

Before I continue, I'm not trying to call either of them out.  My solution for this wasn't exactly inspired.  I'm simply trying to delve into the workings of our answers and account for the performance differences.

We've already discussed that removing the function call actually makes it slower.

So let's compare the logic after the function call.

let mut sum = 0;

That's the same.  We all have to have a container to put the answer.

for n in 1..=target  vs for x in 0..1000

If we run 0..=999 on the right, we actually add some time on.  This makes sense, given that instead of stopping at a limit, we're evaluating if the number is = to 999 and only stopping after that.  

other than the left side looking for a variable and then referencing that value every time it evaluates (if it is running how I think it is and correct me if I'm wrong), the for loop is the same.

Once the for loop is concluded, the function on the left then passes the value back to the main function and prints it.  The one on the right just prints the variable.

I'm going to assume that the extra step of passing through a function call makes up some of that time.  I would love to know exactly what the differences here are.  Let me know if you have any thoughts about this below.