A090025 Number of distinct lines through the origin in 3-dimensional cube of side length n.

0, 7, 19, 49, 91, 175, 253, 415, 571, 805, 1033, 1423, 1723, 2263, 2713, 3313, 3913, 4825, 5491, 6625, 7513, 8701, 9811, 11461, 12637, 14497, 16045, 18043, 19807, 22411, 24163, 27133, 29485, 32425, 35065, 38593, 41221, 45433, 48727, 52831

Offset: 0

Author

Joshua Zucker, Nov 25 2003

Keywords

• nonn

Comments

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

Examples

			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.
		

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.

Programs

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 *)

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

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