cp's OEIS Frontend

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

%I A171503 #44 Mar 26 2021 08:43:19
%S A171503 0,3,7,15,23,39,47,71,87,111,127,167,183,231,255,287,319,383,407,479,
%T A171503 511,559,599,687,719,799,847,919,967,1079,1111,1231,1295,1375,1439,
%U A171503 1535,1583,1727,1799,1895,1959,2119,2167,2335,2415,2511,2599
%N A171503 Number of 2 X 2 integer matrices with entries from {0,1,...,n} having determinant 1.
%C A171503 Number of distinct solutions to k*x+h=0, where |h|<=n and k=1,2,...,n. - _Giovanni Resta_, Jan 08 2013.
%C A171503 Number of reduced rational numbers r/s with |r|<=n and 0<s<=n. - _Juan M. Marquez_, Apr 13 2015
%H A171503 Alois P. Heinz, <a href="/A171503/b171503.txt">Table of n, a(n) for n = 0..1000</a>
%F A171503 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
%F A171503 a(n) = 4 * A002088(n) - 1 for n >= 1. - _Robert Israel_, Jun 01 2014
%p A171503 with(numtheory):
%p A171503 a:= proc(n) option remember;
%p A171503        `if`(n<2, [0, 3][n+1], a(n-1) + 4*phi(n))
%p A171503     end:
%p A171503 seq(a(n), n=0..60);
%t A171503 a[n_]:=Count[Det/@(Partition[ #,2]&/@Tuples[Range[0,n],4]),1]
%t A171503 (* Second program: *)
%t A171503 a[0] = 0; a[1] = 3; a[n_] := a[n] = a[n-1] + 4*EulerPhi[n];
%t A171503 Table[a[n], {n, 0, 60}] (* _Jean-François Alcover_, Jun 16 2018 *)
%o A171503 (PARI) a(n)=(n>0)+2*sum(k=1, n, moebius(k)*(n\k)^2) \\ _Charles R Greathouse IV_, Apr 20 2015
%o A171503 (Python)
%o A171503 from functools import lru_cache
%o A171503 @lru_cache(maxsize=None)
%o A171503 def A171503(n): # based on second formula in A018805
%o A171503     if n == 0:
%o A171503         return 0
%o A171503     c, j = 0, 2
%o A171503     k1 = n//j
%o A171503     while k1 > 1:
%o A171503         j2 = n//k1 + 1
%o A171503         c += (j2-j)*(A171503(k1)-1)//2
%o A171503         j, k1 = j2, n//j2
%o A171503     return 2*(n*(n-1)-c+j) - 1 # _Chai Wah Wu_, Mar 25 2021
%Y A171503 Cf. A062801, A000010, A018805. Differences are A002246.
%Y A171503 See A326354 for an essentially identical sequence.
%K A171503 nonn
%O A171503 0,2
%A A171503 _Jacob A. Siehler_, Dec 10 2009
%E A171503 Edited by _Alois P. Heinz_, Jan 19 2011