login
A090030
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.
12
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, 91, 225, 211, 63, 0, 0, 1, 25, 175, 529, 961, 665, 127, 0, 0, 1, 37, 253, 1185, 2851, 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
OFFSET
0,9
COMMENTS
Equivalently, number of lattice points where the GCD of all coordinates = 1.
FORMULA
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)
T(n,k) = Sum_{i=1..n-k} moebius(i)*((floor((n-k)/i)+1)^k-1). - Vladeta Jovovic, Dec 03 2004
EXAMPLE
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.
Triangle T(n,k) begins:
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, 91, 225, 211, 63, 0;
0, 1, 25, 175, 529, 961, 665, 127, 0;
0, 1, 37, 253, 1185, 2851, 3969, 2059, 255, 0;
0, 1, 45, 415, 2065, 7471, 14833, 16129, 6305, 511, 0;
...
MATHEMATICA
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]
CROSSREFS
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.
T(n,n) gives A081474.
Cf. A008683.
Sequence in context: A325735 A235794 A349911 * A293616 A211649 A202023
KEYWORD
nonn,tabl
AUTHOR
Joshua Zucker, Nov 24 2003
STATUS
approved