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

Author

Max Alekseyev, Dec 01 2003

Keywords

• nonn

Comments

Possibly related to Maillet's determinants.

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

Crossrefs

Cf. A218322, A055513, A203411, A000927.

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

a(n) = A000005(n) + A110654(n) - 2.