A090028 - OEIS

%I #16 Mar 31 2021 09:45:29

%S 0,63,665,3969,14833,45801,112825,257257,515025,980217,1720145,

%T 2934505,4693473,7396137,11112129,16464385,23555441,33430033,45927505,

%U 62881561,83865257,111331241,144772201,187839225,238778281,303522401,379323785

%N Number of distinct lines through the origin in 6-dimensional cube of side length n.

%C Equivalently, lattice points where the GCD of all coordinates = 1.

%F a(n) = A090030(6, n).

%F a(n) = (n+1)^6 - 1 - Sum_{j=2..n+1} a(floor(n/j)). - _Chai Wah Wu_, Mar 30 2021

%e a(2) = 665 because the 665 points with at least one coordinate=2 all make distinct lines and the remaining 63 points and the origin are on those lines.

%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;Table[lines[6, k], {k, 0, 40}]

%o (Python)

%o from functools import lru_cache

%o @lru_cache(maxsize=None)

%o def A090028(n):

%o     if n == 0:

%o         return 0

%o     c, j = 1, 2

%o     k1 = n//j

%o     while k1 > 1:

%o         j2 = n//k1 + 1

%o         c += (j2-j)*A090028(k1)

%o         j, k1 = j2, n//j2

%o     return (n+1)**6-c+63*(j-n-1) # _Chai Wah Wu_, Mar 30 2021

%Y Cf. A000225, A001047, A060867, A090020, A090021, A090022, A090023, A090024 are for n dimensions with side length 1, 2, 3, 4, 5, 6, 7, 8, respectively. A049691, A090025, A090026, A090027, A090028, A090029 are this sequence for 2, 3, 4, 5, 6, 7 dimensions. A090030 is the table for n dimensions, side length k.

%K nonn

%O 0,2

%A _Joshua Zucker_, Nov 25 2003