|
%I #13 Mar 09 2022 08:26:16
%S 0,0,0,0,1,0,0,1,3,0,0,1,5,7,0,0,1,9,19,15,0,0,1,13,49,65,31,0,0,1,21,
%T 91,225,211,63,0,0,1,25,175,529,961,665,127,0,0,1,37,253,1185,2851,
%U 3969,2059,255,0,0,1,45,415,2065,7471,14833,16129,6305,511,0,0,1,57,571,3745,15541,45801,75811,65025,19171,1023,0
%N Triangle read by rows: T(n,k) = number of distinct lines through the origin in the n-dimensional cubic lattice of side length k with one corner at the origin.
%C Equivalently, number of lattice points where the GCD of all coordinates = 1.
%F With A(n, k) = A090225(n, k), T(n, k) =(k+1)^n - 1 - the sum for 0 < i < k of Floor[k/i-1]*A(n, i)
%F T(n,k) = Sum_{i=1..n-k} moebius(i)*((floor((n-k)/i)+1)^k-1). - _Vladeta Jovovic_, Dec 03 2004
%e T(n,1) = 2^n-1 because there are 2^n-1 lattice points other than the corner, all of which make distinct lines. T(n,2) = 3^n - 2^n because if the given corner is the origin, all the points with coordinates in {0,1} make lines that are redundant with a point containing a coordinate 2.
%e Triangle T(n,k) begins:
%e 0;
%e 0, 0;
%e 0, 1, 0;
%e 0, 1, 3, 0;
%e 0, 1, 5, 7, 0;
%e 0, 1, 9, 19, 15, 0;
%e 0, 1, 13, 49, 65, 31, 0;
%e 0, 1, 21, 91, 225, 211, 63, 0;
%e 0, 1, 25, 175, 529, 961, 665, 127, 0;
%e 0, 1, 37, 253, 1185, 2851, 3969, 2059, 255, 0;
%e 0, 1, 45, 415, 2065, 7471, 14833, 16129, 6305, 511, 0;
%e ...
%t aux[n_, k_] := If[k==0, 0, (k+1)^n-k^n-Sum[aux[n, Divisors[k][[i]]], {i, 1, Length[Divisors[k]]-1}]];lines[n_, k_] := (k+1)^n-Sum[Floor[k/i-1]*aux[n, i], {i, 1, Floor[k/2]}]-1;lines[n, k]
%Y Cf. A000225, A001047, A060867, A090020, A090021, A090022, A090023, A090024 give T(n, k) for k = 1, 2, 3, 4, 5, 6, 7, 8, respectively. A049691, A090025, A090026, A090027, A090028, A090029 give T(n, k) for n=2, 3, 4, 5, 6, 7 respectively. A090225 counts only points with at least one coordinate = k.
%Y T(n,n) gives A081474.
%Y Cf. A008683.
%K nonn,tabl
%O 0,9
%A _Joshua Zucker_, Nov 24 2003
|
