A308273 Number of lattice paths from (0,0) to (n,n) that do not go above the diagonal x=y and consist of steps (h,v) with h, v prime or one.

1, 1, 2, 5, 13, 35, 98, 286, 858, 2626, 8174, 25809, 82426, 265773, 864055, 2829271, 9321987, 30883103, 102812795, 343766977, 1153937954, 3887228976, 13137039376, 44528001849, 151335579837, 515617409850, 1760800369203, 6025806553007, 20662226579437

Offset

0,3

Links

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

Wikipedia, Counting lattice paths

Formula

a(n) ~ c * d^n / n^(3/2), where d = 3.6172380297768018622526884344929286291... and c = 0.7309642723485496808628027041489824... - Vaclav Kotesovec, Feb 17 2026

Maple

b:= proc(x, y) option remember; `if`(y=0, 1, add(add(
     `if`((h=1 or isprime(h)) and (v=1 or isprime(v))
      and (x-h<=y-v), b(x-h, y-v), 0), v=1..y), h=1..x))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..30);

Mathematica

f[p_List] := p + {0, p[[1]]}; f[0] = 0;
b[{x_, y_}] := b[{x, y}] = If[y == 0, {1, 1}, f[Sum[Sum[
     If[(h == 1 || PrimeQ[h]) && (v == 1 || PrimeQ[v])
     && x - h <= y - v, b[Sort@{x - h, y - v}], {0, 0}],
     {v, 1, y}], {h, 1, x}]]];
a[n_] := b[{n, n}][[1]];
a /@ Range[0, 30] (* Jean-François Alcover, Apr 05 2021, after Alois P. Heinz *)

Crossrefs

Cf. A000040, A008578, A308240, A308274.

Sequence in context: A025198 A221205 A037247 * A126221 A376277 A107086

Adjacent sequences: A308270 A308271 A308272 * A308274 A308275 A308276

Keyword

nonn

Author

Alois P. Heinz, May 17 2019

Status

approved