A049639 -id:A049639 - cp's OEIS frontend

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

Clark Kimberling

nonn

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

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

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

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

A206297 is an essentially identical sequence.

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

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

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

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

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

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

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

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

A049641 a(n) = Sum_{i=0..n} ((-1)^i)*T(i,n-i), array T as in A049639.

Original entry on oeis.org

0, 0, 2, 0, 3, 0, 5, 0, 7, 0, 11, 0, 13, 0, 19, 0, 23, 0, 29, 0, 33, 0, 43, 0, 47, 0, 59, 0, 65, 0, 73, 0, 81, 0, 97, 0, 103, 0, 121, 0, 129, 0, 141, 0, 151, 0, 173, 0, 181, 0, 201, 0, 213, 0, 231, 0, 243, 0, 271, 0, 279, 0, 309, 0, 325, 0, 345, 0, 361, 0, 385

Offset: 0

Clark Kimberling

nonn

G. C. Greubel, Table of n, a(n) for n = 0..75

Cf. A005728, A049643.

a[0 | 1, 0 | 1] = 0; a[0 | 1, ] = a[, 0 | 1] = 1; a[i_, j_]:= Module[{slopes, cnt}, slopes = Union@Flatten@Table[(k - j)/(h - i), {h, 0, i - 1}, {k, 0, j - 1}]; cnt[slope_] := Count[Flatten[Table[{h, k}, {h, 0, i - 1}, {k, 0, j - 1}], 1], {h_, k_} /; (k - j)/(h - i) == slope]; Count[cnt /@ slopes, c_ /; c >= 2] + 2]; Table[Sum[(-1)^k*a[k, n - k], {k, 0, n}], {n, 0, 25}] (* G. C. Greubel, Dec 07 2017 *)

Terms a(42) onward added by G. C. Greubel, Dec 07 2017

A049640 a(n) = Sum_{i=0..n} T(i,n-i), array T as in A049639.

Original entry on oeis.org

0, 0, 2, 4, 7, 10, 15, 20, 27, 34, 45, 56, 69, 82, 101, 120, 143, 166, 195, 224, 257, 290, 333, 376, 423, 470, 529, 588, 653, 718, 791, 864, 945, 1026, 1123, 1220, 1323, 1426, 1547, 1668, 1797, 1926, 2067, 2208, 2359, 2510, 2683, 2856, 3037, 3218, 3419, 3620, 3833, 4046, 4277, 4508

Offset: 0

Clark Kimberling

nonn

G. C. Greubel, Table of n, a(n) for n = 0..75

a[0 | 1, 0 | 1] = 0; a[0 | 1, ] = a[, 0 | 1] = 1; a[i_, j_] := Module[{slopes, cnt}, slopes = Union@Flatten@Table[(k - j)/(h - i), {h, 0, i - 1}, {k, 0, j - 1}]; cnt[slope_] := Count[Flatten[Table[{h, k}, {h, 0, i - 1}, {k, 0, j - 1}], 1], {h_, k_} /; (k - j)/(h - i) == slope]; Count[cnt /@ slopes, c_ /; c >= 2] + 2]; Table[Sum[a[k, n - k], {k, 0, n}], {n, 0, 25}] (* G. C. Greubel, Dec 15 2017 *)

Terms a(41) and beyond added by G. C. Greubel, Dec 15 2017

A049644 T(n,n), array T given by A049639.

Original entry on oeis.org

0, 0, 3, 3, 5, 5, 9, 9, 13, 13, 21, 21, 25, 25, 37, 37, 45, 45, 57, 57, 65, 65, 85, 85, 93, 93, 117, 117, 129, 129, 145, 145, 161, 161, 193, 193, 205, 205, 241, 241, 257, 257, 281, 281, 301, 301, 345, 345, 361, 361, 401, 401, 425, 425, 461, 461, 485, 485, 541, 541, 557, 557

Offset: 0

Clark Kimberling

nonn

G. C. Greubel, Table of n, a(n) for n = 0..75

Cf. A049691, A206297.

a[0 | 1, 0 | 1] = 0; a[0 | 1, ] = a[, 0 | 1] = 1; a[i_, j_] := Module[{slopes, cnt}, slopes = Union@Flatten@Table[(k - j)/(h - i), {h, 0, i - 1}, {k, 0, j - 1}]; cnt[slope_] := Count[Flatten[Table[{h, k}, {h, 0, i - 1}, {k, 0, j - 1}], 1], {h_, k_} /; (k - j)/(h - i) == slope]; Count[cnt /@ slopes, c_ /; c >= 2] + 2]; Table[a[n, n], {n, 0, 25}] (* G. C. Greubel, Dec 07 2017 *)

Terms a(42) onward added by G. C. Greubel, Dec 10 2017

