A368672 Total number of lattice paths from (0,0) to (k,n-k) for k=0..n using steps (i,j) with i,j>=0 and gcd(i,j)=1.

1, 2, 5, 14, 39, 110, 307, 860, 2407, 6736, 18851, 52758, 147651, 413224, 1156469, 3236546, 9057955, 25350028, 70945807, 198552344, 555678123, 1555147480, 4352310421, 12180584958, 34089170027, 95403588336, 267001063969, 747242000068, 2091267346883, 5852721227868

Offset

0,2

Links

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

Formula

a(n) mod 2 = 1 - (n mod 2) = A059841(n).

a(n) ~ c * d^n, where d = 2.798648023933224047287803536948757710187420348758496337690531870498937575... and c = 0.639525188357518889842205998775477309094300590250850025271938769053628196... - Vaclav Kotesovec, Jan 13 2024

Maple

b:= proc(n, k) option remember; `if`(min(n, k)=0, 1, add(add(
      `if`(igcd(i, j)=1, b(n-i, k-j), 0), j=0..k), i=0..n))
    end:
a:= n-> add(b(k, n-k), k=0..n):
seq(a(n), n=0..29);

Crossrefs

Row sums of A362242.

Cf. A059841.

Sequence in context: A202207 A132834 A000641 * A026135 A201778 A367655

Adjacent sequences: A368669 A368670 A368671 * A368673 A368674 A368675

Keyword

nonn

Author

Alois P. Heinz, Jan 02 2024

Status

approved