A171503 -id:A171503 - cp's OEIS frontend

A210000 Number of unimodular 2 X 2 matrices having all terms in {0,1,...,n}.

0, 6, 14, 30, 46, 78, 94, 142, 174, 222, 254, 334, 366, 462, 510, 574, 638, 766, 814, 958, 1022, 1118, 1198, 1374, 1438, 1598, 1694, 1838, 1934, 2158, 2222, 2462, 2590, 2750, 2878, 3070, 3166, 3454, 3598, 3790, 3918, 4238, 4334, 4670, 4830

Offset: 0

Clark Kimberling, Mar 16 2012

nonn

a(n) is the number of 2 X 2 matrices having all terms in {0,1,...,n} and inverses with all terms integers.
Most sequences in the following guide count 2 X 2 matrices having all terms contained in the domain shown in column 2 and determinant d or permanent p or sum s of terms as indicated in column 3.
A059306 ... {0,1,...,n} ..... d=0
A171503 ... {0,1,...,n} ..... d=1
A210000 ... {0,1,...,n} .... |d|=1
A209973 ... {0,1,...,n} ..... d=2
A209975 ... {0,1,...,n} ..... d=3
A209976 ... {0,1,...,n} ..... d=4
A209977 ... {0,1,...,n} ..... d=5
A210282 ... {0,1,...,n} ..... d=n
A210283 ... {0,1,...,n} ..... d=n-1
A210284 ... {0,1,...,n} ..... d=n+1
A210285 ... {0,1,...,n} ..... d=floor(n/2)
A210286 ... {0,1,...,n} ..... d=trace
A280588 ... {0,1,...,n} ..... d=s
A106634 ... {0,1,...,n} ..... p=n
A210288 ... {0,1,...,n} ..... p=trace
A210289 ... {0,1,...,n} ..... p=(trace)^2
A280934 ... {0,1,...,n} ..... p=s
A210290 ... {0,1,...,n} ..... d>=0
A183761 ... {0,1,...,n} ..... d>0
A210291 ... {0,1,...,n} ..... d>n
A210366 ... {0,1,...,n} ..... d>=n
A210367 ... {0,1,...,n} ..... d>=2n
A210368 ... {0,1,...,n} ..... d>=3n
A210369 ... {0,1,...,n} ..... d is even
A210370 ... {0,1,...,n} ..... d is odd
A210371 ... {0,1,...,n} ..... d is even and >=0
A210372 ... {0,1,...,n} ..... d is even and >0
A210373 ... {0,1,...,n} ..... d is odd and >0
A210374 ... {0,1,...,n} ..... s=n+2
A210375 ... {0,1,...,n} ..... s=n+3
A210376 ... {0,1,...,n} ..... s=n+4
A210377 ... {0,1,...,n} ..... s=n+5
A210378 ... {0,1,...,n} ..... t is even
A210379 ... {0,1,...,n} ..... t is odd
A211031 ... {0,1,...,n} ..... d is in [-n,n]
A211032 ... {0,1,...,n} ..... d is in (-n,n)
A211033 ... {0,1,...,n} ..... d=0 (mod 3)
A211034 ... {0,1,...,n} ..... d=1 (mod 3)
A209974 = (A209973)/4
A134506 ... {1,2,...,n} ..... d=0
A196227 ... {1,2,...,n} ..... d=1
A209979 ... {1,2,...,n} .... |d|=1
A197168 ... {1,2,...,n} ..... d=2
A210001 ... {1,2,...,n} ..... d=3
A210002 ... {1,2,...,n} ..... d=4
A210027 ... {1,2,...,n} ..... d=5
A209978 = (A196227)/2
A209980 = (A197168)/2
A211053 ... {1,2,...,n} ..... d=n
A211054 ... {1,2,...,n} ..... d=n-1
A211055 ... {1,2,...,n} ..... d=n+1
A055507 ... {1,2,...,n} ..... p=n
A211057 ... {1,2,...,n} ..... d is in [0,n]
A211058 ... {1,2,...,n} ..... d>=0
A211059 ... {1,2,...,n} ..... d>0
A211060 ... {1,2,...,n} ..... d>n
A211061 ... {1,2,...,n} ..... d>=n
A211062 ... {1,2,...,n} ..... d>=2n
A211063 ... {1,2,...,n} ..... d>=3n
A211064 ... {1,2,...,n} ..... d is even
A211065 ... {1,2,...,n} ..... d is odd
A211066 ... {1,2,...,n} ..... d is even and >=0
A211067 ... {1,2,...,n} ..... d is even and >0
A211068 ... {1,2,...,n} ..... d is odd and >0
A209981 ... {-n,....,n} ..... d=0
A209982 ... {-n,....,n} ..... d=1
A209984 ... {-n,....,n} ..... d=2
A209986 ... {-n,....,n} ..... d=3
A209988 ... {-n,....,n} ..... d=4
A209990 ... {-n,....,n} ..... d=5
A211140 ... {-n,....,n} ..... d=n
A211141 ... {-n,....,n} ..... d=n-1
A211142 ... {-n,....,n} ..... d=n+1
A211143 ... {-n,....,n} ..... d=n^2
A211140 ... {-n,....,n} ..... p=n
A211145 ... {-n,....,n} ..... p=trace
A211146 ... {-n,....,n} ..... d in [0,n]
A211147 ... {-n,....,n} ..... d>=0
A211148 ... {-n,....,n} ..... d>0
A211149 ... {-n,....,n} ..... d<0 or d>0
A211150 ... {-n,....,n} ..... d>n
A211151 ... {-n,....,n} ..... d>=n
A211152 ... {-n,....,n} ..... d>=2n
A211153 ... {-n,....,n} ..... d>=3n
A211154 ... {-n,....,n} ..... d is even
A211155 ... {-n,....,n} ..... d is odd
A211156 ... {-n,....,n} ..... d is even and >=0
A211157 ... {-n,....,n} ..... d is even and >0
A211158 ... {-n,....,n} ..... d is odd and >0

			a(2)=6 counts these matrices (using reduced matrix notation):
