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

Author

Jacob A. Siehler, Dec 10 2009

Keywords

• nonn

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 0Juan M. Marquez, Apr 13 2015

Links

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

Crossrefs

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

See A326354 for an essentially identical sequence.

Programs

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

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

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

Extensions

Edited by Alois P. Heinz, Jan 19 2011