A049646 a(n) = T(n,n+1), array T given by A049639.

Original entry on oeis.org

0, 1, 3, 4, 5, 7, 9, 11, 13, 17, 21, 23, 25, 31, 37, 41, 45, 51, 57, 61, 65, 75, 85, 89, 93, 105, 117, 123, 129, 137, 145, 153, 161, 177, 193, 199, 205, 223, 241, 249, 257, 269, 281, 291, 301, 323, 345, 353, 361, 381, 401, 413, 425, 443, 461, 473, 485, 513, 541, 549, 557

Offset: 0

Clark Kimberling

nonn

G. C. Greubel, Table of n, a(n) for n = 0..75

Cf. A049639.

a[0 | 1, 0 | 1] = 0; a[0 | 1, ] = a[, 0 | 1] = 1; a[i_, j_] := Module[{slopes, cnt}, slopes = Union@Flatten@Table[(k - j)/(h - i), {h, 0, i - 1}, {k, 0, j - 1}]; cnt[slope_] := Count[Flatten[Table[{h, k}, {h, 0, i - 1}, {k, 0, j - 1}], 1], {h_, k_} /; (k - j)/(h - i) == slope]; Count[cnt /@ slopes, c_ /; c >= 2] + 2]; Table[a[n, n + 1], {n, 0, 25}] (* G. C. Greubel, Dec 07 2017 *)

Terms a(39)-a(60) added by G. C. Greubel, Dec 07 2017

A049649 T(n,n+3), array T given by A049639.

Original entry on oeis.org

1, 1, 4, 5, 7, 8, 11, 14, 17, 18, 23, 28, 31, 34, 41, 46, 51, 54, 61, 70, 75, 78, 89, 100, 105, 110, 123, 130, 137, 144, 153, 168, 177, 182, 199, 216, 223, 230, 249, 260, 269, 278, 291, 312, 323, 330, 353, 372, 381, 392, 413, 430, 443, 454, 473, 500, 513, 520, 549, 578, 587, 602

Offset: 0

Clark Kimberling

nonn

Sean A. Irvine, Table of n, a(n) for n = 0..500 (terms 1..76 from G. C. Greubel)

Cf. A049639.

T[0 | 1, 0 | 1] = 0; T[0 | 1, ] = T[, 0 | 1] = 1; T[i_, j_] := Module[{slopes, cnt}, slopes = Union@Flatten@Table[(k - j)/(h - i), {h, 0, i - 1}, {k, 0, j - 1}]; cnt[slope_] := Count[Flatten[Table[{h, k}, {h, 0, i - 1}, {k, 0, j - 1}], 1], {h_, k_} /; (k - j)/(h - i) == slope]; Count[cnt /@ slopes, c_ /; c >= 2] + 2]; Table[T[n, n + 3], {n, 0, 50}] (* G. C. Greubel, Dec 05 2017 *)

Terms a(37) onward added by G. C. Greubel, Dec 10 2017

Missing a(0)=1 inserted by Sean A. Irvine, Aug 06 2021

A049647 a(n) = T(n,n+2), array T given by A049639.

Original entry on oeis.org

1, 1, 4, 4, 7, 7, 11, 11, 17, 17, 23, 23, 31, 31, 41, 41, 51, 51, 61, 61, 75, 75, 89, 89, 105, 105, 123, 123, 137, 137, 153, 153, 177, 177, 199, 199, 223, 223, 249, 249, 269, 269, 291, 291, 323, 323, 353, 353, 381, 381, 413, 413, 443, 443, 473, 473, 513, 513

Offset: 0

Clark Kimberling

nonn

More terms from Sean A. Irvine, Aug 06 2021

A049648 T(n,n+1), array T as in A049687 and T(2n,2n+2), array T given by A049639.

Original entry on oeis.org

1, 4, 7, 11, 17, 23, 31, 41, 51, 61, 75, 89, 105, 123, 137, 153, 177, 199, 223, 249, 269, 291, 323, 353, 381, 413, 443, 473, 513, 549, 587, 633, 669, 705, 745, 781, 829, 883, 925, 965, 1021, 1073, 1127, 1189, 1233, 1279, 1347, 1409, 1467, 1529, 1581, 1637

Offset: 0

Clark Kimberling

nonn

More terms from Michael Somos

A049687 Array T read by diagonals: T(i,j)=number of lines passing through (0,0) and at least one other lattice point (h,k) satisfying 0<=h<=i, 0<=k<=j.

Original entry on oeis.org

