login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
1, 4, 33, 285, 2643, 24920, 239543, 2327458, 22801065, 224608236, 2222034266, 22053438268 (list; graph; refs; listen; history; text; internal format)
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: A088317 A041024 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 6 04:53 EDT 2021. Contains 343580 sequences. (Running on oeis4.)