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

0, 1, 5, 49, 529, 7471, 112825, 2078455, 42649281, 997784221, 25875851825, 742641202183, 23283999690561, 793616663524231, 29188521870580929, 1152885848976064513, 48659336030073207425, 2185894865613157551481, 104126348669497256201905, 5242869988601103651841105

Offset

0,3

Comments

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

Links

Alois P. Heinz, Table of n, a(n) for n = 0..386

Formula

a(n) = A090030(n,n).

Example

a(3) = 49 because in the 3-dimensional lattice of side length 3, the lines through the origin are determined by all 37 points with at least one coordinate = 3 and 6 permutations of (2,1,0) and 3 permutations each of (2,1,1) and (2,2,1).

Maple

a:= n-> add(numtheory[mobius](i)*((floor(n/i)+1)^n-1), i=1..n):
seq(a(n), n=0..20);  # Alois P. Heinz, Mar 09 2022

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[k, k], {k, 0, 20}]

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: A146311 A212818 A195206 * A378402 A370097 A274671

Adjacent sequences: A081471 A081472 A081473 * A081475 A081476 A081477

Keyword

nonn

Author

Joshua Zucker, Nov 25 2003

Status

approved