cp's OEIS Frontend

A317131 Number of permutations of [n] whose lengths of increasing runs are prime numbers.

%I A317131 #16 Mar 29 2021 08:00:41
%S A317131 1,0,1,1,5,19,80,520,2898,22486,171460,1509534,14446457,147241144,
%T A317131 1650934446,19494460567,248182635904,3340565727176,47659710452780,
%U A317131 718389090777485,11381176852445592,189580213656445309,3305258537062221020,60273557241570401742
%N A317131 Number of permutations of [n] whose lengths of increasing runs are prime numbers.
%H A317131 Alois P. Heinz, <a href="/A317131/b317131.txt">Table of n, a(n) for n = 0..400</a>
%e A317131 a(2) = 1: 12.
%e A317131 a(3) = 1: 123.
%e A317131 a(4) = 5: 1324, 1423, 2314, 2413, 3412.
%e A317131 a(5) = 19: 12345, 12435, 12534, 13245, 13425, 13524, 14235, 14523, 15234, 23145, 23415, 23514, 24135, 24513, 25134, 34125, 34512, 35124, 45123.
%p A317131 g:= n-> `if`(n=0 or isprime(n), 1, 0):
%p A317131 b:= proc(u, o, t) option remember; `if`(u+o=0, g(t),
%p A317131       `if`(g(t)=1, add(b(u-j, o+j-1, 1), j=1..u), 0)+
%p A317131        add(b(u+j-1, o-j, t+1), j=1..o))
%p A317131     end:
%p A317131 a:= n-> b(n, 0$2):
%p A317131 seq(a(n), n=0..27);
%t A317131 g[n_] := If[n == 0 || PrimeQ[n], 1, 0];
%t A317131 b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, g[t],
%t A317131      If[g[t] == 1, Sum[b[u - j, o + j - 1, 1], {j, 1, u}], 0] +
%t A317131      Sum[b[u + j - 1, o - j, t + 1], {j, 1, o}]];
%t A317131 a[n_] := b[n, 0, 0];
%t A317131 a /@ Range[0, 27] (* _Jean-François Alcover_, Mar 29 2021, after _Alois P. Heinz_ *)
%o A317131 (Python)
%o A317131 from functools import lru_cache
%o A317131 from sympy import isprime
%o A317131 def g(n): return int(n == 0 or isprime(n))
%o A317131 @lru_cache(maxsize=None)
%o A317131 def b(u, o, t):
%o A317131   if u + o == 0: return g(t)
%o A317131   return (sum(b(u-j,  o+j-1,  1) for j in range(1, u+1)) if g(t) else 0) +\
%o A317131           sum(b(u+j-1, o-j, t+1) for j in range(1, o+1))
%o A317131 def a(n): return b(n, 0, 0)
%o A317131 print([a(n) for n in range(28)]) # _Michael S. Branicky_, Mar 29 2021 after _Alois P. Heinz_
%Y A317131 Cf. A000040, A097597, A218002, A317111, A317128, A317129, A317130, A317132, A317447.
%K A317131 nonn
%O A317131 0,5
%A A317131 _Alois P. Heinz_, Jul 21 2018