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

Published on 12 May 2024 09:40 PM
#Nim

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

Source code in the nim programming language

import std/[algorithm, math, strformat]

func isPrime(n: Natural): bool =
  if n < 2: return false
  if (n and 1) == 0: return n == 2
  if n mod 3 == 0: return n == 3
  var k = 5
  var delta = 2
  while k * k <= n:
    if n mod k == 0: return false
    inc k, delta
    delta = 6 - delta
  result = true

func divisors(n: Positive): seq[int] =
  for d in 1..sqrt(n.toFloat).int:
    if n mod d == 0:
      result.add d
      if n div d != d:
        result.add n div d
  result.sort()

func zs(n, a, b: Positive): int =
  let dn = a^n - b^n
  if dn.isPrime: return dn
  var divs = dn.divisors
  for m in 1..<n:
    let dm = a^m - b^m
    for i in countdown(divs.high, 1):
      if gcd(dm, divs[i]) != 1:
        divs.delete i
  result = divs[^1]

const N = 15
for (a, b) in [(2, 1), (3, 1), (4, 1), (5, 1), (6, 1), (7, 1), (3, 2), (5, 3), (7, 3), (7, 5)]:
  echo &"Zsigmondy(n, {a}, {b}) – First {N} terms:"
  for n in 1..N:
    stdout.write zs(n, a, b), ' '
  echo '\n'

You may also check:How to resolve the algorithm N-queens problem step by step in the SQL PL programming language
You may also check:How to resolve the algorithm Yellowstone sequence step by step in the RPL programming language
You may also check:How to resolve the algorithm Hilbert curve step by step in the Processing programming language
You may also check:How to resolve the algorithm Attractive numbers step by step in the C programming language
You may also check:How to resolve the algorithm Binary digits step by step in the Picat programming language