(1,0,0,1), determinant = 1, inverse = (1,0,0,1)
(1,0,1,1), determinant = 1, inverse = (1,0,-1,1)
(1,1,0,1), determinant = 1, inverse = (1,-1,0,1)
(0,1,1,0), determinant = -1, inverse = (0,1,1,0)
(0,1,1,1), determinant = -1, inverse = (-1,1,1,0)
(1,1,1,0), determinant = -1, inverse = (0,1,1,-1)

Cf. A171503.

See also the very useful list of cross-references in the Comments section.

a = 0; b = n; z1 = 50;
t[n_] := t[n] = Flatten[Table[w*z - x*y, {w, a, b}, {x, a, b}, {y, a, b}, {z, a, b}]]
c[n_, k_] := c[n, k] = Count[t[n], k]
Table[c[n, 0], {n, 0, z1}]  (* A059306 *)
Table[c[n, 1], {n, 0, z1}]  (* A171503 *)
2 %                         (* A210000 *)
Table[c[n, 2], {n, 0, z1}]  (* A209973 *)
%/4                         (* A209974 *)
Table[c[n, 3], {n, 0, z1}]  (* A209975 *)
Table[c[n, 4], {n, 0, z1}]  (* A209976 *)
Table[c[n, 5], {n, 0, z1}]  (* A209977 *)

a(n) = 2*A171503(n).

A209982 added to list in comment by Chai Wah Wu, Nov 27 2016

A018805 Number of elements in the set {(x,y): 1 <= x,y <= n, gcd(x,y)=1}.

Original entry on oeis.org

1, 3, 7, 11, 19, 23, 35, 43, 55, 63, 83, 91, 115, 127, 143, 159, 191, 203, 239, 255, 279, 299, 343, 359, 399, 423, 459, 483, 539, 555, 615, 647, 687, 719, 767, 791, 863, 899, 947, 979, 1059, 1083, 1167, 1207, 1255, 1299, 1391, 1423, 1507, 1547, 1611, 1659, 1763

Offset: 1

David W. Wilson

Number of positive rational numbers of height at most n, where the height of p/q is max(p, q) when p and q are relatively prime positive integers. - Charles R Greathouse IV, Jul 05 2012
The number of ordered pairs (i,j) with 1<=i<=n, 1<=j<=n, gcd(i,j)=d is a(floor(n/d)). - N. J. A. Sloane, Jul 29 2012
Equals partial sums of A140434 (1, 2, 4, 4, 8, 4, 12, 8, ...) and row sums of triangle A143469. - Gary W. Adamson, Aug 17 2008
Number of distinct solutions to k*x+h=0, where 1 <= k,h <= n. - Giovanni Resta, Jan 08 2013
a(n) is the number of rational numbers which can be constructed from the set of integers between 1 and n, without combination of multiplication and division. a(3) = 7 because {1, 2, 3} can only create {1/3, 1/2, 2/3, 1, 3/2, 2, 3}. - Bernard Schott, Jul 07 2019

