|
%I #35 Jan 21 2023 01:58:54
%S 11,2,3,41,5,61,7,83,19,101,11,127,13,149,151,163,17,181,19,1201,211,
%T 223,23,241,251,263,127,281,29,307,31,1321,233,347,353,367,37,383,139,
%U 401,41,421,43,443,457,461,47,487,149,503,151,521,53,541,557,563,157
%N Smallest prime obtained from n by inserting zero or more decimal digits.
%C The digits may be added before, in the middle of, or after the digits of n.
%C a(n) = n for prime n, by definition. - _Zak Seidov_, Nov 13 2014
%C 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.
%C Similar to but different from A062584. E.g. a(133) = 1033, but A062584(133) = 4133.
%H Michael S. Branicky, <a href="/A068164/b068164.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..1000 from Allan C. Wechsler)
%H <a href="/index/Pri#piden">Index entries for primes involving decimal expansion of n</a>
%e 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.
%p A068164 := proc(n)
%p local p,pdigs,plen,dmas,dmasdigs,i,j;
%p # test all primes ascending
%p p := 2;
%p while true do
%p pdigs := convert(p,base,10) ;
%p plen := nops(pdigs) ;
%p # binary digit mask over p
%p for dmas from 2^plen-1 to 0 by -1 do
%p dmasdigs := convert(dmas,base,2) ;
%p pdel := [] ;
%p for i from 1 to nops(dmasdigs) do
%p if op(i,dmasdigs) = 1 then
%p pdel := [op(pdel),op(i,pdigs)] ;
%p end if;
%p end do:
%p if n = add(op(j,pdel)*10^(j-1),j=1..nops(pdel)) then
%p return p;
%p end if;
%p end do:
%p p := nextprime(p) ;
%p end do:
%p end proc:
%p seq(A068164(n),n=1..120) ; # _R. J. Mathar_, Nov 13 2014
%o (Haskell)
%o a068164 n = head (filter isPrime (digitExtensions n))
%o digitExtensions n = filter (includes n) [0..]
%o includes n k = listIncludes (show n) (show k)
%o listIncludes [] _ = True
%o listIncludes (h:_) [] = False
%o listIncludes l1@(h1:t1) (h2:t2) = if (h1 == h2) then (listIncludes t1 t2) else (listIncludes l1 t2)
%o isPrime 1 = False
%o isPrime n = not (hasDivisorAtLeast 2 n)
%o hasDivisorAtLeast k n = (k*k <= n) && (((n `rem` k) == 0) || (hasDivisorAtLeast (k+1) n))
%o (Python)
%o from sympy import sieve
%o def dmo(n, t):
%o if t < n: return False
%o while n and t:
%o if n%10 == t%10:
%o n //= 10
%o t //= 10
%o return n == 0
%o def a(n):
%o return next(p for p in sieve if dmo(n, p))
%o print([a(n) for n in range(1, 77)]) # _Michael S. Branicky_, Jan 21 2023
%Y Cf. A018800 (an upper bound), A060386, A062584 (also an upper bound).
%Y Cf. also A068165.
%K base,easy,nonn
%O 1,1
%A _Amarnath Murthy_, Feb 25 2002
%E Corrected by _Ray Chandler_, Oct 11 2003
%E Haskell code and b-file added by _Allan C. Wechsler_, Nov 13 2014
|
