How to resolve the algorithm Zsigmondy numbers step by step in the Rust programming language

Published on 12 May 2024 09:40 PM
#Rust

How to resolve the algorithm Zsigmondy numbers step by step in the Rust programming language

Table of Contents

Problem Statement

Zsigmondy numbers n to a, b, are the greatest divisor of an - bn that is coprime to am - bm for all positive integers m < n.

Suppose we set a = 2 and b = 1. (Zs(n,2,1)) For each n, find the divisors of an - bn and return the largest that is coprime to all of am - bm, where m is each of the positive integers 1 to n - 1. When n = 4, 24 - 14 = 15. The divisors of 15 are 1, 3, 5, and 15. For m = 1, 2, 3 we get 2-1, 22-12, 23-13, or 1, 3, 7. The divisors of 15 that are coprime to each are 5 and 1, (1 is always included). The largest coprime divisor is 5, so Zs(4,2,1) = 5.

When n = 6, 26 - 16 = 63; its divisors are 1, 3, 7, 9, 21, 63. The largest divisor coprime to all of 1, 3, 7, 15, 31 is 1, (1 is always included), so Zs(6,2,1) = 1.

If a particular an - bn is prime, then Zs(n,a,b) will be equal to that prime. 25 - 15 = 31 so Zs(5,2,1) = 31.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Zsigmondy numbers step by step in the Rust programming language

Source code in the rust programming language

use itertools::{max, all};
use gcd::Gcd;
use divisors::get_divisors;

fn zsigmondy(a: u64, b: u64, n: u64) -> u64 {
    assert!(a > b);
    let dexpms: Vec<u64> = (1..(n as u32)).map(|i| a.pow(i) - b.pow(i)).collect();
    let dexpn: u64 = a.pow(n as u32) - b.pow(n as u32);
    let mut divisors = get_divisors(dexpn).to_vec(); // get_divisors(n) does not include 1 and n
    divisors.append(&mut [1, dexpn].to_vec());       // so add those
    let z = divisors.iter().filter(|d| all(dexpms.clone(), |k| Gcd::gcd(k, **d) == 1));
    return *max(z).unwrap();
}

fn main() {
    for (name, a, b) in [
        ("A064078: Zsigmondy(n,2,1)", 2, 1,),
        ("A064079: Zsigmondy(n,3,1)", 3, 1,),
        ("A064080: Zsigmondy(n,4,1)", 4, 1,),
        ("A064081: Zsigmondy(n,5,1)", 5, 1,),
        ("A064082: Zsigmondy(n,6,1)", 6, 1,),
        ("A064083: Zsigmondy(n,7,1)", 7, 1,),
        ("A109325: Zsigmondy(n,3,2)", 3, 2,),
        ("A109347: Zsigmondy(n,5,3)", 5, 3,),
        ("A109348: Zsigmondy(n,7,3)", 7, 3,),
        ("A109349: Zsigmondy(n,7,5)", 7, 5,),] {
        println!("\n{name}:");
        for n in 1..21 {
            print!("{} ", zsigmondy(a, b, n));
        }
    }
}

You may also check:How to resolve the algorithm Forward difference step by step in the Quackery programming language
You may also check:How to resolve the algorithm URL decoding step by step in the jq programming language
You may also check:How to resolve the algorithm Events step by step in the E programming language
You may also check:How to resolve the algorithm Scope modifiers step by step in the J programming language
You may also check:How to resolve the algorithm Search a list step by step in the Fortran programming language