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.
KEYWORD
nonn,tabl
AUTHOR
Joshua Zucker, Nov 24 2003
STATUS
approved