OFFSET
0,2
COMMENTS
Number of distinct solutions to k*x+h=0, where |h|<=n and k=1,2,...,n. - Giovanni Resta, Jan 08 2013.
Number of reduced rational numbers r/s with |r|<=n and 0<s<=n. - Juan M. Marquez, Apr 13 2015
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000
FORMULA
Recursion: a(n) = a(n - 1) + 4*phi(n) for n > 1, with phi being Euler's totient function. - Juan M. Marquez, Jan 19 2010
a(n) = 4 * A002088(n) - 1 for n >= 1. - Robert Israel, Jun 01 2014
MAPLE
with(numtheory):
a:= proc(n) option remember;
`if`(n<2, [0, 3][n+1], a(n-1) + 4*phi(n))
end:
seq(a(n), n=0..60);
MATHEMATICA
a[n_]:=Count[Det/@(Partition[ #, 2]&/@Tuples[Range[0, n], 4]), 1]
(* Second program: *)
a[0] = 0; a[1] = 3; a[n_] := a[n] = a[n-1] + 4*EulerPhi[n];
Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Jun 16 2018 *)
PROG
(PARI) a(n)=(n>0)+2*sum(k=1, n, moebius(k)*(n\k)^2) \\ Charles R Greathouse IV, Apr 20 2015
(Python)
from functools import lru_cache
@lru_cache(maxsize=None)
if n == 0:
return 0
c, j = 0, 2
k1 = n//j
while k1 > 1:
j2 = n//k1 + 1
c += (j2-j)*(A171503(k1)-1)//2
j, k1 = j2, n//j2
return 2*(n*(n-1)-c+j) - 1 # Chai Wah Wu, Mar 25 2021
CROSSREFS
KEYWORD
nonn
AUTHOR
Jacob A. Siehler, Dec 10 2009
EXTENSIONS
Edited by Alois P. Heinz, Jan 19 2011
STATUS
approved