Posts for: #Totient

Totients

In the past, I’ve implemented Euler’s totient function for shits and giggles. It’s not a hard exercise by any means, but it can be if you haven’t had education in math at a level to understand the formula.

$$\varphi(n) =n \prod_{p\mid n} \left(1-\frac{1}{p}\right)$$

Admittedly, I had to google what the hell is going on. Technically, that’s just the framework, there are more details that follow in the form of rules. However, it was definitely a fun exercise to implement it. I think today I’m going to commit to downloading the latest version of rust and compiling that old code to see how much data I can generate. It’s really about all I can do to keep myself from going insane having to watch this robot perform the same tasks over and over until it gets them right. Yes, I have to intervene occasionally, but most of these debugs are very “hands off”.

[]

Totient Calculator in C

Rewrote my totient calculator in C. It’s pretty much a direct translation of the excrement I wrote in Rust. Be gentle, there are obvious points that I miss completely in C that veterans in the ancient language would scoff heartily about. I don’t yet know what the hell a struct is for or the extents of threading. All in good time.

So here’s my uncommented and fully unnecessary data type usage.

[]

Euler’s Totient Function in Rust

Figured I’d write a much quicker varient of the Totient Function in Rust. Excellent language. I don’t have a grasp on the finer points available to Rustaceans, but I can hopefully put concurrency and whatnot to use at some point. The code is quick, but I know it can be quicker if I just spend some time putting it together.

This is the quick crap I dreamt up:

use std::env;

fn gcd(mut m: u64, mut n: u64) -> u64 {
   while m != 0 {
       let old_m = m;
       m = n % m;
       n = old_m;
   }
   n
}

fn totient(mut a: u64) -> u64 {
    let mut y = 0;
    let o = a;
    while a != 0 {
        if gcd(o, a) == 1 {
            y += 1;
        }
        a -= 1;
    }
    y
}

fn main() {
    let args: Vec<_> = env::args().collect();
    let n: u64 = args[1].parse::<u64>().unwrap();
    let m: u64 = args[2].parse::<u64>().unwrap();

    let x = (n..m).collect::<Vec<u64>>();

    for i in &x {
        let o = totient(*i);
        println!("{:?}, {:?}", i, o);
    }
    
}

The code should compile with no problems. Yes, I realize that u64 is overkill. No, my code will never require unsigned 2^64 integers. It may be a quirky choice, but whatever. Change to u32 as needed, though I’m sure it won’t be a problem for anyone.

[]