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

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.

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

Example

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.

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

Prog

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

Crossrefs

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

Cf. also A068165.

Sequence in context: A160137 A371885 A107698 * A089754 A110743 A077549

Adjacent sequences: A068161 A068162 A068163 * A068165 A068166 A068167

Keyword

base,easy,nonn

Author

Amarnath Murthy, Feb 25 2002

Extensions

Corrected by Ray Chandler, Oct 11 2003

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

Status

approved