A088922 Consider the n X n matrix with entries (i*j mod n), where i,j=0..n-1; a(n) = rank of this matrix over the real numbers.
0, 1, 2, 3, 3, 5, 4, 6, 6, 7, 6, 10, 7, 9, 10, 11, 9, 13, 10, 14, 13, 13, 12, 18, 14, 15, 16, 18, 15, 21, 16, 20, 19, 19, 20, 25, 19, 21, 22, 26, 21, 27, 22, 26, 27, 25, 24, 32, 26, 29, 28, 30, 27, 33, 30, 34, 31, 31, 30, 40, 31, 33, 36, 37, 35, 39, 34, 38, 37, 41, 36, 46, 37, 39, 42, 42, 41, 45, 40, 48, 44, 43, 42, 52, 45, 45, 46, 50, 45, 55, 48, 50, 49, 49, 50, 58, 49, 53, 54, 57
Offset: 1
Keywords
Examples
From _Alexander Adam_, Nov 10 2012: (Start) a(2^m) = 2^(m-1) + m - 1. Let p >= 3 be a prime number. Then a(p^m) = (p^m + 1) / 2 + m - 1. a(625000) = a(2^3*5^7) = 2^2*5^7 + 4 * 8 - 2 = 312530. (End)
Links
- Alexander Adam, Proof of the formula
- Wikipedia, Maillet's determinant
Programs
-
Mathematica
a[n_] := MatrixRank[Table[Table[Mod[i * j, n], {j, 0, n - 1}], {i, 0, n - 1}]]; Array[a,100] (* Alexander Adam, Nov 10 2012 *) -
PARI
a(n) = matrank(matrix(n,n,i,j,(i*j)%n))
Formula
Let n = Prod_{i>0} p_i^{m_i} be the prime factorization of n. Then a(n) = floor((n + 1)/2) + Prod_{i>0} (m_i + 1) - 2. - Alexander Adam, Nov 10 2012
Comments