Zsigmondy numbers: Difference between revisions
Thundergnat (talk | contribs) New draft task and Raku example |
Thundergnat (talk | contribs) m →{{header|Raku}}: short circuit, succeed early |
||
Line 62: | Line 62: | ||
(1..∞).map: -> $n { |
(1..∞).map: -> $n { |
||
my @divisors = divisors(@aexp[$n] - @bexp[$n]).sort: -*; |
my @divisors = divisors(@aexp[$n] - @bexp[$n]).sort: -*; |
||
@divisors.first: -> $d { all (1..^$n).map: -> $m { (@aexp[$m] - @bexp[$m]) gcd $d == 1 } } |
|||
} |
} |
||
} |
} |
Revision as of 16:04, 23 September 2022
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.
- E.G.
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, there are none coprime to all of 3, 7, 15, 31 (but 1 is always included) so Zs(6,2,1) = 1.
If a particular an - bn is prime, than Zs(n,a,b) will be equal to that prime. 25 - 15 = 31 so Zs(5,2,1) = 31.
- Task
- Write a general routine (function, procedure, whatever) to find the Zsigmondy number sequence given a set of radices.
- Use that routine to generate the first several elements, (at least 10), for the following radix sets.
- (2,1)
- (3,1)
- (4,1)
- (5,1)
- (6,1)
- (7,1)
- (3,2)
- (5,3)
- (7,3)
- (7,5)
- See also
- OEIS:A064078 - Zsigmondy numbers for a = 2, b = 1
- OEIS:A064077 - Zsigmondy numbers for a = 3, b = 1
- OEIS:A064080 - Zsigmondy numbers for a = 4, b = 1
- OEIS:A064081 - Zsigmondy numbers for a = 5, b = 1
- OEIS:A064082 - Zsigmondy numbers for a = 6, b = 1
- OEIS:A064083 - Zsigmondy numbers for a = 7, b = 1
- OEIS:A109325 - Zsigmondy numbers for a = 3, b = 2
- OEIS:A109347 - Zsigmondy numbers for a = 5, b = 3
- OEIS:A109348 - Zsigmondy numbers for a = 7, b = 3
- OEIS:A109349 - Zsigmondy numbers for a = 7, b = 5
Raku
First twenty elements of each.
use Prime::Factor;
sub Zsigmondy ($a, $b) {
my @aexp = 1, $a, * × $a … *;
my @bexp = 1, $b, * × $b … *;
(1..∞).map: -> $n {
my @divisors = divisors(@aexp[$n] - @bexp[$n]).sort: -*;
@divisors.first: -> $d { all (1..^$n).map: -> $m { (@aexp[$m] - @bexp[$m]) gcd $d == 1 } }
}
}
for '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)
-> $name, $seq { say "\n$name:\n" ~ Zsigmondy(|$seq)[^20] }
- Output:
A064078: Zsigmondy(n,2,1): 1 3 7 5 31 1 127 17 73 11 2047 13 8191 43 151 257 131071 19 524287 41 A064079: Zsigmondy(n,3,1): 2 1 13 5 121 7 1093 41 757 61 88573 73 797161 547 4561 3281 64570081 703 581130733 1181 A064080: Zsigmondy(n,4,1): 3 5 7 17 341 13 5461 257 1387 41 1398101 241 22369621 3277 49981 65537 5726623061 4033 91625968981 61681 A064081: Zsigmondy(n,5,1): 4 3 31 13 781 7 19531 313 15751 521 12207031 601 305175781 13021 315121 195313 190734863281 5167 4768371582031 375601 A064082: Zsigmondy(n,6,1): 5 7 43 37 311 31 55987 1297 46873 1111 72559411 1261 2612138803 5713 1406371 1679617 3385331888947 46441 121871948002099 1634221 A064083: Zsigmondy(n,7,1): 6 1 19 25 2801 43 137257 1201 39331 2101 329554457 2353 16148168401 102943 4956001 2882401 38771752331201 117307 1899815864228857 1129901 A109325: Zsigmondy(n,3,2): 1 5 19 13 211 7 2059 97 1009 11 175099 61 1586131 463 3571 6817 129009091 577 1161737179 4621 A109347: Zsigmondy(n,5,3): 2 1 49 17 1441 19 37969 353 19729 421 24325489 481 609554401 10039 216001 198593 381405156481 12979 9536162033329 288961 A109348: Zsigmondy(n,7,3): 4 5 79 29 4141 37 205339 1241 127639 341 494287399 2041 24221854021 82573 3628081 2885681 58157596211761 109117 2849723505777919 4871281 A109349: Zsigmondy(n,7,5): 2 3 109 37 6841 13 372709 1513 176149 1661 964249309 1801 47834153641 75139 3162961 3077713 115933787267041 30133 5689910849522509 3949201