cp's OEIS Frontend

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).

%I A246806 #36 Mar 27 2021 03:54:24
%S A246806 1,4,33,285,2643,24920,239543,2327458,22801065,224608236,2222034266,
%T A246806 22053438268
%N 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).
%C A246806 Here we assume all representations involved are "canonical", that is, have no leading zeros.  1 is not a prime, and neither is 0.
%e A246806 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}.
%p A246806 P[1]:= {2,3,5,7}: C[1]:= P[1]:
%p A246806 for n from 2 to 7 do
%p A246806   P[n]:= select(isprime, {seq(2*i+1, i=10^(n-1)/2 .. 5*10^(n-1)-1)});
%p A246806   C[n]:= `union`(P[n],seq({seq(seq(c*10^j+p,p=P[j]),c=C[n-j])},j=1..n-1));
%p A246806 od:
%p A246806 1, seq(nops(C[n]),n=1..7); # _Robert Israel_, Dec 07 2014
%o A246806 (Python)
%o A246806 from sympy import isprime, primerange
%o A246806 from functools import lru_cache
%o A246806 @lru_cache(maxsize=None)
%o A246806 def ok(n):
%o A246806   if n%10 not in {1, 2, 3, 5, 7, 9}: return False
%o A246806   if isprime(n): return True
%o A246806   d = str(n)
%o A246806   for i in range(1, len(d)):
%o A246806     if d[i] != '0' and isprime(int(d[:i])) and ok(int(d[i:])): return True
%o A246806   return False
%o A246806 def a(n): return 1 if n == 0 else sum(ok(m) for m in range(10**(n-1), 10**n))
%o A246806 print([a(n) for n in range(7)]) # _Michael S. Branicky_, Mar 26 2021
%Y A246806 Cf. A006879, A246807.
%K A246806 nonn,base,hard,more
%O A246806 0,2
%A A246806 _Jeffrey Shallit_, Nov 16 2014
%E A246806 a(9) from _Jeffrey Shallit_, Dec 07 2014
%E A246806 a(10)-a(11) from _Lars Blomberg_, Feb 09 2019