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!)
A068164 Smallest prime obtained from n by inserting zero or more decimal digits. 10
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 (list; graph; refs; listen; history; text; internal format)
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

Allan C. Wechsler, Table of n, a(n) for n = 1..1000

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

CROSSREFS

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

Cf. also A068165.

Sequence in context: A089744 A160137 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

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 February 20 20:08 EST 2020. Contains 332084 sequences. (Running on oeis4.)