S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 110-112.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954. See Theorem 332.

Olivier Gérard, Table of n, a(n) for n = 1..100000 [Replaces an earlier b-file from Charles R Greathouse IV]
Jin-Yi Cai and Eric Bach, On testing for zero polynomials by a set of points with bounded precision, Theoret. Comput. Sci. 296 (2003), no. 1, 15-25. MR1965515 (2004m:68279).
Pieter Moree, Counting carefree couples, arXiv:math/0510003 [math.NT], 2005-2014.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
Eric Weisstein's World of Mathematics, Carefree Couple

Cf. A015614, A002088, A100613 (gcd > 1), A071778 (triples), A143469, A140434, A013661, A059956, A137243, A171503.
Cf. A177853 (partial sums).
The main diagonal of A331781, also of A333295.

a018805 n = length [()| x <- [1..n], y <- [1..n], gcd x y == 1]
-- Reinhard Zumkeller, Jan 21 2013

/* based on the first formula */ A018805:=func< n | 2*&+[ EulerPhi(k): k in [1..n] ]-1 >; [ A018805(n): n in [1..60] ]; // Klaus Brockhaus, Jan 27 2011

/* based on the second formula */ A018805:=func< n | n eq 1 select 1 else n^2-&+[ $$(n div j): j in [2..n] ] >; [ A018805(n): n in [1..60] ]; // Klaus Brockhaus, Feb 07 2011

N:= 1000; # to get the first N entries
P:= Array(1..N,numtheory:-phi);
A:= map(t -> 2*round(t)-1, Statistics:-CumulativeSum(P));
convert(A,list); # Robert Israel, Jul 16 2014

FoldList[ Plus, 1, 2 Array[ EulerPhi, 60, 2 ] ] (* Olivier Gérard, Aug 15 1997 *)
Accumulate[2*EulerPhi[Range[60]]]-1 (* Harvey P. Dale, Oct 21 2013 *)

PARI
```
a(n)=sum(k=1,n,moebius(k)*(n\k)^2)
```

A018805(n)=2 *sum(j=1, n, eulerphi(j)) - 1;
for(n=1, 99, print1(A018805(n), ", ")); /* show terms */

a(n)=my(s); forsquarefree(k=1,n, s+=moebius(k)*(n\k[1])^2); s \\ Charles R Greathouse IV, Jan 08 2018

from sympy import sieve
def A018805(n): return 2*sum(t for t in sieve.totientrange(1,n+1)) - 1 # Chai Wah Wu, Mar 23 2021

from functools import lru_cache
@lru_cache(maxsize=None)
def A018805(n): # based on second formula
    if n == 0:
        return 0
    c, j = 1, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*A018805(k1)
        j, k1 = j2, n//j2
    return n*(n-1)-c+j # Chai Wah Wu, Mar 24 2021

a(n) = 2*(Sum_{j=1..n} phi(j)) - 1.
a(n) = n^2 - Sum_{j=2..n} a(floor(n/j)).
a(n) = 2*A015614(n) + 1. - Reinhard Zumkeller, Apr 08 2006
a(n) = 2*A002088(n) - 1. - Hugo van der Sanden, Nov 22 2008
a(n) ~ (1/zeta(2)) * n^2 = (6/Pi^2) * n^2 as n goes to infinity (zeta is the Riemann zeta function, A013661, and the constant 6/Pi^2 is 0.607927..., A059956). - Ahmed Fares (ahmedfares(AT)my-deja.com), Jul 18 2001
a(n) ~ 6*n^2/Pi^2 + O(n*log n). - N. J. A. Sloane, May 31 2020
a(n) = Sum_{k=1..n} mu(k)*floor(n/k)^2. - Benoit Cloitre, May 11 2003
a(n) = A000290(n) - A100613(n) = A015614(n) + A002088(n). - Reinhard Zumkeller, Jan 21 2013
a(n) = A242114(floor(n/k),1), 1<=k<=n; particularly a(n) = A242114(n,1). - Reinhard Zumkeller, May 04 2014
a(n) = 2 * A005728(n) - 3. - David H Post, Dec 20 2016
a(n) ~ 6*n^2/Pi^2, cf. A059956. [Hardy and Wright] - M. F. Hasler, Jan 20 2017
G.f.: (1/(1 - x)) * (-x + 2 * Sum_{k>=1} mu(k) * x^k / (1 - x^k)^2). - Ilya Gutkovskiy, Feb 14 2020

More terms from Reinhard Zumkeller, Apr 08 2006

Link to Moree's paper corrected by Peter Luschny, Aug 08 2009