0, 1, 1, 1, 3, 1, 1, 4, 4, 1, 1, 5, 5, 5, 1, 1, 6, 7, 7, 6, 1, 1, 7, 8, 9, 8, 7, 1, 1, 8, 10, 11, 11, 10, 8, 1, 1, 9, 11, 14, 13, 14, 11, 9, 1, 1, 10, 13, 15, 17, 17, 15, 13, 10, 1, 1, 11, 14, 18, 18, 21, 18, 18, 14, 11, 1, 1, 12, 16, 20, 22, 23, 23, 22, 20, 16, 12, 1, 1, 13, 17, 22, 24

Offset: 0

Clark Kimberling

			The array begins:
0 1 1 1 1  ...
1 3 4 5 6  ...
1 4 5 7 8  ...
1 5 7 9 11 ...
1 6 8 11 13 ...
...

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

Main diagonal is A049691.

Cf. A049639, A135646, A300778.

a[0, 0] = 0; a[0, ] = a[, 0] = 1; a[i_, j_] := Module[{slopes, cnt}, slopes = Union @ Flatten @ Table[k/h, {h, 1, i }, {k, 1, j }]; cnt[ slope_] := Count[Flatten[Table[{h, k}, {h, 1, i }, {k, 1, j }], 1], {h_, k_} /; k/h == slope]; Count[cnt /@ slopes, c_ /; c >= 1] + 2]; Table[a[i-j, j], {i, 0, 12}, {j, 0, i}] // Flatten (* Jean-François Alcover, Apr 03 2017 *)

T(i,j) = (i>0) + (j>0) + sum(g=1, min(i,j), (i\g) * (j\g) * moebius(g));
for (i=0, 10, for(j=0, 10, print1(T(i,j), ", ")); print); \\ Andrew Howroyd, Sep 17 2017

T(i,j) = sum(h=0, i, sum(k=0, j, gcd(h,k) == 1)); \\ Andrew Howroyd, Sep 17 2017

From Andrew Howroyd, Sep 17 2017: (Start)
T(i, j) = 2 + Sum_{g=1..min(i,j)} floor(i/g) * floor(j/g) * mu(g) for i > 0, j > 0.
T(i, j) = signum(i) + signum(j) + A135646(i, j).
T(i, j) = |{(x, y): gcd(x, y) = 1, 0<=x<=i, 0<=y<=j}|.
(End)

More terms from Michael Somos

A049704 Array T read by antidiagonals; T(i,j)=number of nonnegative slopes of lines determined by two points in the triangular set {(x,y): 0<=x<=i, 0<=y<=j-j*x/i} of lattice points.

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 3, 4, 3, 1, 1, 1, 1, 3, 4, 4, 3, 1, 1, 1, 1, 4, 5, 6, 5, 4, 1, 1, 1, 1, 4, 6, 6, 6, 6, 4, 1, 1, 1, 1, 5, 6, 8, 10, 8, 6, 5, 1, 1, 1, 1, 5, 7, 9, 10, 10, 9, 7, 5, 1, 1, 1, 1, 6, 9, 11, 11, 12, 11, 11

Offset: 0

Clark Kimberling

			The array begins:
0 1 1 1 1 1 1 1 1...
1 1 1 1 1 1 1 1 1...
1 1 2 2 3 3 4 4 5...
1 1 2 4 4 5 6 6 7...
1 1 3 4 6 6 8 9 11...
...

Cf. A049600, A049615, A049639, A049687, A049695, A049702. Cf. A049706-A049709. Main diagonal: A002088.

t[i_,j_] := If[i==0||j==0, 1-KroneckerDelta[i+j], 1+Length[Union[Divide@@#& /@ Select[-Subtract@@@Subsets[Flatten[Table[{x,y}, {x,0,i}, {y,0,j-j*x/i}], 1], {2}], And@@Positive/@#&]]]];
(*Table[t[i,j], {i,0,10}, {j,0,10}]//TableForm*)
Flatten@Table[t[j,i-j], {i,0,20}, {j,0,i}]
(* Andrey Zabolotskiy, Jun 09 2017 *)

Name corrected by Michel Marcus and Andrey Zabolotskiy, Jun 10 2017

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

Extensions

A049641 a(n) = Sum_{i=0..n} ((-1)^i)*T(i,n-i), array T as in A049639.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A049640 a(n) = Sum_{i=0..n} T(i,n-i), array T as in A049639.

Views

Author

Keywords

Links

Programs

Mathematica

Extensions

A049644 T(n,n), array T given by A049639.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A049646 a(n) = T(n,n+1), array T given by A049639.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A049649 T(n,n+3), array T given by A049639.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A049647 a(n) = T(n,n+2), array T given by A049639.

Views

Author

Keywords

Extensions

A049648 T(n,n+1), array T as in A049687 and T(2n,2n+2), array T given by A049639.

Views

Author

Keywords

Extensions

A049687 Array T read by diagonals: T(i,j)=number of lines passing through (0,0) and at least one other lattice point (h,k) satisfying 0<=h<=i, 0<=k<=j.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs