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

Published on 12 May 2024 09:40 PM
#J

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

Source code in the j programming language

dp=: -/@:(^/) NB. (a,b) dp n  is (a^n)-(b^n)
Zsigmondy=: dp (-.,)&.:q: (dp 1 }. i.)


   Zs=: Zsigmondy"1 0&(1x+i.20) NB. first 20 in sequence
   Zs 2 1
1 3 7 5 31 1 127 17 73 11 2047 13 8191 43 151 257 131071 19 524287 41
   Zs 3 1
2 1 13 5 121 7 1093 41 757 61 88573 73 797161 547 4561 3281 64570081 703 581130733 1181
   Zs 4 1
3 5 7 17 341 13 5461 257 1387 41 1398101 241 22369621 3277 49981 65537 5726623061 4033 91625968981 61681
   Zs 5 1
4 3 31 13 781 7 19531 313 15751 521 12207031 601 305175781 13021 315121 195313 190734863281 5167 4768371582031 375601
   Zs 6 1
5 7 43 37 311 31 55987 1297 46873 1111 72559411 1261 2612138803 5713 1406371 1679617 3385331888947 46441 121871948002099 1634221
   Zs 7 1
6 1 19 25 2801 43 137257 1201 39331 2101 329554457 2353 16148168401 102943 4956001 2882401 38771752331201 117307 1899815864228857 1129901
   Zs 3 2
1 5 19 13 211 7 2059 97 1009 11 175099 61 1586131 463 3571 6817 129009091 577 1161737179 4621
   Zs 5 3
2 1 49 17 1441 19 37969 353 19729 421 24325489 481 609554401 10039 216001 198593 381405156481 12979 9536162033329 288961
   Zs 7 3
4 5 79 29 4141 37 205339 1241 127639 341 494287399 2041 24221854021 82573 3628081 2885681 58157596211761 109117 2849723505777919 4871281
   Zs 7 5
2 3 109 37 6841 13 372709 1513 176149 1661 964249309 1801 47834153641 75139 3162961 3077713 115933787267041 30133 5689910849522509 3949201

You may also check:How to resolve the algorithm Sorting algorithms/Selection sort step by step in the Nim programming language
You may also check:How to resolve the algorithm Catamorphism step by step in the Maxima programming language
You may also check:How to resolve the algorithm Permutations by swapping step by step in the Rust programming language
You may also check:How to resolve the algorithm Function definition step by step in the XSLT programming language
You may also check:How to resolve the algorithm Terminal control/Ringing the terminal bell step by step in the Kotlin programming language