A196227 Number of 2 X 2 integer matrices with elements from {1,...,n} whose determinant is 1.

Original entry on oeis.org

0, 0, 2, 8, 14, 28, 34, 56, 70, 92, 106, 144, 158, 204, 226, 256, 286, 348, 370, 440, 470, 516, 554, 640, 670, 748, 794, 864, 910, 1020, 1050, 1168, 1230, 1308, 1370, 1464, 1510, 1652, 1722, 1816, 1878, 2036, 2082, 2248, 2326, 2420, 2506, 2688, 2750, 2916, 2994

Offset: 0

Aldo González Lorenzo, Sep 29 2011

nonn

It is also the number of 2 X 2 integer matrices with elements from {1,...,n} whose determinant is -1.

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Cf. A171503 (determinants of matrices that include zero), A209978, A210000.

a:= proc(n) option remember; `if`(n<2, 0,
      a(n-1)-2 + 4*numtheory[phi](n))
    end:
seq(a(n), n=0..60);  # Alois P. Heinz, May 05 2020

Table[cnt = 0; Do[If[a*d-b*c == 1, cnt++], {a, n}, {b, n}, {c, n}, {d, n}]; cnt, {n, 50}] (* T. D. Noe, Oct 11 2011 *)

a(n) = if(n < 1, 0, 4*sum(k=1, n, eulerphi(k)) - 2*(n + 1)) \\ Andrew Howroyd, May 05 2020

From Andrew Howroyd, May 05 2020: (Start)
a(n) = A171503(n) - (2*n + 1) for n > 0.
a(n) = -2*(n + 1) + 4*Sum_{k=1..n} phi(k) for n > 0.
a(n) = 2 * A209978(n). (End)

a(0)=0 prependend by Andrew Howroyd, May 05 2020

A206350 Position of 1/n in the canonical bijection from the positive integers to the positive rational numbers.

Original entry on oeis.org

1, 2, 4, 8, 12, 20, 24, 36, 44, 56, 64, 84, 92, 116, 128, 144, 160, 192, 204, 240, 256, 280, 300, 344, 360, 400, 424, 460, 484, 540, 556, 616, 648, 688, 720, 768, 792, 864, 900, 948, 980, 1060, 1084, 1168, 1208, 1256, 1300, 1392, 1424, 1508, 1548

Offset: 1

Clark Kimberling, Feb 06 2012

nonn

The canonical bijection from the positive integers to the positive rational numbers is given by A038568(n)/A038569(n).
Appears to be a variant of A049696. - R. J. Mathar, Feb 11 2012
Apparently numbers m such that A071912(m) = 1. - Bill McEachen, Aug 01 2023

			The canonical bijection starts with 1/1, 1/2, 2/1, 1/3, 3/1, 2/3, 3/2, 1/4, 4/1, 3/4, 4/3, 1/5, 5/1, so that A206297 starts with 1,3,5,9,13 and this sequence starts with 1,2,4,8,12.

G. C. Greubel, Table of n, a(n) for n = 1..10000

Cf. A000010, A008683, A038568, A038569, A049696, A171503, A206296.

Cf. A071912.

[1] cat [2*(&+[EulerPhi(k): k in [1..n-1]]): n in [2..80]]; // G. C. Greubel, Mar 29 2023

1, op(2*ListTools:-PartialSums(map(numtheory:-phi, [$1..100]))); # Robert Israel, Apr 24 2015

a[n_]:= Module[{s=1, k=2, j=1},
  While[s<=n, s= s + 2*EulerPhi[k]; k= k+1];
  s = s - 2*EulerPhi[k-1];
  While[s<=n, If[GCD[j, k-1] == 1,
    s = s+2]; j = j+1];
  If[s>n+1, j-1, k-1]];
t = Table[a[n], {n, 0, 3000}];   (* A038568 *)
ReplacePart[Flatten[Position[t, 1]], 1, 1] (* A206350 *)
(* Second program *)
a[n_]:= If[n==1, 1, 2*Sum[EulerPhi[k], {k, n-1}]];;
Table[a[n], {n, 80}] (* G. C. Greubel, Mar 29 2023 *)

def A206350(n): return 1 if (n==1) else 2*sum(euler_phi(k) for k in range(1,n))
[A206350(n) for n in range(1,80)] # G. C. Greubel, Mar 29 2023

a(1) = 1, a(n+1) = Sum_{k=1..n} mu(k) * floor(n/k) * floor(1 + n/k), where mu(k) is the Moebius function A008683. - Daniel Suteu, May 28 2018

