A018800 -id:A018800 - 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

A262369 A(n,k) is the n-th prime whose decimal expansion begins with the decimal expansion of k; square array A(n,k), n>=1, k>=1, read by antidiagonals.

Original entry on oeis.org

11, 2, 13, 3, 23, 17, 41, 31, 29, 19, 5, 43, 37, 211, 101, 61, 53, 47, 307, 223, 103, 7, 67, 59, 401, 311, 227, 107, 83, 71, 601, 503, 409, 313, 229, 109, 97, 89, 73, 607, 509, 419, 317, 233, 113, 101, 907, 809, 79, 613, 521, 421, 331, 239, 127

Offset: 1

Alois P. Heinz, Sep 20 2015

			Square array A(n,k) begins:
:  11,   2,   3,  41,   5,  61,   7,  83, ...
:  13,  23,  31,  43,  53,  67,  71,  89, ...
:  17,  29,  37,  47,  59, 601,  73, 809, ...
:  19, 211, 307, 401, 503, 607,  79, 811, ...
: 101, 223, 311, 409, 509, 613, 701, 821, ...
: 103, 227, 313, 419, 521, 617, 709, 823, ...
: 107, 229, 317, 421, 523, 619, 719, 827, ...
: 109, 233, 331, 431, 541, 631, 727, 829, ...

Alois P. Heinz, Antidiagonals n = 1..200, flattened
Index entries for primes involving decimal expansion of n

Columns k=1-9 give: A045707, A045708, A045709, A045710, A045711, A045712, A045713, A045714, A045715.
Row n=1 gives A018800.
Main diagonal gives A077345.
Cf. A077344, A262365.

u:= (h, t)-> select(isprime, [seq(h*10^t+k, k=0..10^t-1)]):
A:= proc(n, k) local l, p;
      l:= proc() [] end; p:= proc() -1 end;
      while nops(l(k))

u[h_, t_] := Select[Table[h*10^t + k, {k, 0, 10^t - 1}], PrimeQ];
A[n_, k_] := Module[{l, p}, l[] = {}; p[] = -1; While[Length[l[k]] < n, p[k] = p[k]+1; l[k] = Join[l[k], u[k, p[k]]]]; l[k][[n]]];
Table[Table[A[n, 1+d-n], {n, 1, d}], {d, 1, 12}] // Flatten (* Jean-François Alcover, Dec 06 2019, from Maple *)

A030665 Smallest nontrivial extension of n which is prime.

Original entry on oeis.org

11, 23, 31, 41, 53, 61, 71, 83, 97, 101, 113, 127, 131, 149, 151, 163, 173, 181, 191, 2003, 211, 223, 233, 241, 251, 263, 271, 281, 293, 307, 311, 3203, 331, 347, 353, 367, 373, 383, 397, 401, 419, 421, 431, 443, 457, 461, 479, 487, 491, 503, 5101

Offset: 1

Patrick De Geest

The argument in A069695 shows that a(n) always exists. - N. J. A. Sloane, Nov 11 2020

			For n = 1, we could append 1, 3, 7, 9, 01, etc., to make a prime, but 1 gives the smallest of these, 11, so a(1) = 11.
For n = 2, although 2 is already prime, the definition requires an appending at least one digit. 1 doesn't work because 21 = 3 * 7, but 3 does because 23 is prime. Hence a(2) = 23.

Chai Wah Wu, Table of n, a(n) for n = 1..10000 [T. D. Noe computed the first 1000 terms]
Chai Wah Wu, On a conjecture regarding primality of numbers constructed from prepending and appending identical digits, arXiv:1503.08883 [math.NT], 2015.
Index entries for primes involving decimal expansion of n

Cf. A018800, A068695, A077501.

f:= proc(n) local x0, d, r, y;
   for d from 1 do
     x0:= n*10^d;
     for r from 1 to 10^d-1 by 2 do
       if isprime(x0+r) then
          return(x0+r)
       fi
     od
   od
