Code for finding the totient function of a number.

euler70.rs

#[warn(non_camel_case_types)];

/*
Euler Challenge #70

Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.
The number 1 is considered to be relatively prime to every positive number, so φ(1)=1.

Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180.

Find the value of n, 1 < n < 10^7, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.
*/

extern mod extra;

use std::float::{sqrt,ceil};
use extra::sort;
use std::uint::{range,range_step};
use std::vec::from_fn;

// based on vec::each_permutation
// I'm not sure what the return value of vec::each_permutation is; it seems to always return true?
// Here, return value is "ran to completion"
fn each_combination<T: Copy>(l: &[T], n: uint, fun: &fn(combo: &[T]) -> bool) -> bool {
    //let x : ~[uint] = copy l;
    //let longl : ~[~[uint]] = ~[x];
    if(n == 0){
        return fun([]);
    };
    if(l.len() < n){return true;}
    if(l.len() == n){
        return fun(l);
    };
    
    let sl = l.slice(1, l.len());
    
    do each_combination(sl, n-1) |sub_combo| {
        let grown : ~[T] = do from_fn(n) |i| {
            match i {
                0 => copy l[0],
                _ => copy sub_combo[i-1]
            }
        };
        fun(grown)
    };
    
    if !each_combination(sl, n, fun){
        // finished early
        return false;
    }
    true
}


// Find all subsets of a set
fn subsets<T: Copy>(l: &[T], fun: &fn(combo: &[T]) -> bool) -> bool {
    do range(0,1+l.len()) |n| {
        do each_combination(l, n) |sub_combo| {
            fun(sub_combo)
        }
    }
}

// Find the first factor (other than 1) of a number
fn firstfac(x: uint) -> uint {
    let m = ceil(sqrt(x as float) as f64) as uint;
    if (x % 2 == 0){return 2;};
    for range_step(3,m+1,2) |n| {
        if (x % n == 0){return n;};
    }
    return x;
}

// Find all prime factors of a number
fn factors(x: uint) -> ~[uint] {
    let mut lst : ~[uint] = ~[];
    let mut curn = x;
    loop {
        let m = firstfac(curn);
        lst = lst + [m];
        if(m == curn){break}
        else{curn /= m};
    }
    return lst
}

// Find all unique prime factors of a number
fn factors1(x: uint) -> ~[uint] {
    let mut lst : ~[uint] = ~[];
    let mut curn = x;
    loop {
        let m = firstfac(curn);
        lst = lst + [m];
        if(curn == m){break;}
        while(curn % m == 0){curn /= m;}
        if(curn == 1){break;}
    }
    return lst
}

fn totient(n: uint) -> uint {
    if(n==1){return 1};
    let facs = factors1(n);
    //~ println(fmt!("totient(%?): facs %?",n,facs));
    
    let mut T = n;
    
    for subsets(facs) |clist| {
        if(clist.len() == 0) {loop};
        //~ if(clist.len() == facs.len()) {loop};
        let fullfac = do std::iter::product |f| { clist.iter().advance(f) };
        let count = n / fullfac;
        //~ println(fmt!("totient(%?): facs %? clist %?, T %?, count %?",n,facs,clist,T,count));
        match (clist.len() % 2) {
            0 => T += count,
            _ => T -= count
        }
    }
    
    T
}

fn sorted_str(s: &str) -> ~str {
    let mut sl : ~[u8] = from_fn(s.len(), |i| s[i]);
    sort::tim_sort(sl);
    return std::str::from_bytes(sl);
}

fn are_permutations(n: uint, m: uint) -> bool {
    let s1 = fmt!("%u", n);
    let mut sv1 : ~[u8] = from_fn(s1.len(), |i| s1[i]);
    sort::tim_sort(sv1);
    
    let s2 = fmt!("%u", m);
    let mut sv2 : ~[u8] = from_fn(s2.len(), |i| s2[i]);
    sort::tim_sort(sv2);
    
    sv1 == sv2
}

fn main() {
    let mut bestr = 10.0;
    
    let bignum = 100000;
    
    for range(2, bignum) |n| {
        let t = totient(n);
        if(are_permutations(n, t)){
            let r = (n as float)/(t as float);
            if(r < bestr){
                println(fmt!("%u -> %u , %?", n, t, r));
                bestr = r;
            }
        }
    };
}