login
A090026
Number of distinct lines through the origin in 4-dimensional cube of side length n.
12
0, 15, 65, 225, 529, 1185, 2065, 3745, 5841, 9105, 13025, 19105, 25521, 35361, 45825, 59905, 75425, 96865, 117841, 147505, 177041, 214961, 254401, 306321, 355249, 420929, 485489, 565265, 645377, 748081, 841841, 966881, 1086241, 1230401, 1373185, 1549825
OFFSET
0,2
COMMENTS
Equivalently, number of lattice points where the GCD of all coordinates = 1.
FORMULA
a(n) = A090030(4, n).
a(n) = (n+1)^4 - 1 - Sum_{j=2..n+1} a(floor(n/j)). - Chai Wah Wu, Mar 30 2021
EXAMPLE
a(2) = 65 because the 65 points with at least one coordinate=2 all make distinct lines and the remaining 15 points and the origin are on those lines.
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; Table[lines[4, k], {k, 0, 40}]
PROG
(Python)
from functools import lru_cache
@lru_cache(maxsize=None)
def A090026(n):
if n == 0:
return 0
c, j = 1, 2
k1 = n//j
while k1 > 1:
j2 = n//k1 + 1
c += (j2-j)*A090026(k1)
j, k1 = j2, n//j2
return (n+1)**4-c+15*(j-n-1) # Chai Wah Wu, Mar 30 2021
CROSSREFS
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.
Sequence in context: A027455 A152729 A055268 * A027526 A334802 A284898
KEYWORD
nonn
AUTHOR
Joshua Zucker, Nov 25 2003
STATUS
approved