%I #33 Jan 04 2016 10:21:27
%S 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,
%T 18,15,21,16,20,19,19,20,25,19,21,22,26,21,27,22,26,27,25,24,32,26,29,
%U 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
%N 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.
%C Possibly related to Maillet's determinants.
%H Alexander Adam, <a href="https://oeis.org/wiki/User:Alexander_Adam#The_rank_of_the_modular_multiplication_table">Proof of the formula</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Maillet%27s_determinant">Maillet's determinant</a>
%F 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
%F a(n) = A000005(n) + A110654(n) - 2.
%e From _Alexander Adam_, Nov 10 2012, (Start)
%e a(2^m) = 2^(m-1) + m - 1.
%e Let p >= 3 be a prime number. Then a(p^m) = (p^m + 1) / 2 + m - 1.
%e a(625000) = a(2^3*5^7) = 2^2*5^7 + 4 * 8 - 2 = 312530. (end)
%t 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 *)
%o (PARI) a(n) = matrank(matrix(n,n,i,j,(i*j)%n))
%Y Cf. A218322, A055513, A203411, A000927.
%K nonn
%O 1,3
%A _Max Alekseyev_, Dec 01 2003
|