Search: a020478 -id:a020478
|
| |
|
|
A005353
|
|
Number of 2 X 2 matrices with entries mod n and nonzero determinant.
(Formerly M4254)
|
|
+10
5
|
|
|
|
0, 6, 48, 168, 480, 966, 2016, 3360, 5616, 8550, 13200, 17832, 26208, 34566, 45840, 59520, 78336, 95526, 123120, 147240, 181776, 219846, 267168, 307488, 372000, 433446, 505440, 580776, 682080, 762150, 892800, 999936, 1138368, 1284486
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
REFERENCES
|
T. Brenner, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
|
|
|
FORMULA
|
For prime n, a(n) = (n^2-1)(n-1)n. - T. D. Noe, Jan 12 2006
|
|
|
MATHEMATICA
|
Table[cnt=0; Do[m={{a, b}, {c, d}}; If[Det[m, Modulus->p] > 0, cnt++ ], {a, 0, p-1}, {b, 0, p-1}, {c, 0, p-1}, {d, 0, p-1}]; cnt, {p, 37}] (* T. D. Noe, Jan 12 2006 *)
f[p_, e_] := p^(2*e - 1)*(p^(e + 1) + p^e - 1); a[1] = 0; a[n_] := n^4 - Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Oct 31 2023 *)
|
|
|
PROG
|
(PARI) a(n) = {my(f = factor(n), p, e); n^4 - prod(i = 1, #f~, p = f[i, 1]; e = f[i, 2]; p^(2*e - 1)*(p^(e + 1) + p^e - 1)); } \\ Amiram Eldar, Oct 31 2023
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A240547
|
|
Number of non-congruent solutions of x^2 + y^2 + z^2 + t^2 == 0 mod n.
|
|
+10
5
|
|
|
|
1, 8, 33, 32, 145, 264, 385, 128, 945, 1160, 1441, 1056, 2353, 3080, 4785, 512, 5185, 7560, 7201, 4640, 12705, 11528, 12673, 4224, 18625, 18824, 26001, 12320, 25201, 38280, 30721, 2048, 47553, 41480, 55825, 30240, 51985, 57608, 77649, 18560, 70561, 101640
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
LINKS
|
|
|
|
FORMULA
|
Multiplicative, with a(2^e) = 2^(2e+1) for e>=1, a(p^e) = p^(2e-1)*(p^(e+1)+p^e-1) for p > 2, e>=1.
Sum_{k=1..n} a(k) ~ c * n^4 + O(n^3 * log(n)), where c = 5*Pi^2/(168*zeta(3)) = 0.244362... (Tóth, 2014). - Amiram Eldar, Oct 18 2022
|
|
|
EXAMPLE
|
For n=2 the a(2)=8 solutions are (0,0,0,0), (1,1,0,0), (1,0,1,0), (1,0,0,1), (0,1,1,0), (0,1,0,1), (0,0,1,1), (1,1,1,1).
|
|
|
MAPLE
|
A240547 := proc(n) local a, x, y, z, t ; a := 0 ; for x from 0 to n-1 do for y
from 0 to n-1 do for z from 0 to n-1 do for t from 0 to n-1 do if
(x^2+y^2+z^2+t^2) mod n = 0 mod n then a := a+1 ; fi; od; od ; od; od;
a ; end proc;
# alternative
a := 1;
for pe in ifactors(n)[2] do
p := op(1, pe) ;
e := op(2, pe) ;
if p = 2 then
a := a*p^(2*e+1) ;
else
a := a* p^(2*e-1)*(p^(e+1)+p^e-1) ;
end if;
end do:
a ;
end proc:
|
|
|
MATHEMATICA
|
b[2, e_] := 2^(2 e + 1);
b[p_, e_] := p^(2 e - 1)*(p^(e + 1) + p^e - 1);
a[n_] := Times @@ b @@@ FactorInteger[n];
|
|
|
PROG
|
(PARI) a(n) = my(m); if( n<1, 0, forvec( v = vector(4, i, [0, n-1]), m += (0 == norml2(v)%n))); m /* Michael Somos, Apr 07 2014 */
(PARI) a(n) = {my(f = factor(n), res = 1, start = 1, p, e, i); if(n % 2 == 0, res = 1<<(f[1, 2]<<1+1); start = 2); for(i = start, #f~, p = f[i, 1]; e = f[i, 2]; res*=(p^(e<<1-1)*(p^(e+1)+p^e-1))); res} \\ David A. Corneth, Jul 22 2018
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,mult
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A115075
|
|
Number of 2 X 2 symmetric matrices over Z(n) having determinant 0.
|
|
+10
2
|
|
|
|
1, 4, 9, 20, 25, 36, 49, 80, 99, 100, 121, 180, 169, 196, 225, 352, 289, 396, 361, 500, 441, 484, 529, 720, 725, 676, 891, 980, 841, 900, 961, 1408, 1089, 1156, 1225, 1980, 1369, 1444, 1521, 2000, 1681, 1764, 1849, 2420, 2475, 2116, 2209, 3168, 2695, 2900
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
LINKS
|
|
|
|
FORMULA
|
For squarefree n, a(n) = n^2.
Multiplicative with a(p^e) = p^(e)*(p^(e)+p^(e-1)-p^(ceiling(e/2)-1)).
Dirichlet g.f.: zeta(s-2) * zeta(2*s-3) / zeta(2*s-2).
Sum_{k=1..n} a(k) ~ (zeta(3)/(3*zeta(4))) * n^3. (End)
|
|
|
MATHEMATICA
|
Table[cnt=0; Do[m={{a, b}, {b, c}}; If[Det[m, Modulus->n]==0, cnt++ ], {a, 0, n-1}, {b, 0, n-1}, {c, 0, n-1}]; cnt, {n, 50}]
f[p_, e_] := p^e*(p^e + p^(e-1) - p^(Ceiling[e/2] - 1)); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Oct 31 2023 *)
|
|
|
PROG
|
(PARI) a(n) = {my(f = factor(n), p, e); prod(i = 1, #f~, p = f[i, 1]; e = f[i, 2]; p^e*(p^e + p^(e-1) - p^((e+1)\2 - 1))); } \\ Amiram Eldar, Oct 31 2023
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
mult,nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A181107
|
|
Triangle read by rows: T(n,k) is the number of 2 X 2 matrices over Z(n) having determinant congruent to k mod n, 1 <= n, 0 <= k <= n-1.
|
|
+10
2
|
|
|
|
1, 10, 6, 33, 24, 24, 88, 48, 72, 48, 145, 120, 120, 120, 120, 330, 144, 240, 198, 240, 144, 385, 336, 336, 336, 336, 336, 336, 736, 384, 576, 384, 672, 384, 576, 384, 945, 648, 648, 864, 648, 648, 864, 648, 648, 1450, 720, 1200, 720, 1200, 870, 1200, 720, 1200, 720
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
The n-th row is {T(n,0),T(n,1),...,T(n,n-1)}.
Let m denote the prime power p^e.
T(m,0) = A020478(m) = (p^(e+1) + p^e-1)*p^(2*e-1).
T(m,1) = A000056(m) = (p^2-1)*p^(3*e-2).
Sum_{k=1..n-1} T(n,k) = A005353(n).
T(n,1) = n*A007434(n) for n>=1 because A000056(n) = n*Jordan_Function_J_2(n).
T(2^n,1) = A083233(n) = A164640(2n) for n>=1. Proof: a(n):=T(2^n,1); a(1)=6, a(n)=8*a(n-1); A083233(1)=6 and A083233(n) is a geometric series with ratio 8 (because of its g.f.), too; A164640 = {b(1)=1, b(2)=6, b(n)=8*b(n-2)}.
T(2^n,0) = A165148(n) for n>=0, because 2*T(2^n,0) = (3*2^n-1)*4^n.
T(2^e,2) = A003951(e) for 2 <= e. Proof: T(2^e,2) = 9*8^(e-1) is a series with ratio 8 and initial term 72, as A003951(2...inf) is.
Working with consecutive powers of a prime p, we need a definition (0 <= i < e):
N(p^e,i):=#{k: 0 < k < p^e, gcd(k,p^e) = p^i} = (p-1)*p^(e-1-i). We say that these k's belong to i (respect to p^e). Note that N(p^e,0) = EulerPhi(p^e), and if 0 < k < p^e then gcd(k,p^e) = gcd(k,p^(e+1)). Let T(p^e,[i]) denote the common value of T(p^e,k)'s, where k's belong to i (q.v.PROGRAM); for example, T(p^e,[0]) = T(p^e,1). The number of the 2 X 2 matrices over Z(p^e), T(p^e,0) + Sum_{i=0..e-1} T(p^e,[i])*N(p^e,i) = p^(4e) will be useful.
On the hexagon property: Let prime p be given and let T(p^e,[0]), T(p^e,[1]), T(p^e,[2]), ..., T(p^e,[e-2]), T(p^e,[e-1]) form the e-th row of a Pascal-like triangle, e>=1. Let denote X(r,s) an element of the triangle and its value T(p^r,[s]). Let positive integers a and b given, so that the entries A(m-a,n-b), B(m-a,n), C(m,n+a), D(m+b,n+a), E(m+b,n), F(m,n-b) of the triangle form a hexagon spaced around T(p^m,[n]); if a=b=1 then they surround it. If A*C*E = B*D*F, then we say that the triangle T(.,.) has the "hexagon property". (In the case of binomial coefficients X(r,s) = COMB(r,s), the "hexagon property" holds (see [Gupta]) and moreover gcd(A,C,E) = gcd(B,D,F) (see [Hitotumatu & Sato]).)
Corollary 2.2 in [Brent & McKay] says that, for the d X d matrices over Z(p^e), (mutatis mutandis) T_d(p^e,0) = K*(1-P(d+e-1)/P(e-1)) and T_d(p^e,[i]) = K*(q^e)*((1-q^d)/(1-q))*P(d+i-1)/P(i), where q=1/p, K=(p^e)^(d^2), P(t) = Product_{j=1..t} (1-q^j), P(0):=1. (For the case d=2, we have T(p^e,[i]) = (p+1)*(p^(i+1)-1)*p^(3*e-i-2).) Due to [Brent & McKay], it can be simply proved that for d X d matrices the "hexagon property" is true. The formulation implies an obvious generalization: For the entries A(r,u), B(r,v), C(s,w), D(t,w), E(t,v), F(s,u) of the T_d(.,.)-triangle, a hexagon-like property A*C*E = B*D*F holds. This is false in general for the COMB(.,.)-triangle.
Another (rotated-hexagon-like) property: for the entries A(m-b1,n), B(m-a1,n+c2), C(m+a2,n+c2), D(m+b2,n), E(m+a2,n-c1), F(m-a1,n-c1) of the T_d(.,.)-triangle, the property A*C*E = B*D*F holds, if and only if 2*(a1 + a2) = b1 + b2. This is also in general false for COMB(.,.)-triangle.
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(a*b,k) = T(a,(k mod a))*T(b,(k mod b)) if gcd(a,b) = 1.
|
|
|
EXAMPLE
|
Triangle begins:
1;
10, 6;
33, 24, 24;
88, 48, 72, 48;
145, 120, 120, 120, 120;
330, 144, 240, 198, 240, 144;
385, 336, 336, 336, 336, 336, 336;
736, 384, 576, 384, 672, 384, 576, 384;
945, 648, 648, 864, 648, 648, 864, 648, 648;
... (End)
|
|
|
PROG
|
(Other) . (* computing T(p^e, k) ; p=prime, 1<=e, 0<=k<p^e, elementary approach *)
. (1) F := (p-1)*p^(e-1)
. (2) u := [ u(0), u(1), ..., u(p^e-1) ] vector, where
. (21) u(0) := p^e + e*F, and
. (22) FOR x := 1 TO p^e-1
. (22) u(x) := (i+1)*F, where GCD(x, p^e)= p^i
. (22) ENDFOR
. (3) T(p^e, k):= ScalarProduct( u, kTimesCyclicRightShift(u) )
(PARI)
S(p, e)={my(u=vector(p^e)); my(t=(p-1)*p^(e-1)); u[1] = p^e + e*t; for(j=1, p^e-1, u[j+1] = t*(1+valuation(j, p))); vector(#u, k, sum(j=0, #u-1, u[j + 1]*u[(j+k-1) % #u + 1]))}
T(n)={my(f=factor(n), v=vector(n, i, 1)); for(i=1, #f~, my(r=S(f[i, 1], f[i, 2])); for(j=0, #v-1, v[j + 1] *= r[j % #r + 1])); v}
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A345754
|
|
Number of 2 X 2 matrices over Z_n whose permanent equals their determinant.
|
|
+10
1
|
|
|
|
1, 16, 45, 192, 225, 720, 637, 2048, 1701, 3600, 2541, 8640, 4225, 10192, 10125, 20480, 9537, 27216, 13357, 43200, 28665, 40656, 23805, 92160, 40625, 67600, 59049, 122304, 47937, 162000, 58621, 196608, 114345, 152592, 143325, 326592, 99937, 213712, 190125
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = A344372(n) * n^2 (conjectured).
The formula is correct. Proof:
Let A = ([a, b], [c, d]) be an arbitrary 2 X 2 matrix over Z_n. So det(A) = a*d - b*c and perm(A) = a*d + b*c. Then, det(A) = perm(A) iff -b*c = b*c, i.e., 2*b*c = 0.
Suppose first that n is odd. Then 2*b*c = 0 iff b*c = 0. The number of solutions to this equation over Z_n is A018804(n). Furthermore, the value of a and b in A can be anything, so there are n possible choices for a and n possible choices for b. Thus, there are n*n*A018804(n) = n^2 * A344372(n) matrices A over Z_n such that det(A) = perm(A).
Suppose now that n is even. Then 2*b*c = 0 in Z_n iff b'*c' = 0 in Z_{n/2}, where b' and c' are b and c reduced modulo n/2. The latter equation has A018804(n/2) distinct solutions in Z_{n/2}. As the preimage of both b' and c' contains precisely 2 elements each, the number of solutions to 2*b*c = 0 in Z_n is 2*2*A018804(n/2). Hence, a(n) = n*n*4*A018804(n/2) = n^2 * A344372(n). Q.E.D.
The formula implies that the sequence is multiplicative with a(2^e) = (e+1)*8^e, a(p^e) = p^(3*e-1)*((p-1)*e+p) for odd primes p. (End)
|
|
|
MATHEMATICA
|
a[n_] := a[n] = Sum[If[Mod[Permanent[{{a, b}, {c, d}}] - Det[{{a, b}, {c, d}}], n] == 0, 1, 0], {a, 0, n - 1}, {b, 0, n - 1}, {c, 0, n - 1}, {d, 0, n - 1}] ; Array[a, 22]
f[p_, e_] := p^(3*e - 1)*((p - 1)*e + p); f[2, e_] := (e + 1)*8^e; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 50] (* Amiram Eldar, Dec 06 2022 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,mult
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
Search completed in 0.009 seconds
|
