A068164 Smallest prime obtained from n by inserting zero or more decimal digits.

11, 2, 3, 41, 5, 61, 7, 83, 19, 101, 11, 127, 13, 149, 151, 163, 17, 181, 19, 1201, 211, 223, 23, 241, 251, 263, 127, 281, 29, 307, 31, 1321, 233, 347, 353, 367, 37, 383, 139, 401, 41, 421, 43, 443, 457, 461, 47, 487, 149, 503, 151, 521, 53, 541, 557, 563, 157

Offset: 1

Author

Amarnath Murthy, Feb 25 2002

Keywords

• base
• easy
• nonn

Comments

The digits may be added before, in the middle of, or after the digits of n.

a(n) = n for prime n, by definition. - Zak Seidov, Nov 13 2014

a(n) always exists. Proof. Suppose n is L digits long, and let n' = 10*n+1. The arithmetic progression k*10^(2L)+n' (k >= 0) contains infinitely many primes, by Dirichlet's theorem, and they all contain the digits of n. QED. - Robert Israel, Nov 13 2014. For another proof, see A018800.

Similar to but different from A062584. E.g. a(133) = 1033, but A062584(133) = 4133.

Examples

			Smallest prime formed from 20 is 1201, by placing 1 on both sides. Smallest prime formed from 33 is 233, by placing a 2 in front.
		

Links

• Michael S. Branicky, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Allan C. Wechsler)
• Index entries for primes involving decimal expansion of n

Crossrefs

Cf. A018800 (an upper bound), A060386, A062584 (also an upper bound).

Cf. also A068165.

Programs

Haskell

a068164 n = head (filter isPrime (digitExtensions n))
digitExtensions n = filter (includes n) [0..]
includes n k = listIncludes (show n) (show k)
listIncludes [] _ = True
listIncludes (h:_) [] = False
listIncludes l1@(h1:t1) (h2:t2) = if (h1 == h2) then (listIncludes t1 t2) else (listIncludes l1 t2)
isPrime 1 = False
isPrime n = not (hasDivisorAtLeast 2 n)
hasDivisorAtLeast k n = (k*k <= n) && (((n `rem` k) == 0) || (hasDivisorAtLeast (k+1) n))

Maple

A068164 := proc(n)
    local p,pdigs,plen,dmas,dmasdigs,i,j;
    # test all primes ascending
    p := 2;
    while true do
        pdigs := convert(p,base,10) ;
        plen := nops(pdigs) ;
        # binary digit mask over p
        for dmas from 2^plen-1 to 0 by -1 do
            dmasdigs := convert(dmas,base,2) ;
            pdel := [] ;
            for i from 1 to nops(dmasdigs) do
                if op(i,dmasdigs) = 1 then
                    pdel := [op(pdel),op(i,pdigs)] ;
                end if;
            end do:
            if n = add(op(j,pdel)*10^(j-1),j=1..nops(pdel)) then
                return p;
            end if;
        end do:
        p := nextprime(p) ;
    end do:
end proc:
seq(A068164(n),n=1..120) ; # R. J. Mathar, Nov 13 2014

Python

from sympy import sieve
def dmo(n, t):
    if t < n: return False
    while n and t:
        if n%10 == t%10:
            n //= 10
        t //= 10
    return n == 0
def a(n):
    return next(p for p in sieve if dmo(n, p))
print([a(n) for n in range(1, 77)]) # Michael S. Branicky, Jan 21 2023

Extensions

Corrected by Ray Chandler, Oct 11 2003

Haskell code and b-file added by Allan C. Wechsler, Nov 13 2014