A116381 Number of compositions of n which are prime when concatenated and read as a decimal string.
0, 2, 1, 3, 7, 0, 29, 27, 0, 90, 236, 0, 758, 1039, 0, 3949, 9325, 0, 32907, 51243, 0, 184458, 426372, 0, 1552101, 2537233, 0, 9526385, 21117111, 0, 78112040, 134568638, 0, 505079269, 1096046406, 0
Offset: 1
Examples
The eight compositions of 4 are 4,13,31,22,112,121,211,1111 of which 3 {13,31,211} are primes.
Primes for n=11 are: 11, 29, 47, 83, 101, 137, 173, 191, 227, 263, 281, 317, 353, 443, 461, 641, 821, 911, 1163, 1181, ..., 131111111, 212111111, 1111111121, 1111211111, 1121111111.
Programs
-
Mathematica
f[n_] := If[n > 5 && Mod[n, 3] == 0, 0, Block[{len = PartitionsP@ n, p = IntegerPartitions[n], c = 0}, Do[c = c + Length@ Select[ FromDigits /@ Join @@@ IntegerDigits /@ Permutations@ p[[i]], PrimeQ@# &], {i, len}]; c]]; Array[f, 28] (* Robert G. Wilson v, Aug 03 2012 *) -
Python
from sympy import isprime from sympy.utilities.iterables import partitions, multiset_permutations def a(n): c = 0 for p in partitions(n): plst = [k for k in p for _ in range(p[k])] s = sum(sum(map(int, str(pi))) for pi in plst) if s != 3 and s%3 == 0: continue for m in multiset_permutations(plst): if isprime(int("".join(map(str, m)))): c += 1 return c print([a(n) for n in range(1, 22)]) # Michael S. Branicky, Nov 19 2022 -
Python
from collections import Counter from sympy.utilities.iterables import partitions, multiset_permutations from sympy import isprime def A116381(n): return sum(1 for p in partitions(n) for a in multiset_permutations(Counter(p).elements()) if isprime(int(''.join(str(d) for d in a)))) if n==3 or n%3 else 0 # Chai Wah Wu, Feb 21 2024
Extensions
a(29)-a(33) from Michael S. Branicky, Nov 19 2022
a(34)-a(36) from Michael S. Branicky, Jul 10 2023