A049691 a(n)=T(n,n), array T as in A049687. Also a(n)=T(2n,2n), array T given by A049639.

0, 3, 5, 9, 13, 21, 25, 37, 45, 57, 65, 85, 93, 117, 129, 145, 161, 193, 205, 241, 257, 281, 301, 345, 361, 401, 425, 461, 485, 541, 557, 617, 649, 689, 721, 769, 793, 865, 901, 949, 981, 1061, 1085, 1169, 1209, 1257, 1301, 1393, 1425, 1509, 1549

Offset: 0

Author

Clark Kimberling

Keywords

• nonn

Comments

a(n) is related to the sequence b(n) = |{(x, y): gcd(x, y) = 1, 1<=x, y<=n}| (A018805) as follows: a(n) = b(n - 1) + 2 (for n > 1). - Shawn Westmoreland (westmore(AT)math.utexas.edu), Jun 11 2003

Comment from N. J. A. Sloane, Sep 08 2019 (Start)

The above comment can be rephrased as saying that a(n) is the cardinality of the subsequence F(B(2n),n) of the Farey series F_{2n} that is extensively studied in Matveev (2017). See the definition on page 1.

For example, F(B(2),1), F(B(4),2), F(B(6),3), and F(B(8),4) are:

[0, 1/2, 1],

[0, 1/3, 1/2, 2/3, 1],

[0, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 1],

[0, 1/5, 1/4, 1/3, 2/5, 3/7, 1/2, 4/7, 3/5, 2/3, 3/4, 4/5, 1],

of cardinalities 3,5,9,13 respectively. See also A324796/A324797. (End)

a(n) is the number of visible points on an n X n square lattice when viewed from (0, 0), (0, n), (n, 0), or (n, n). - Torlach Rush, Nov 16 2020

Also number of elements in { c/d ; -d <= c <= d <= n }, i.e., distinct fractions with denominator not exceeding n and absolute value of numerator not exceeding the denominator. - M. F. Hasler, Mar 26 2023

References

• A. O. Matveev, Farey Sequences, De Gruyter, 2017.

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..1000
• A. O. Matveev, Farey Sequences: Errata + Haskell code
• Eric Weisstein's World of Mathematics, Visible Point

Crossrefs

Cf. A000010, A018805, A049687, A324796, A324797.

A206297 is an essentially identical sequence.

Programs

Maple

Farey := proc(n) sort(convert(`union`({0}, {seq(seq(m/k, m=1..k), k=1..n)}), list)) end: # A006842/A006843
BF := proc(m) local a,i,h,k; global Farey; a:=[];
for i in Farey(2*m) do h:=numer(i); k:=denom(i);
if (h <= m) and (k-m <= h) then a:=[op(a),i]; fi; od: a; end;
[seq(nops(BF(m),m=1..20)]; # this sequence - N. J. A. Sloane, Sep 08 2019

Mathematica

a[0] = 0; a[n_] := 2 + Sum[Quotient[n, g]^2*MoebiusMu[g], {g, 1, n}]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Oct 07 2017, translated from PARI *)

PARI

a(n) = if(n>0, 2, 0) + sum(g=1, n, (n\g)^2 * moebius(g)); \\ Andrew Howroyd, Sep 17 2017

PARI

a(n) = if(n>0, 1, 0) + 2 * sum(k=1, n, eulerphi(k)); \\ Torlach Rush, Nov 24 2020

PARI

a(n)=#Set(concat([[c/d|c<-[-d..d],d]|d<-[0..n]])) \\ For illustrative purpose only! - M. F. Hasler, Mar 26 2023

Python

from functools import lru_cache
@lru_cache(maxsize=None)
def A049691(n):
    if n == 0:
        return 0
    c, j = 1, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*(A049691(k1)-2)
        j, k1 = j2, n//j2
    return n*(n-1)-c+j+2 # Chai Wah Wu, Aug 04 2024

Formula

a(n) = A206297(n+1) = 2 + A018805(n) for n > 0. - Andrew Howroyd, Sep 17 2017

a(n) = 1 + 2 * Sum{k=1..n} A000010(k), n > 0. - Torlach Rush, Nov 24 2020

Extensions

Terms a(41) and beyond from Andrew Howroyd, Sep 17 2017