A246806 Number of n-digit numbers whose base-10 representations can be written as the concatenations of 0 or more prime numbers (also expressed in base 10).
1, 4, 33, 285, 2643, 24920, 239543, 2327458, 22801065, 224608236, 2222034266, 22053438268
Offset: 0
Examples
For n = 2 the 33 numbers counted include the 21 primes between 10 and 99, and also the 12 numbers {22,25,27,32,33,35,52,55,57,72,75,77}.
Programs
-
Maple
P[1]:= {2,3,5,7}: C[1]:= P[1]: for n from 2 to 7 do P[n]:= select(isprime, {seq(2*i+1, i=10^(n-1)/2 .. 5*10^(n-1)-1)}); C[n]:= `union`(P[n],seq({seq(seq(c*10^j+p,p=P[j]),c=C[n-j])},j=1..n-1)); od: 1, seq(nops(C[n]),n=1..7); # Robert Israel, Dec 07 2014 -
Python
from sympy import isprime, primerange from functools import lru_cache @lru_cache(maxsize=None) def ok(n): if n%10 not in {1, 2, 3, 5, 7, 9}: return False if isprime(n): return True d = str(n) for i in range(1, len(d)): if d[i] != '0' and isprime(int(d[:i])) and ok(int(d[i:])): return True return False def a(n): return 1 if n == 0 else sum(ok(m) for m in range(10**(n-1), 10**n)) print([a(n) for n in range(7)]) # Michael S. Branicky, Mar 26 2021
Extensions
a(9) from Jeffrey Shallit, Dec 07 2014
a(10)-a(11) from Lars Blomberg, Feb 09 2019
Comments