A171503 Number of 2 X 2 integer matrices with entries from {0,1,...,n} having determinant 1.

0, 3, 7, 15, 23, 39, 47, 71, 87, 111, 127, 167, 183, 231, 255, 287, 319, 383, 407, 479, 511, 559, 599, 687, 719, 799, 847, 919, 967, 1079, 1111, 1231, 1295, 1375, 1439, 1535, 1583, 1727, 1799, 1895, 1959, 2119, 2167, 2335, 2415, 2511, 2599

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)
def A171503(n): # based on second formula in A018805
    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

Cf. A062801, A000010, A018805. Differences are A002246.

See A326354 for an essentially identical sequence.

Sequence in context: A181106 A131753 A330319 * A326354 A283008 A283259

Adjacent sequences: A171500 A171501 A171502 * A171504 A171505 A171506

Keyword

nonn

Author

Jacob A. Siehler, Dec 10 2009

Extensions

Edited by Alois P. Heinz, Jan 19 2011

Status

approved