cp's OEIS Frontend

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

%I A090025 #26 Mar 30 2021 18:44:17
%S A090025 0,7,19,49,91,175,253,415,571,805,1033,1423,1723,2263,2713,3313,3913,
%T A090025 4825,5491,6625,7513,8701,9811,11461,12637,14497,16045,18043,19807,
%U A090025 22411,24163,27133,29485,32425,35065,38593,41221,45433,48727,52831
%N A090025 Number of distinct lines through the origin in 3-dimensional cube of side length n.
%C A090025 Equivalently, lattice points where the GCD of all coordinates = 1.
%F A090025 a(n) = A090030(3, n).
%F A090025 a(n) = Sum_{k=1..n} moebius(k)*((floor(n/k)+1)^3-1). - _Vladeta Jovovic_, Dec 03 2004
%F A090025 a(n) = (n+1)^3 - Sum_{j=2..n+1} a(floor(n/j)). - _Seth A. Troisi_, Aug 29 2013
%F A090025 a(n) = 6*A015631(n) + 1 for n>=1. - _Hugo Pfoertner_, Mar 30 2021
%e A090025 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.
%t A090025 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}]
%t A090025 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_ *)
%o A090025 (PARI) a(n)=(n+1)^3-sum(j=2,n+1,a(floor(n/j)))
%o A090025 (Python)
%o A090025 from functools import lru_cache
%o A090025 @lru_cache(maxsize=None)
%o A090025 def A090025(n):
%o A090025     if n == 0:
%o A090025         return 0
%o A090025     c, j = 1, 2
%o A090025     k1 = n//j
%o A090025     while k1 > 1:
%o A090025         j2 = n//k1 + 1
%o A090025         c += (j2-j)*A090025(k1)
%o A090025         j, k1 = j2, n//j2
%o A090025     return (n+1)**3-c+7*(j-n-1) # _Chai Wah Wu_, Mar 30 2021
%Y A090025 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.
%Y A090025 Cf. A071778.
%K A090025 nonn
%O A090025 0,2
%A A090025 _Joshua Zucker_, Nov 25 2003