a(n) = 2*Sum_{k=1..n-1} A000010(k), a(1) = 1. - Robert Israel, Apr 24 2015

A209982 Number of 2 X 2 matrices having all elements in {-n,...,n} and determinant 1.

Original entry on oeis.org

0, 20, 52, 116, 180, 308, 372, 564, 692, 884, 1012, 1332, 1460, 1844, 2036, 2292, 2548, 3060, 3252, 3828, 4084, 4468, 4788, 5492, 5748, 6388, 6772, 7348, 7732, 8628, 8884, 9844, 10356, 10996, 11508, 12276, 12660, 13812, 14388, 15156

Offset: 0

Clark Kimberling, Mar 17 2012

nonn

See A210000 for a guide to related sequences.

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Cf. A171503, A196227, A210000.

(See the Mathematica section at A209981.)

a(n)=if(n<1, 0, 32*sum(k=1, n, eulerphi(k)) - 12) \\ Andrew Howroyd, May 05 2020

From Andrew Howroyd, May 05 2020: (Start)
a(n) = 8*A196227(n) + 4*(4*n + 1) = 8*A171503(n) - 4 for n > 0.
a(n) = -12 + 32*Sum_{k=1..n} phi(k) for n > 0. (End)

A209991 Number of 2 X 2 matrices with all elements in {0,1,...,n} and determinant in {0,1}.

Original entry on oeis.org

1, 13, 38, 79, 136, 209, 302, 407, 536, 681, 846, 1015, 1240, 1441, 1678, 1951, 2240, 2505, 2854, 3151, 3552, 3945, 4326, 4687, 5216, 5657, 6110, 6615, 7192, 7649, 8342, 8831, 9472, 10105, 10702, 11407, 12272, 12857, 13526, 14279, 15224

Offset: 0

Clark Kimberling, Mar 18 2012

nonn

See A210000 for a guide to related sequences.

Cf. A059306, A171503, A210000.

a = 0; b = n; z1 = 40;
t[n_] := t[n] = Flatten[Table[w*z - x*y, {w, a, b}, {x, a, b}, {y, a, b}, {z, a, b}]]
c[n_, k_] := c[n, k] = Count[t[n], k]
c1[n_, m_] := c1[n, m] = Sum[c[n, k], {k, 0, 1}]
Table[c1[n, 1], {n, 0, z1}]    (* A209991 *)

A059306 + A171503.

A326354 a(n) is the number of fractions reduced to lowest terms with numerator and denominator less than or equal to n in absolute value.

Original entry on oeis.org

1, 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, 2783, 2847, 3015, 3095

Offset: 0

Stefano Spezia, Jul 06 2019

nonn

All the terms of this sequence are odd numbers (A005408).
For n > 1, a(n) is congruent to 7 mod 8 (A004771).
Apart from a(0) the same as A171503. - R. J. Mathar, Sep 03 2019

			a(0) = 1 since X(0) = {0};
a(1) = 3 since X(1) = {-1, 0, 1};
a(2) = 7 since X(2) = {-2, -1, -1/2, 0, 1/2, 1, 2};
a(3) = 15 since X(3) = {-3, -2, -3/2, -1, -2/3, -1/2, -1/3, 0, 1/3, 1/2, 2/3, 1, 3/2, 2, 3};
...

Cf. A000010, A004771, A005408, A171503, A206350.

I:=[1, 3]; [n le 2 select I[n] else Self(n-1)+4*EulerPhi(n-1): n in [1..51]];

nmax = 50; a=vector(nmax+1); a[1]=1; a[2]=3; for(n=3, nmax+1, a[n]=a[n-1]+4*eulerphi(n-1)); a

a(0) = 1, a(1) = 3 and a(n) = a(n-1) + 4*A000010(n) for n > 1, where A000010(n) = phi(n).

a(n) = 2*A206350(n+1) - 1. - Michel Marcus, Jul 07 2019

cp's OEIS Frontend

A210000 Number of unimodular 2 X 2 matrices having all terms in {0,1,...,n}.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A018805 Number of elements in the set {(x,y): 1 <= x,y <= n, gcd(x,y)=1}.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Formula

Extensions

A196227 Number of 2 X 2 integer matrices with elements from {1,...,n} whose determinant is 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A206350 Position of 1/n in the canonical bijection from the positive integers to the positive rational numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A209982 Number of 2 X 2 matrices having all elements in {-n,...,n} and determinant 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A209991 Number of 2 X 2 matrices with all elements in {0,1,...,n} and determinant in {0,1}.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula