A062115 Numbers with no prime substring in their decimal expansion.

0, 1, 4, 6, 8, 9, 10, 14, 16, 18, 40, 44, 46, 48, 49, 60, 64, 66, 68, 69, 80, 81, 84, 86, 88, 90, 91, 94, 96, 98, 99, 100, 104, 106, 108, 140, 144, 146, 148, 160, 164, 166, 168, 169, 180, 184, 186, 188, 400, 404, 406, 408, 440, 444, 446, 448, 460, 464, 466

Offset: 1

Author

Erich Friedman, Jun 28 2001

Keywords

• base
• easy
• nonn

Comments

This is a 10-automatic sequence, a consequence of the finitude of A071062. - Charles R Greathouse IV, Sep 27 2011

Subsequence of A202259 (right-truncatable nonprimes). Supersequence of A202262 (composite numbers in which all substrings are composite), A202265 (nonprime numbers in which all substrings and reversal substrings are nonprimes). - Jaroslav Krizek, Jan 28 2012

Examples

			25 is not included because 5 is prime.
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• Jeffrey Shallit, Minimal primes, Journal of Recreational Mathematics 30:2 (1999-2000), pp. 113-117.
• Index entries for 10-automatic sequences.

Crossrefs

Subsequence of A084984. [Arkadiusz Wesolowski, Jul 05 2011]

Cf. A071062.

Cf. A163753 (complement).

Programs

Haskell

a062115 n = a062115_list !! (n-1)
a062115_list = filter ((== 0) . a039997) a084984_list
-- Reinhard Zumkeller, Jan 31 2012

Python

from sympy import isprime
def ok(n):
    s = str(n)
    ss = (int(s[i:j]) for i in range(len(s)) for j in range(i+1, len(s)+1))
    return not any(isprime(k) for k in ss)
print([k for k in range(500) if ok(k)]) # Michael S. Branicky, May 02 2023

Python

# faster for initial segment of sequence; uses ok, import above
from itertools import chain, count, islice, product
def agen(): # generator of terms
    yield from chain((0,), (int(t) for t in (f+"".join(r) for d in count(1) for f in "14689" for r in product("014689", repeat=d-1)) if ok(t)))
print(list(islice(agen(), 100))) # Michael S. Branicky, May 02 2023

Formula

A039997(a(n)) = 0. - Reinhard Zumkeller, Jul 16 2007

From Charles R Greathouse IV, Mar 23 2010: (Start)

a(n) = O(n^(log_4 10)) = O(n^1.661) because numbers containing only 0,4,6,8 are in this sequence.

a(n) = Omega(n^(log_13637 1000000)) = Omega(n^1.451) for similar reasons; this bound can be increased by considering longer sequences of digits. (End)

Extensions

Offset corrected by Arkadiusz Wesolowski, Jul 27 2011