Displaying 1-10 of 14 results found.
a(n) = Sum_{i=1..n, j=1..n, gcd(i,j)=1} (n+1-i)*(n+1-j).
+10
96
1, 8, 31, 80, 179, 332, 585, 948, 1463, 2136, 3065, 4216, 5729, 7568, 9797, 12456, 15737, 19520, 24087, 29308, 35315, 42120, 50073, 58920, 69025, 80264, 92871, 106756, 122475, 139528, 158681, 179608, 202529, 227400, 254597, 283784, 315957, 350576, 387977
COMMENTS
Also (1/4) * number of ways to select 3 distinct points forming a triangle of unsigned area = 1/2 from a square of grid points with side length n. Diagonal of triangle A320541. - Hugo Pfoertner, Oct 22 2018 Theorem: a(n) = n^2 + Sum_{i=2..n} (n+1-i)*(2*n+2-i)*phi(i).
Proof: Since gcd(n,n) = 1 if and only if n = 1, Sum_{i=1..n, j=1..n, gcd(i,j)=1} (n+1-i)*(n+1-j) = n^2 + Sum_{i=1..n, j=1..n, gcd(i,j)=1, (i,j) <> (1,1)} (n+1-i)*(n+1-j)
= n^2 + Sum_{i=2..n, j=1..i, gcd(i,j)=1} (n+1-i)*(n+1-j) + Sum_{j=2..n, i=1..j, gcd(i,j)=1} (n+1-i)*(n+1-j) = n^2 + 2*Sum_{i=2..n, j=1..i, gcd(i,j)=1} (n+1-i)*(n+1-j), i.e., the diagonal is not double-counted.
This is equal to n^2 + 2*Sum_{i=2..n, j is a totative of i} (n+1-i)*(n+1-j). Since Sum_{j is a totative of i} 1 = phi(i) and for i > 1, Sum_{j is a totative of i} j = i*phi(i)/2, the conclusion follows.
(End)
LINKS
N. J. A. Sloane (in collaboration with Scott R. Shannon), Art and Sequences, Slides of guest lecture in Math 640, Rutgers Univ., Feb 8, 2020. Mentions this sequence.
FORMULA
a(n) = Sum_{i=1..n, j=1..n, gcd(i,j)=1} (n+1-i)*(n+1-j).
a(n) = n^2 + Sum_{i=2..n} (n+1-i)*(2n+2-i)*phi(i). - Chai Wah Wu, Aug 15 2021
MAPLE
local a, b, r ;
r := 0 ;
for a from 1 to n do
for b from 1 to n do
if igcd(a, b) = 1 then
r := r+(n+1-a)*(n+1-b);
end if;
end do:
end do:
r ;
end proc:
MATHEMATICA
a[n_] := Sum[(n-i+1) (n-j+1) Boole[GCD[i, j] == 1], {i, n}, {j, n}];
PROG
(Python)
from math import gcd
def a115004(n):
r=0
for a in range(1, n + 1):
for b in range(1, n + 1):
if gcd(a, b)==1:
r+=(n + 1 - a)*(n + 1 - b)
return r
print([a115004(n) for n in range(1, 51)]) # Indranil Ghosh, Jul 21 2017 (Python)
from sympy import totient
def A115004(n): return n**2 + sum(totient(i)*(n+1-i)*(2*n+2-i) for i in range(2, n+1)) # Chai Wah Wu, Aug 15 2021 (PARI) a(n) = n^2 + sum(i=2, n, (n+1-i)*(2*n+2-i)*eulerphi(i)); \\ Michel Marcus, May 08 2024
Number of regions into which a figure made up of a row of n adjacent congruent rectangles is divided upon drawing diagonals of all possible rectangles (a(0)=0 by convention).
+10
51
0, 4, 16, 46, 104, 214, 380, 648, 1028, 1562, 2256, 3208, 4384, 5924, 7792, 10052, 12744, 16060, 19880, 24486, 29748, 35798, 42648, 50648, 59544, 69700, 80992, 93654, 107596, 123374, 140488, 159704, 180696, 203684, 228624, 255892, 285152, 317400, 352096, 389576
COMMENTS
Assuming that the rectangles have vertices at (k,0) and (k,1), k=0..n, the projective map (x,y) -> ((1-y)/(x+1),y/(x+1)) maps their partition to the partition of the right isosceles triangle described by Alekseyev et al. (2015), for which Theorem 13 gives the number of regions, line segments, and intersection points. - Max Alekseyev, Apr 10 2019
FORMULA
a(n) = Sum_{i=1..n, j=1..n, gcd(i,j)=1} (n+1-i)*(n+1-j) + n^2 + 2*n. - N. J. A. Sloane, Apr 11 2020 a(n) = 2n(n+1) + Sum_{i=2..n} (n+1-i)*(2n+2-i)*phi(i). - Chai Wah Wu, Aug 16 2021
MAPLE
z := proc(n)
local a, b, r ;
r := 0 ;
for a from 1 to n do
for b from 1 to n do
if igcd(a, b) = 1 then
r := r+(n+1-a)*(n+1-b);
end if;
end do:
end do:
r ;
end proc:
a := n-> z(n)+n^2+2*n;
[seq(a(n), n=1..50)];
MATHEMATICA
z[n_] := Sum[(n - i + 1)(n - j + 1) Boole[GCD[i, j] == 1], {i, n}, {j, n}];
a[0] = 0;
a[n_] := z[n] + n^2 + 2n;
PROG
(Python)
from sympy import totient
def A306302(n): return 2*n*(n+1) + sum(totient(i)*(n+1-i)*(2*n+2-i) for i in range(2, n+1)) # Chai Wah Wu, Aug 16 2021
CROSSREFS
See A331755 for the number of vertices, A331757 for the number of edges.
Number of regions in a regular drawing of the complete bipartite graph K_{n,n}.
+10
29
0, 2, 12, 40, 96, 204, 368, 634, 1012, 1544, 2236, 3186, 4360, 5898, 7764, 10022, 12712, 16026, 19844, 24448, 29708, 35756, 42604, 50602, 59496, 69650, 80940, 93600, 107540, 123316, 140428, 159642, 180632, 203618, 228556, 255822, 285080, 317326, 352020, 389498
FORMULA
a(n) = 2*(n-1)^2 + Sum_{i=2..n-1} (n-i)*(2n-i)*phi(i). - Chai Wah Wu, Aug 16 2021
MATHEMATICA
z[n_] := Sum[(n - i + 1)(n - j + 1) Boole[GCD[i, j] == 1], {i, n}, {j, n}];
a[n_] := z[n - 1] + (n - 1)^2;
PROG
(Python)
from math import gcd
def a115004(n):
r=0
for a in range(1, n + 1):
for b in range(1, n + 1):
if gcd(a, b)==1:r+=(n + 1 - a)*(n + 1 - b)
return r
def a(n): return a115004(n - 1) + (n - 1)**2
print([a(n) for n in range(1, 51)]) # Indranil Ghosh, Jul 20 2017, after Maple code (Python)
from sympy import totient
def A290131(n): return 2*(n-1)**2 + sum(totient(i)*(n-i)*(2*n-i) for i in range(2, n)) # Chai Wah Wu, Aug 16 2021
Take an n X n square grid of points in the plane; a(n) = number of ways to divide the points into two sets using a straight line.
+10
23
1, 7, 29, 87, 201, 419, 749, 1283, 2041, 3107, 4493, 6395, 8745, 11823, 15557, 20075, 25457, 32087, 39725, 48935, 59457, 71555, 85253, 101251, 119041, 139351, 161933, 187255, 215137, 246691, 280917, 319347, 361329, 407303
COMMENTS
Also, half of the number of two-dimensional threshold functions ( A114146). The line may not pass through any point. This is the "labeled" version - rotations and reflections are not taken into account (cf. A116696). The number of ways to divide a (2n) X (2n) grid into two sets of equal size is given by 2* A099957(n). - David Applegate, Feb 23 2006 All terms are odd: the line that misses the grid contributes 1 to the total and all other lines contribute 2, 4 or 8, so the total must be odd.
What can be said about the 3-D generalization? - Max Alekseyev, Feb 27 2006
FORMULA
Let V(m,n) = Sum_{i=1..m, j=1..n, gcd(i,j)=1} (m+1-i)*(n+1-j); then a(n+1) = 2*(n^2 + n + V(n,n)) + 1. - Max Alekseyev, Feb 22 2006 a(n) = 4*n^2 - 6*n + 3 + 2*Sum_{i=2..n-1} (n-i)*(2n-i)*phi(i). - Chai Wah Wu, Aug 15 2021
EXAMPLE
Examples: the two sets are indicated by X's and o's.
a(2) = 7:
XX oX Xo XX XX oo oX
XX XX XX Xo oX XX oX
--------------------
a(3) = 29:
XXX oXX ooX ooo ooX ooo
XXX XXX XXX XXX oXX oXX
XXX XXX XXX XXX XXX XXX
-1- -4- -8- -4- -4- -8- Total = 29
--------------------
a(4)= 87:
XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX
XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX
XXXX XXXX XXXX XXXX XXXX XXXo XXXo XXXo XXoo XXoo
XXXX XXXo XXoo Xooo oooo XXoo Xooo oooo Xooo oooo
--1- --4- --8- --8- --4- --4- --8- --8- --8- --8-
XXXX XXXX XXXX XXXX XXXX
XXXo XXXX XXXX XXXo XXXo
XXoo Xooo oooo Xooo XXoo
Xooo oooo oooo oooo oooo
--4- --8- --2- --4- --8- Total = 87.
--------------------
MATHEMATICA
a[n_] := 2*Sum[(n - i)*(n - j)*Boole[CoprimeQ[i, j]], {i, 1, n - 1}, {j, 1, n - 1}] + 2*n^2 - 2*n + 1; Array[a, 40] (* Jean-François Alcover, Apr 25 2016, after Max Alekseyev *)
PROG
(Python)
from sympy import totient
def A114043(n): return 4*n**2-6*n+3 + 2*sum(totient(i)*(n-i)*(2*n-i) for i in range(2, n)) # Chai Wah Wu, Aug 15 2021
Total number of line segments between points visible to each other in a square n X n lattice.
+10
23
0, 6, 28, 86, 200, 418, 748, 1282, 2040, 3106, 4492, 6394, 8744, 11822, 15556, 20074, 25456, 32086, 39724, 48934, 59456, 71554, 85252, 101250, 119040, 139350, 161932, 187254, 215136, 246690, 280916, 319346, 361328, 407302, 457180, 511714, 570232
COMMENTS
A line segment joins points (a,b) and (c,d) if the points are distinct and gcd(c-a,d-b)=1.
REFERENCES
D. M. Acketa, J. D. Zunic: On the number of linear partitions of the (m,n)-grid. Inform. Process. Lett., 38 (3) (1991), 163-168. See Table A.1.
Jovisa Zunic, Note on the number of two-dimensional threshold functions, SIAM J. Discrete Math. Vol. 25 (2011), No. 3, pp. 1266-1268. See Eq. (1.2).
FORMULA
a(n) = 2*(n-1)*(2n-1) + 2*Sum_{i=2..n-1} (n-i)*(2n-i)*phi(i). - Chai Wah Wu, Aug 16 2021
EXAMPLE
The 2 x 2 square lattice has a total of 6 line segments: 2 vertical, 2 horizontal and 2 diagonal.
MATHEMATICA
Table[cnt=0; Do[If[GCD[c-a, d-b]<2, cnt++ ], {a, n}, {b, n}, {c, n}, {d, n}]; (cnt-n^2)/2, {n, 20}]
(* This recursive code is much more efficient. *)
a[n_]:=a[n]=If[n<=1, 0, 2*a1[n]-a[n-1]+R1[n]]
a1[n_]:=a1[n]=If[n<=1, 0, 2*a[n-1]-a1[n-1]+R2[n]]
R1[n_]:=R1[n]=If[n<=1, 0, R1[n-1]+4*EulerPhi[n-1]]
R2[n_]:=(n-1)*EulerPhi[n-1]
Table[a[n], {n, 1, 37}]
a[n_]:=2 Sum[(n-i) (n-j) Boole[CoprimeQ[i, j]], {i, 1, n-1}, {j, 1, n-1}] + 2 n^2 - 2 n; Array[a, 40] (* Vincenzo Librandi, Feb 05 2020 *)
PROG
(Python)
from sympy import totient
def A141255(n): return 2*(n-1)*(2*n-1) + 2*sum(totient(i)*(n-i)*(2*n-i) for i in range(2, n)) # Chai Wah Wu, Aug 16 2021
Number of triangles in an n X n unit grid that have minimal possible area (of 1/2).
+10
12
0, 4, 32, 124, 320, 716, 1328, 2340, 3792, 5852, 8544, 12260, 16864, 22916, 30272, 39188, 49824, 62948, 78080, 96348, 117232, 141260, 168480, 200292, 235680, 276100, 321056, 371484, 427024, 489900, 558112, 634724, 718432, 810116, 909600, 1018388, 1135136, 1263828, 1402304, 1551908
FORMULA
a(n) = 4*(n-1)^2 + 4*Sum_{i=2..n-1} (n-i)*(2n-i)*phi(i). - Chai Wah Wu, Aug 15 2021
EXAMPLE
a(2)=4 because 4 (isosceles right) triangles with area 1/2 can be placed on a 2 X 2 grid.
MATHEMATICA
z[n_] := Sum[(n - i + 1)(n - j + 1) Boole[GCD[i, j] == 1], {i, n}, {j, n}];
a[n_] := 4 z[n - 1];
PROG
(Python)
from sympy import totient
def A088658(n): return 4*(n-1)**2 + 4*sum(totient(i)*(n-i)*(2*n-i) for i in range(2, n)) # Chai Wah Wu, Aug 15 2021
AUTHOR
Yuval Dekel (dekelyuval(AT)hotmail.com), Nov 21 2003
Number of threshold functions on n X n grid.
+10
12
1, 2, 14, 58, 174, 402, 838, 1498, 2566, 4082, 6214, 8986, 12790, 17490, 23646, 31114, 40150, 50914, 64174, 79450, 97870, 118914, 143110, 170506, 202502, 238082, 278702, 323866, 374510, 430274, 493382, 561834, 638694, 722658, 814606, 914362, 1023430, 1140466
COMMENTS
Also, number of intersections of a halfspace with an n X n grid. While A114043 counts cuts, this sequence counts sides of cuts. The only difference between this and twice A114043 is that this makes sense for the empty grid. This is the "labeled" version - rotations and reflections are not taken into account. - David Applegate, Feb 24 2006 In the terminology of Koplowitz et al., this is the number of linear dichotomies on a square grid. - N. J. A. Sloane, Mar 14 2020
FORMULA
For n>0, a(n) = 8*n^2 - 12*n + 6 + 4*Sum_{i=2..n-1} (n-i)*(2n-i)*phi(i). - Chai Wah Wu, Aug 15 2021
MATHEMATICA
a[0] = 1; a[n_] := 4 Sum[(n-i)(n-j) Boole[CoprimeQ[i, j]], {i, 1, n-1}, {j, 1, n-1}] + 4 n^2 - 4 n + 2;
PROG
(Python)
from sympy import totient
def A114146(n): return 1 if n == 0 else 8*n**2-12*n+6 + 4*sum(totient(i)*(n-i)*(2*n-i) for i in range(2, n)) # Chai Wah Wu, Aug 15 2021
Array read by antidiagonals: T(m,n) = Sum_{i=1..m, j=1..n, gcd(i,j)=1} (m+1-i)*(n+1-j), m>=1, n>=1.
+10
11
1, 3, 3, 6, 8, 6, 10, 16, 16, 10, 15, 26, 31, 26, 15, 21, 39, 50, 50, 39, 21, 28, 54, 75, 80, 75, 54, 28, 36, 72, 103, 120, 120, 103, 72, 36, 45, 92, 137, 164, 179, 164, 137, 92, 45, 55, 115, 175, 218, 244, 244, 218, 175, 115, 55, 66, 140, 218, 278, 324, 332, 324, 278, 218, 140
COMMENTS
The corresponding triangle is A320541, counting (1/4) * number of ways to select 3 distinct points forming a triangle of unsigned area = 1/2 from a rectangle of grid points with side lengths j and k, written as triangle T(j,k), j<=k. - Hugo Pfoertner, Oct 22 2018
EXAMPLE
The top left corner of the array is:
[1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78]
[3, 8, 16, 26, 39, 54, 72, 92, 115, 140, 168, 198]
[6, 16, 31, 50, 75, 103, 137, 175, 218, 265, 318, 374]
[10, 26, 50, 80, 120, 164, 218, 278, 346, 420, 504, 592]
[15, 39, 75, 120, 179, 244, 324, 413, 514, 623, 747, 877]
[21, 54, 103, 164, 244, 332, 441, 562, 699, 846, 1014, 1190]
[28, 72, 137, 218, 324, 441, 585, 745, 926, 1120, 1342, 1575]
[36, 92, 175, 278, 413, 562, 745, 948, 1178, 1424, 1706, 2002]
[45, 115, 218, 346, 514, 699, 926, 1178, 1463, 1768, 2118, 2485]
[55, 140, 265, 420, 623, 846, 1120, 1424, 1768, 2136, 2559, 3002]
[66, 168, 318, 504, 747, 1014, 1342, 1706, 2118, 2559, 3065, 3595]
[78, 198, 374, 592, 877, 1190, 1575, 2002, 2485, 3002, 3595, 4216]
...
MAPLE
T:=proc(m, n) local t1, i, j; t1:=0; for i from 1 to m do for j from 1 to n do if gcd(i, j)=1 then t1:=t1+(m+1-i)*(n+1-j); fi; od; od; t1; end;
MATHEMATICA
T[m_, n_] := Module[{t1, i, j}, t1 = 0; For[i = 1, i <= m, i++, For[j = 1, j <= n, j++, If[GCD[i, j] == 1 , t1 = t1 + (m+1-i)*(n+1-j)]]]; t1]; Table[T[m-n+1, n], {m, 1, 11}, {n, 1, m}] // Flatten (* Jean-François Alcover, Jan 07 2014, translated from Maple *)
Number of quadrilateral regions into which a figure made up of a row of n adjacent congruent rectangles is divided upon drawing diagonals of all possible rectangles.
+10
11
0, 2, 14, 34, 90, 154, 288, 462, 742, 1038, 1512, 2074, 2904, 3774, 4892, 6154, 7864, 9662, 12022, 14638, 17786, 20998, 25024, 29402, 34672, 40038, 46310, 53038, 61090, 69454, 79344, 89890, 101792, 113854, 127476, 141866, 158428, 175182, 193760, 213274, 235444, 258182, 283858, 310750, 339986
COMMENTS
A row of n adjacent congruent rectangles can only be divided into triangles (cf. A324042) or quadrilaterals when drawing diagonals. Proof is given in Alekseyev et al. (2015) under the transformation described in A306302.
FORMULA
a(n) = A115005(n+1) - A177719(n+1) - n - 1 = Sum_{i,j=1..n; gcd(i,j)=1} (n+1-i)*(n+1-j) - 2*Sum_{i,j=1..n; gcd(i,j)=2} (n+1-i)*(n+1-j) - n^2. - Max Alekseyev, Jul 08 2019 For n>1, a(n) = -2(n-1)^2 + Sum_{i=2..floor(n/2)} (n+1-i)*(7i-2n-2)*phi(i) + Sum_{i=floor(n/2)+1..n} (n+1-i)*(2n+2-i)*phi(i). - Chai Wah Wu, Aug 16 2021
EXAMPLE
For k adjacent congruent rectangles, the number of quadrilateral regions in the j-th rectangle is:
k\j| 1 2 3 4 5 6 7 ...
---+--------------------------------
1 | 0, 0, 0, 0, 0, 0, 0, ...
2 | 1, 1, 0, 0, 0, 0, 0, ...
3 | 3, 8, 3, 0, 0, 0, 0, ...
4 | 5, 12, 12, 5, 0, 0, 0, ...
5 | 7, 22, 32, 22, 7, 0, 0, ...
6 | 9, 28, 40, 40, 28, 9, 0, ...
7 | 11, 38, 58, 74, 58, 38, 11, ...
...
a(4) = 5 + 12 + 12 + 5 = 34.
MATHEMATICA
Table[Sum[Sum[(Boole[GCD[i, j] == 1] - 2 * Boole[GCD[i, j] == 2]) * (n + 1 - i) * (n + 1 - j), {j, 1, n}], {i, 1, n}] - n^2, {n, 1, 45}] (* Joshua Oliver, Feb 05 2020 *)
PROG
(PARI) { A324043(n) = sum(i=1, n, sum(j=1, n, ( (gcd(i, j)==1) - 2*(gcd(i, j)==2) ) * (n+1-i) * (n+1-j) )) - n^2; } \\ Max Alekseyev, Jul 08 2019 (Python)
from sympy import totient
def A324043(n): return 0 if n==1 else -2*(n-1)**2 + sum(totient(i)*(n+1-i)*(7*i-2*n-2) for i in range(2, n//2+1)) + sum(totient(i)*(n+1-i)*(2*n+2-i) for i in range(n//2+1, n+1)) # Chai Wah Wu, Aug 16 2021
Array read by antidiagonals: let V(m,n) = Sum_{i=1..m, j=1..n, gcd(i,j)=1} (m+1-i)*(n+1-j), then T(m,n) = 2*m*n+m+n+2*V(m,n), for m >= 0, n >= 0.
+10
4
0, 1, 1, 2, 6, 2, 3, 13, 13, 3, 4, 22, 28, 22, 4, 5, 33, 49, 49, 33, 5, 6, 46, 74, 86, 74, 46, 6, 7, 61, 105, 131, 131, 105, 61, 7, 8, 78, 140, 188, 200, 188, 140, 78, 8, 9, 97, 181, 251, 289, 289, 251, 181, 97, 9, 10, 118, 226, 326, 386, 418, 386, 326, 226, 118, 10, 11, 141, 277
COMMENTS
This is the number of linear partitions of an m X n grid.
REFERENCES
D. M. Acketa, J. D. Zunic: On the number of linear partitions of the (m,n)-grid. Inform. Process. Lett., 38 (3) (1991), 163-168. See Table A.1.
Jovisa Zunic, Note on the number of two-dimensional threshold functions, SIAM J. Discrete Math. Vol. 25 (2011), No. 3, pp. 1266-1268. See Equation (1.2).
EXAMPLE
The array begins:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
1, 6, 13, 22, 33, 46, 61, 78, 97, 118, ...
2, 13, 28, 49, 74, 105, 140, 181, 226, 277, ...
3, 22, 49, 86, 131, 188, 251, 326, 409, 502, ...
4, 33, 74, 131, 200, 289, 386, 503, 632, 777, ...
5, 46, 105, 188, 289, 418, 559, 730, 919, 1132, ...
6, 61, 140, 251, 386, 559, 748, 979, 1234, 1521, ...
7, 78, 181, 326, 503, 730, 979, 1282, 1617, 1994, ...
...
MAPLE
V:=proc(m, n) local t1, i, j; t1:=0; for i from 1 to m do for j from 1 to n do if gcd(i, j)=1 then t1:=t1+(m+1-i)*(n+1-j); fi; od; od; t1; end; T:=(m, n)->(2*m*n+m+n+2*V(m, n));
MATHEMATICA
V[m_, n_] := Sum[If[GCD[i, j] == 1, (m-i+1)*(n-j+1), 0], {i, 1, m}, {j, 1, n}]; T[m_, n_] := 2*m*n+m+n+2*V[m, n]; Table[T[m-n, n], {m, 0, 11}, {n, 0, m}] // Flatten (* Jean-François Alcover, Jan 08 2014 *)
Search completed in 0.016 seconds
| 
