OFFSET
0,2
COMMENTS
Equivalently, lattice points where the GCD of all coordinates = 1.
FORMULA
a(n) = A090030(3, n).
a(n) = Sum_{k=1..n} moebius(k)*((floor(n/k)+1)^3-1). - Vladeta Jovovic, Dec 03 2004
a(n) = (n+1)^3 - Sum_{j=2..n+1} a(floor(n/j)). - Seth A. Troisi, Aug 29 2013
a(n) = 6*A015631(n) + 1 for n>=1. - Hugo Pfoertner, Mar 30 2021
EXAMPLE
a(2) = 19 because the 19 points with at least one coordinate=2 all make distinct lines and the remaining 7 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[3, k], {k, 0, 40}]
a[n_] := Sum[MoebiusMu[k]*((Floor[n/k]+1)^3-1), {k, 1, n}]; Table[a[n], {n, 0, 39}] (* Jean-François Alcover, Nov 28 2013, after Vladeta Jovovic *)
PROG
(PARI) a(n)=(n+1)^3-sum(j=2, n+1, a(floor(n/j)))
(Python)
from functools import lru_cache
@lru_cache(maxsize=None)
def A090025(n):
if n == 0:
return 0
c, j = 1, 2
k1 = n//j
while k1 > 1:
j2 = n//k1 + 1
c += (j2-j)*A090025(k1)
j, k1 = j2, n//j2
return (n+1)**3-c+7*(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.
Cf. A071778.
KEYWORD
nonn
AUTHOR
Joshua Zucker, Nov 25 2003
STATUS
approved