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

Published on 12 May 2024 09:40 PM
#Setl

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

Source code in the setl programming language

program zsigmondy;
    pairs := [[2, 1], [3, 1], [4, 1], [5, 1], [6, 1], [7, 1],
              [3, 2], [5, 3], [7, 3], [7, 5]];

    loop for [a, b] in pairs do
        print("Zsigmondy(n, " + str a + ", " + str b + ")");
        loop for n in [1..18] do
            putchar(str zs(n, a, b) + " ");
        end loop;
        print;
    end loop;

    proc zs(n,a,b);
        dn := a**n - b**n;
        divs := divisors(dn);
        if #divs = 1 then return dn; end if;

        loop for m in [1..n-1] do
            dm := a**m - b**m;
            divs -:= {d : d in divs | gcd(dm, d) > 1};
        end loop;
        return max/divs;
    end proc;

    proc divisors(n);
        ds := {d : d in {1..floor(sqrt(n))} | n mod d=0};
        return ds + {n div d : d in ds};
    end proc;

    proc gcd(a,b);
        loop while b/=0 do
            [a, b] := [b, a mod b];
        end loop;
        return a;
    end proc;
end program;

You may also check:How to resolve the algorithm String matching step by step in the Quackery programming language
You may also check:How to resolve the algorithm The Name Game step by step in the J programming language
You may also check:How to resolve the algorithm Parametric polymorphism step by step in the Scala programming language
You may also check:How to resolve the algorithm FTP step by step in the UNIX Shell programming language
You may also check:How to resolve the algorithm Minimum positive multiple in base 10 using only 0 and 1 step by step in the FreeBASIC programming language