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

Published on 12 May 2024 09:40 PM
#Wren

How to resolve the algorithm Zsigmondy numbers step by step in the Wren 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 Wren programming language

Source code in the wren programming language

import "./math" for Int
import "./fmt" for Fmt

var zs = Fn.new { |n, a, b|
    var dn = a.pow(n) - b.pow(n)
    if (Int.isPrime(dn)) return dn
    var divs = Int.divisors(dn)
    var dms = (1...n).map { |m| a.pow(m) - b.pow(m) }.toList
    for (i in divs.count-1..1) {
        if (dms.all { |dm| Int.gcd(dm, divs[i]) == 1 }) return divs[i]
    }
    return 1
}

var abs = [ [2, 1], [3, 1], [4, 1], [5, 1], [6, 1], [7, 1], [3, 2], [5, 3], [7, 3], [7, 5] ]
for (ab in abs) {
    var a = ab[0]
    var b = ab[1]
    var lim = 20
    if (a == 7 && b != 3) lim = 18
    System.print("Zsigmony(n, %(a), %(b)) - first %(lim) terms:")
    Fmt.print("$d", (1..lim).map { |n| zs.call(n, a, b) }.toList)
    System.print()
}

import "./big" for BigInt
import "./seq" for Lst
import "./fmt" for Fmt

var divisors = Fn.new { |n|
    var factors = BigInt.primeFactors(n)
    var divs = [BigInt.one]
    for (p in factors) {
        for (i in 0...divs.count) divs.add(divs[i]*p)
    }
    return Lst.prune(divs.sort { |i, j| i >= j })
}

var zs = Fn.new { |n, a, b|
    a = BigInt.new(a)
    b = BigInt.new(b)
    var dn = a.pow(n) - b.pow(n)
    if (dn.isPrime) return dn
    var divs = divisors.call(dn)
    var dms = (1...n).map { |m| a.pow(m) - b.pow(m) }.toList
    for (div in divs) {
        if (dms.all { |dm| BigInt.gcd(dm, div) == 1 }) return div
    }
    return BigInt.one
}

var abs = [ [2, 1], [3, 1], [4, 1], [5, 1], [6, 1], [7, 1], [3, 2], [5, 3], [7, 3], [7, 5] ]
var lim = 20
for (ab in abs) {
    var a = ab[0]
    var b = ab[1]
    System.print("Zsigmony(n, %(a), %(b)) - first %(lim) terms:")
    Fmt.print("$i", (1..lim).map { |n| zs.call(n, a, b) }.toList)
    System.print()
}

You may also check:How to resolve the algorithm Semiprime step by step in the PL/M programming language
You may also check:How to resolve the algorithm String prepend step by step in the PicoLisp programming language
You may also check:How to resolve the algorithm Averages/Simple moving average step by step in the Icon and Unicon programming language
You may also check:How to resolve the algorithm Flatten a list step by step in the WDTE programming language
You may also check:How to resolve the algorithm Top rank per group step by step in the PowerShell programming language