login
Smallest prime that begins with n.
17

%I #65 Nov 04 2023 08:46:44

%S 11,2,3,41,5,61,7,83,97,101,11,127,13,149,151,163,17,181,19,2003,211,

%T 223,23,241,251,263,271,281,29,307,31,3203,331,347,353,367,37,383,397,

%U 401,41,421,43,443,457,461,47,487,491,503,5101,521,53,541,557,563,571,587,59

%N Smallest prime that begins with n.

%C Conjecture: If a(n) = (n concatenated with k) then k < n. - _Amarnath Murthy_, May 01 2002

%C a(n) always exists. Proof. Suppose n is L digits long, and consider the numbers between n*10^B and n*10^B+10^C, where B > C are both large compared with L. All such numbers begin with the digits of n. Using the upper and lower bounds on pi(x) from Theorem 1 of Rosser and Schoenfeld, it follows that for sufficiently large B and C, at least one of these numbers is a prime. QED - _N. J. A. Sloane_, Nov 14 2014

%H T. D. Noe, <a href="/A018800/b018800.txt">Table of n, a(n) for n = 1..1000</a> (first 100 terms from Paolo P. Lava)

%H J. Barkley Rosser and Lowell Schoenfeld, <a href="http://projecteuclid.org/euclid.ijm/1255631807">Approximate formulas for some functions of prime numbers</a>, Illinois J. Math. 6 (1962), pp. 64-94.

%H <a href="/index/Pri#piden">Index entries for primes involving decimal expansion of n</a>

%F a(n) = prime(A085608(n)). - _Michel Marcus_, Oct 19 2013

%p f:= proc(n) local x0, d,r,y;

%p if isprime(n) then return(n) fi;

%p for d from 1 do

%p x0:= n*10^d;

%p for r from 1 to 10^d-1 by 2 do

%p if isprime(x0+r) then

%p return(x0+r)

%p fi

%p od

%p od

%p end proc:

%p seq(f(n),n=1..100); # _Robert Israel_, Dec 23 2014

%t Table[Function[d, FromDigits@ SelectFirst[ IntegerDigits@ Prime@ Range[10^4], Length@ # >= Length@ d && Take[#, Length@ d] == d &]][ IntegerDigits@ n], {n, 59}] (* _Michael De Vlieger_, May 24 2016, Version 10 *)

%o (Haskell)

%o import Data.List (isPrefixOf, find); import Data.Maybe (fromJust)

%o a018800 n = read $ fromJust $

%o find (show n `isPrefixOf`) $ map show a000040_list :: Int

%o -- _Reinhard Zumkeller_, Jul 01 2015

%o (PARI) a(n{,base=10}) = for (l=0, oo, forprime (p=n*base^l, (n+1)*base^l-1, return (p))) \\ _Rémy Sigrist_, Jun 11 2017

%o (Python)

%o from sympy import isprime

%o def a(n):

%o if isprime(n): return n

%o pow10 = 10

%o while True:

%o t, maxt = n * pow10 + 1, (n+1) * pow10

%o while t < maxt:

%o if isprime(t): return t

%o t += 2

%o pow10 *= 10

%o print([a(n) for n in range(1, 60)]) # _Michael S. Branicky_, Nov 02 2021

%Y Cf. A030665, A068164, A068695, A062584, A088781, A085608.

%Y A164022 is the base-2 analog.

%Y Cf. also A258337.

%Y Row n=1 of A262369.

%K nonn,base

%O 1,1

%A _David W. Wilson_