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