end proc:
seq(f(n), n=1..100); # Robert Israel, Dec 23 2014

A030665[n_] := Module[{d = 10, nd = 10 * n}, While[True, x = NextPrime[nd]; If[x < nd + d, Return[x]]; d *= 10; nd *= 10]]; Array[A030665, 100] (* Jean-François Alcover, Oct 19 2016, translated from Chai Wah Wu's Python code *)

apply( {A030665(n)=my(p,L); until(n+10^L++>p=nextprime(n), n*=10);p}, [1..55]) \\ M. F. Hasler, Jan 27 2025

from sympy import nextprime
def A030665(n):
    d, nd = 10, 10*n
    while True:
        x = nextprime(nd)
        if x < nd+d:
            return int(x)
        d *= 10
        nd *= 10 # Chai Wah Wu, May 24 2016

Corrected by Ray Chandler, Aug 11 2003

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

A164022 a(n) = the smallest prime that, when written in binary, starts with the substring of n in binary.

Original entry on oeis.org

2, 2, 3, 17, 5, 13, 7, 17, 19, 41, 11, 97, 13, 29, 31, 67, 17, 37, 19, 41, 43, 89, 23, 97, 101, 53, 109, 113, 29, 61, 31, 131, 67, 137, 71, 73, 37, 307, 79, 163, 41, 337, 43, 89, 181, 373, 47, 97, 197, 101, 103, 211, 53, 109, 223, 113, 229, 233, 59, 241, 61, 251, 127, 257

Offset: 1

Leroy Quet, Aug 08 2009

The argument used to prove that A018800(n) always exists applies here also. - N. J. A. Sloane, Nov 14 2014

			4 in binary is 100. Looking at the binary numbers that begin with 100: 100 = 4 in decimal is composite; 1000 = 8 in decimal is composite; 1001 = 9 in decimal is composite; 10000 = 16 in decimal is composite. But 10001 = 17 in decimal is prime. So a(4) = 17.

Alois P. Heinz, Table of n, a(n) for n = 1..20000
Index entries for primes involving decimal expansion of n

A018800 is the base-10 analog.

Row n=1 of A262365. Cf. A108234 (number of new bits), A208241 (proper substring).

A164022 := proc(n) dgs2 := convert(n,base,2) ; ldgs := nops(dgs2) ; for i from 1 do p := ithprime(i) ; if p >= n then pdgs := convert(p,base,2) ; if [op(nops(pdgs)+1-ldgs.. nops(pdgs),pdgs)] = dgs2 then RETURN( p) ; fi; fi; od: end: seq(A164022(n),n=1..120) ; # R. J. Mathar, Sep 13 2009

With[{s = Map[IntegerDigits[#, 2] &, Prime@ Range[10^4]]}, Table[Block[{d = IntegerDigits[n, 2]}, FromDigits[#, 2] &@ SelectFirst[s, Take[#, UpTo@ Length@ d] == d &]], {n, 64}]] (* Michael De Vlieger, Sep 23 2017 *)

Corrected terms a(1) and a(2) (with help from Ray Chandler) Leroy Quet, Aug 16 2009

Extended by R. J. Mathar, Sep 13 2009

A258337 Smallest prime starting with n that does not appear earlier.

Original entry on oeis.org

11, 2, 3, 41, 5, 61, 7, 83, 97, 101, 113, 127, 13, 149, 151, 163, 17, 181, 19, 2003, 211, 223, 23, 241, 251, 263, 271, 281, 29, 307, 31, 3203, 331, 347, 353, 367, 37, 383, 397, 401, 419, 421, 43, 443, 457, 461, 47, 487, 491, 503, 5101, 521, 53, 541, 557, 563, 571, 587, 59, 601, 613, 6203, 631, 641, 653, 661, 67, 683, 691, 701

Offset: 1

Vladimir Shevelev, May 27 2015

According to a comment in A018800, every term exists. So the sequence is a permutation of the primes. Indeed, every prime p appears in the sequence either as the p-th term or earlier.

Peter J. C. Moses, Table of n, a(n) for n = 1..5000
Index entries for primes involving decimal expansion of n

Cf. A000040, A018800, A030665, A062584, A258190, A258339.

import Data.List (isPrefixOf, delete)
a258337 n = a258337_list !! (n-1)
a258337_list = f 1 $ map show a000040_list where
   f x pss = g pss where
     g (qs:qss) = if show x `isPrefixOf` qs
                     then (read qs :: Int) : f (x + 1) (delete qs pss)
                     else g qss
-- Reinhard Zumkeller, Jul 01 2015

N:= 100: # to get a(1) to a(N)
for n from 1 to N do
  p:= n;
  if n < 10 then
    p1:= 0
  else
    p1:= A[floor(n/10)];
  fi;
  if isprime(p) and p > p1 then
     A[n]:= p
  else
    for d from 1 while not assigned(A[n]) do
      for i from 1 to 10^d-1 do
        p:= 10^d*n+i;
        if p > p1 and isprime(p) then
           A[n]:= p;
           break
        fi;
      od
    od
  fi
od:
seq(A[i],i=1..N); # Robert Israel, Jun 29 2015

sw(m,n)=d1=digits(n);d2=digits(m);for(i=1,min(#d1,#d2),if(d1[i]!=d2[i],return(0)));1
v=[];n=1;while(n<70,k=1;while(k<10^3,p=prime(k);if(sw(p,n)&&!vecsearch(vecsort(v),p),v=concat(v,p);k=0;n++);k++));v \\ Derek Orr, Jun 13 2015

For n>=2, a(n) >= prime(n-1). The equality holds iff prime(n-1) did not already appear as a(k), k

A197816 Smallest composite number m such that m and the greatest prime divisor of m begin with n.

Original entry on oeis.org

102, 203, 36, 410, 50, 603, 70, 801, 970, 1010, 110, 1270, 130, 1490, 1510, 1630, 170, 1810, 190, 20030, 2110, 2230, 230, 2410, 2510, 2630, 2710, 2810, 290, 3070, 310, 32030, 3310, 3470, 3530, 3670, 370, 3830, 3970, 4010, 410, 4210, 430, 4430, 4570, 4610, 470

Offset: 1

Michel Lagneau, Oct 18 2011

A majority of numbers are divisible by 10.

The case m prime gives A062584 (First occurrence of n in the decimal representation of primes).

			a(6) = 603 = 3^2*67 => 603 and 67 start with 6.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A018800, A062584.

with(numtheory): for n from 1 to 47 do: l1:=length(n):i:=0:for m from 2 to 100000 while(i=0) do: x:=factorset(m):k:=nops(x):y:=x[k]: l2:=length(m):x1:=floor(m/(10^(l2-l1))): l3:=length(y):x2:=floor(y/(10^(l3-l1))):if x1=n and x2=n and l2>=l1 and l3 >=l1 and type(m,prime)=false then i:=1: printf(`%d, `,m):else fi :od:od:
# Alternative:
f:= proc(n) local d,k,p;
  for d from 1 do
    for k from 10^d*n to 10^d*(n+1)-1 do
       if not isprime(k) then
         p:= max(numtheory:-factorset(k));
         if p >= n and floor(p/10^(length(p)-length(n))) = n then return k fi
       fi od od
end proc:
map(f, [$1..100]); # Robert Israel, Jun 04 2018

a(n) = 10*A018800(n) for n >= 9. - Robert Israel, Jun 04 2018

A374899 a(n) is the least semiprime that starts with n.

Original entry on oeis.org

10, 21, 33, 4, 51, 6, 74, 82, 9, 10, 111, 121, 133, 14, 15, 161, 177, 183, 194, 201, 21, 22, 235, 247, 25, 26, 274, 287, 291, 301, 314, 321, 33, 34, 35, 361, 371, 38, 39, 403, 411, 422, 437, 445, 451, 46, 471, 481, 49, 501, 51, 526, 533, 542, 55, 562, 57, 58, 591, 6001, 611, 62, 633, 649, 65, 662

Offset: 1

Robert Israel, Jul 22 2024

			a(5) = 51 because 51 = 3 * 17 is a semiprime that starts with 5, and is the least such semiprime.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A001358, A018800, A374897.

f:= proc(n) local d,x;
  if numtheory:-bigomega(n)=2 then return n fi;
  for d from 1 do
    for x from n*10^d to (n+1)*10^d-1 do
      if numtheory:-bigomega(x)=2 then return x fi
  od od
end proc:
map(f, [$1..100]);

A085608 Index of the smallest prime starting with n.

Original entry on oeis.org

5, 1, 2, 13, 3, 18, 4, 23, 25, 26, 5, 31, 6, 35, 36, 38, 7, 42, 8, 304, 47, 48, 9, 53, 54, 56, 58, 60, 10, 63, 11, 453, 67, 69, 71, 73, 12, 76, 78, 79, 13, 82, 14, 86, 88, 89, 15, 93, 94, 96, 682, 98, 16, 100, 102, 103, 105, 107, 17, 110, 18, 807

Offset: 1

Zak Seidov, Jul 07 2003

			a(4)=13 because prime[13]=41 is the smallest prime starting with 4.

Cf. A000720, A018800.

a(n) = PrimePi(A018800(n)). - Michel Marcus, Oct 19 2013

A089754 Smallest prime ending (least significant side) in n if possible else beginning in n.

Original entry on oeis.org

11, 2, 3, 41, 5, 61, 7, 83, 19, 101, 11, 127, 13, 149, 151, 163, 17, 181, 19, 2003, 421, 223, 23, 241, 251, 263, 127, 281, 29, 307, 31, 3203, 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, 587, 59, 601, 61, 6203, 163

Offset: 1

Amarnath Murthy, Nov 22 2003

Cf. A018800, A062584, A068164.

read("transforms)"):
nleadzero := proc(n,dgs)
    local ndgs ;
    if n = 0 then
        ndgs := 0 ;
    else
        ndgs := ilog10(n)+1 ;
    end if;
    [op(convert(n,base,10)),seq(0,i=1..dgs-ndgs)]
end proc:
digcatL2 := proc(L1,L2)
    digcatL([op(L1),op(L2)]) ;
end proc:
A089754 := proc(n)
    local prep,a,dgs ;
    if isprime(n) then
        n;
    elif modp(n,2) = 0 or modp(n,5) = 0 then
        ndgs := convert(n,base,10) ;
        for dgs from 1 do
            for prep from 0 to 10^dgs-1 do
                a := digcatL2(ListTools[Reverse](ndgs),ListTools[Reverse](nleadzero(prep,dgs))) ;
                if isprime(a) then
                    return a;
                end if;
            end do:
        end do:
    else
        for prep from 1 do
            a := digcat2(prep,n) ;
            if isprime(a) then
                return a;
            end if;
        end do:
    end if;
end proc: # R. J. Mathar, Sep 18 2015

Corrected by R. J. Mathar, Sep 18 2015

Showing 1-10 of 16 results. Next

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

PARI

Python

Formula

Extensions

A262369 A(n,k) is the n-th prime whose decimal expansion begins with the decimal expansion of k; square array A(n,k), n>=1, k>=1, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A030665 Smallest nontrivial extension of n which is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Python

Extensions

A164022 a(n) = the smallest prime that, when written in binary, starts with the substring of n in binary.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A258337 Smallest prime starting with n that does not appear earlier.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

PARI

Formula

A197816 Smallest composite number m such that m and the greatest prime divisor of m begin with n.

Views