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