A060386 -id:A060386 - cp's OEIS frontend

A062584 a(n) is the smallest prime whose digits include the digits of n as a substring.

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

Offset: 0

Jason Earls, Jul 03 2001

a(0) = 101 is the first term where a(n) has two more digits than n. a(665808) = 106658081 is the first term where a(n) has three more digits than n. For which n does a(n) first have four more digits than n? Is lim sup a(n)/n infinite? - Charles R Greathouse IV, Jun 23 2017

Decide how many elements you want to find. Then for every prime, check all substrings to see if they are the first to be in some n. If you've found all values a(n), then you want to stop. - David A. Corneth, Jun 24 2017

			0 first occurs in 101. 14 first occurs as a substring in 149.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Index entries for primes involving decimal expansion of n

Cf. A082058, A018800, A060386. Similar to but different from A068164. E.g., a(133) = 4133, but A068164(133) = 1033.

import Data.List (isInfixOf)
a062584 n = head [p | p <- a000040_list, show n `isInfixOf` show p]
-- Reinhard Zumkeller, Dec 29 2011

Do[k = 1; While[ StringPosition[ ToString[Prime[k]], ToString[n]] == {}, k++ ]; Print[ Prime[k]], {n, 0, 62} ]
(* Second program *)
Function[s, Table[FromDigits@ FirstCase[s, w_ /; SequenceCount[w, IntegerDigits@ n] > 0], {n, 0, 56}]]@ IntegerDigits@ Prime@ Range[10^4] (* Michael De Vlieger, Jun 24 2017 *)
With[{prs=Prime[Range[300]]},Table[SelectFirst[prs,SequenceCount[ IntegerDigits[#], IntegerDigits[ n]]>0&],{n,0,60}]] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Dec 06 2018 *)

build(root, prefixLen, suffixLen)=my(v=List(),t); for(i=10^(prefixLen-1)\1,10^prefixLen-1, t=eval(Str(i,root))*10^suffixLen; for(n=t,t+10^suffixLen-1, listput(v,n))); Vec(v)
buildLen(n,d)=my(v=[]); for(i=0,d, v=concat(v,build(n,i,d-i))); Set(v)
a(n)=if(n==0, return(101)); my(d,v); while(1, v=buildLen(n,d); for(i=1,#v, if(isprime(v[i]), return(v[i]))); d++) \\ Charles R Greathouse IV, Jun 23 2017

first(n) = my(res = vector(n), todo = n, g); forprime(p = 2, , d = digits(p); for(i=1,#d, if(d[i]!=0, g = d[i]; if(res[g]==0, res[g]=p; todo--); for(j=1,#d-i, g=10*g+d[i+j]; if(g>n,next(2)); if(res[g]==0, res[g]=p; todo--)))); if(todo==0,return(concat([101],res)))) \\ David A. Corneth, Jun 23 2017

from sympy import nextprime
def a(n):
    p, s = 2, str(n)
    while s not in str(p): p = nextprime(p)
    return p
print([a(n) for n in range(57)]) # Michael S. Branicky, Dec 02 2021

a(n) = prime(A082058(n)). - Giovanni Resta, Apr 29 2017

More terms from Lior Manor, Jul 08 2001
Corrected by Larry Reeves (larryr(AT)acm.org), Jul 10 2001
Further correction from Reinhard Zumkeller, Oct 14 2001
Name clarified by Jon E. Schoenfield, Dec 04 2021

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

Original entry on oeis.org

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

Amarnath Murthy, Feb 25 2002

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.

			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.

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

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

Cf. also A068165.

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

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

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

Corrected by Ray Chandler, Oct 11 2003

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

cp's OEIS Frontend

A062584 a(n) is the smallest prime whose digits include the digits of n as a substring.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI