login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A323748 Square array read by ascending antidiagonals: the n-th row lists the Zsigmondy numbers for a = n, b = 1, that is, T(n,k) = Zs(k, n, 1) is the greatest divisor of n^k - 1 that is coprime to n^m - 1 for all positive integers m < k, with n >= 2, k >= 1. 4
1, 2, 3, 3, 1, 7, 4, 5, 13, 5, 5, 3, 7, 5, 31, 6, 7, 31, 17, 121, 1, 7, 1, 43, 13, 341, 7, 127, 8, 9, 19, 37, 781, 13, 1093, 17, 9, 5, 73, 25, 311, 7, 5461, 41, 73, 10, 11, 91, 65, 2801, 31, 19531, 257, 757, 11, 11, 3, 37, 41, 4681, 43, 55987, 313, 1387, 61, 2047, 12, 13, 133, 101, 7381, 19, 137257, 1297, 15751, 41, 88573, 13 (list; table; graph; refs; listen; history; text; internal format)
OFFSET
2,2
COMMENTS
By Zsigmondy's theorem, T(n,k) = 1 if and only if n = 2 and k = 1 or 6, or n + 1 is a power of 2 and k = 2.
All prime factors of T(n,k) are congruent to 1 modulo k.
If T(n,k) = p^e where p is prime, then p is a unique-period prime in base n. By the property above, k must be a divisor of p - 1.
There are many squares of primes in the third, fourth or sixth column (e.g., T(7,4) = 25 = 5^2, T(22,3) = T(23,6) = 169 = 13^2, T(41,4) = 841 = 29^2, etc.). Conjecturally all other prime powers with exponent >= 2 in the table excluding the first two columns are T(3,5) = 121 = 11^2, T(18,3) = T(19,6) = 343 = 7^3 and T(239,4) = 28561 = 13^4.
LINKS
Jianing Song, Notes for A323748
FORMULA
T(n,k) = A000265(n+1) if k = 2, otherwise T(n,k) = Phi_k(n)/gcd(Phi_k(n), k) = A253240(k,n)/gcd(A253240(k,n), k) where Phi_k is the k-th cyclotomic polynomial.
T(n,k) = A000265(n+1) if k = 2, Phi_k(n)/p if k = p^e*ord(n,p) != 2 for some prime p and exponent e >= 1, Phi_k(n) otherwise, where ord(n,p) is the multiplicative order of n modulo p.
T(n,k) = Phi_k(n)/A342255(n,k) for n >= 2, k != 2.
EXAMPLE
In the following list, "*" identifies a prime power.
Table begins
n\k | 1 2 3 4 5 6 7 8
2 | 1 , 3*, 7*, 5*, 31*, 1 , 127*, 17*
3 | 2*, 1 , 13*, 5*, 121*, 7*, 1093*, 41*
4 | 3*, 5*, 7*, 17*, 341 , 13*, 5461 , 257*
5 | 4*, 3*, 31*, 13*, 781 , 7*, 19531*, 313*
6 | 5*, 7*, 43*, 37*, 311*, 31*, 55987*, 1297*
7 | 6 , 1 , 19*, 25*, 2801*, 43*, 137257 , 1201*
8 | 7*, 9*, 73*, 65 , 4681 , 19*, 42799 , 4097
9 | 8*, 5*, 91 , 41*, 7381 , 73*, 597871 , 3281
10 | 9*, 11*, 37*, 101*, 11111 , 91 , 1111111 , 10001
11 | 10 , 3*, 133 , 61*, 3221*, 37*, 1948717 , 7321*
12 | 11*, 13*, 157*, 145 , 22621*, 133 , 3257437 , 20737
The first few columns:
T(n,1) = n - 1;
T(n,2) = A000265(n+1);
T(n,3) = (n^2 + n + 1)/3 if n == 1 (mod 3), n^2 + n + 1 otherwise;
T(n,4) = (n^2 + 1)/2 if n == 1 (mod 2), n^2 + 1 otherwise;
T(n,5) = (n^4 + n^3 + n^2 + n + 1)/5 if n == 1 (mod 5), n^4 + n^3 + n^2 + n + 1 otherwise;
T(n,6) = (n^2 - n + 1)/3 if n == 2 (mod 3), n^2 - n + 1 otherwise;
T(n,7) = (n^6 + n^5 + ... + 1)/7 if n == 1 (mod 7), n^6 + n^5 + ... + 1 otherwise;
T(n,8) = (n^4 + 1)/2 if n == 1 (mod 2), n^4 + 1 otherwise;
T(n,9) = (n^6 + n^3 + 1)/3 if n == 1 (mod 3), n^6 + n^3 + 1 otherwise;
T(n,10) = (n^4 - n^3 + n^2 - n + 1)/5 if n == 4 (mod 5), n^4 - n^3 + n^2 - n + 1 otherwise;
T(n,11) = (n^10 + n^9 + ... + 1)/11 if n == 1 (mod 11), n^10 + n^9 + ... + 1 otherwise;
T(n,12) = n^4 - n^2 + 1 (12 is not of the form p^e*d for any prime p, exponent e >= 1 and d dividing p-1).
MATHEMATICA
Table[Function[n, SelectFirst[Reverse@ Divisors[n^k - 1], Function[m, AllTrue[n^Range[k - 1] - 1, GCD[#, m] == 1 &]]]][j - k + 2], {j, 12}, {k, j}] // Flatten (* or *)
Table[Function[n, If[k == 2, #/2^IntegerExponent[#, 2] &[n + 1], #/GCD[#, k] &@ Cyclotomic[k, n]]][j - k + 1], {j, 2, 13}, {k, j - 1}] // Flatten (* Michael De Vlieger, Feb 02 2019 *)
PROG
(PARI) T(n, k) = if(k==2, (n+1)>>valuation(n+1, 2), my(m = polcyclo(k, n)); m/gcd(m, k))
CROSSREFS
Rows 1..6 are A064078, A064079, A064080, A064081, A064082 and A064083.
Sequence in context: A120653 A323850 A236937 * A116155 A365991 A144149
KEYWORD
nonn,tabl
AUTHOR
Jianing Song, Jan 25 2019
EXTENSIONS
Zs notation in Name changed by Jeppe Stig Nielsen, Oct 16 2020
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 02:23 EDT 2024. Contains 371264 sequences. (Running on oeis4.)