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,2

Comments

Here we assume all representations involved are "canonical", that is, have no leading zeros. 1 is not a prime, and neither is 0.

Links

Table of n, a(n) for n=0..11.

Example

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

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

Prog

(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

Crossrefs

Cf. A006879, A246807.

Sequence in context: A041024 A088317 A257068 * A202765 A264830 A237872

Adjacent sequences: A246803 A246804 A246805 * A246807 A246808 A246809

Keyword

nonn,base,hard,more

Author

Jeffrey Shallit, Nov 16 2014

Extensions

a(9) from Jeffrey Shallit, Dec 07 2014

a(10)-a(11) from Lars Blomberg, Feb 09 2019

Status

approved