A090030 - OEIS

%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