A068695 -id:A068695 - cp's OEIS frontend

A018800 Smallest prime that begins with n.

11, 2, 3, 41, 5, 61, 7, 83, 97, 101, 11, 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, 41, 421, 43, 443, 457, 461, 47, 487, 491, 503, 5101, 521, 53, 541, 557, 563, 571, 587, 59

Offset: 1

David W. Wilson

Conjecture: If a(n) = (n concatenated with k) then k < n. - Amarnath Murthy, May 01 2002

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

T. D. Noe, Table of n, a(n) for n = 1..1000 (first 100 terms from Paolo P. Lava)
J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), pp. 64-94.
Index entries for primes involving decimal expansion of n

Cf. A030665, A068164, A068695, A062584, A088781, A085608.
A164022 is the base-2 analog.
Cf. also A258337.
Row n=1 of A262369.

import Data.List (isPrefixOf, find); import Data.Maybe (fromJust)
a018800 n = read $ fromJust $
            find (show n `isPrefixOf`) $ map show a000040_list :: Int
-- Reinhard Zumkeller, Jul 01 2015

f:= proc(n) local x0, d,r,y;
   if isprime(n) then return(n) fi;
   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

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

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

from sympy import isprime
def a(n):
    if isprime(n): return n
    pow10 = 10
    while True:
        t, maxt = n * pow10 + 1, (n+1) * pow10
        while t < maxt:
            if isprime(t): return t
            t += 2
        pow10 *= 10
print([a(n) for n in range(1, 60)]) # Michael S. Branicky, Nov 02 2021

a(n) = prime(A085608(n)). - Michel Marcus, Oct 19 2013

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

A091089 Numbers which form a prime by appending a 3-digit odd number and form no primes by appending any 1- or 2-digit odd number not beginning with 0.

Original entry on oeis.org

16557, 16718, 26378, 35921, 46524, 46867, 50018, 55187, 58374, 58452, 60850, 63714, 68771, 71299, 78035, 78269, 81661, 84213, 89052, 90157, 95490, 97080, 102892, 105690, 108682, 115558, 115994, 116138, 116305, 121097, 128192, 131194

Offset: 1

Chuck Seggelin, Dec 18 2003

Many numbers become prime by appending a one-digit odd number. Some numbers (such as 20, 32, 51, etc.) require a 2-digit odd number (A032352 has these). In the first 100000 values of n there are only 22 that require a 3-digit odd number.

			a(1)=16557 because 16557 is first number which requires a 3-digit odd number be appended to it to form a prime. 165571, 165573, 165575, ..., 165579, 1655711, 1655713, ..., 1655799 are all nonprime numbers. 16557103 is the first prime formed by appending odd numbers to 16657.
a(2) = 16718 because 16718111 is the first prime formed by appending odd numbers to 16718.

Robert Price, Table of n, a(n) for n = 1..23419
Index entries for primes involving decimal expansion of n

Cf. A032352 (a(n) requires at least a 2-digit odd number), A068695 (minimum odd number that must be appended to n to form a prime).

Definition edited by N. J. A. Sloane, Nov 08 2020

A228323 a(1)=1; thereafter a(n) is the smallest number m not yet in the sequence such that at least one of the concatenations a(n-1)||m or m||a(n-1) is prime.

Original entry on oeis.org

1, 3, 2, 9, 5, 21, 4, 7, 6, 13, 10, 19, 16, 27, 8, 11, 15, 23, 12, 17, 20, 29, 14, 33, 26, 47, 18, 31, 25, 39, 22, 37, 24, 41, 30, 49, 34, 57, 28, 43, 36, 59, 32, 51, 38, 53, 42, 61, 45, 67, 58, 69, 55, 63, 44, 81, 35, 71, 48, 77, 50, 87, 62, 99, 40, 73, 46

Offset: 1

N. J. A. Sloane, Aug 20 2013

Does every number appear in the sequence?
If a(n) is coprime to 10, then a(n+1) exists by Dirichlet's theorem. - Eric M. Schmidt, Aug 20 2013 [In more detail: let a(n) have d digits, and consider the arithmetic progression k*10^d + a(n), and apply Dirichlet's theorem. This gives a number k such that the concatenation k||a(n) is prime. N. J. A. Sloane, Nov 08 2020]
The argument in A068695 shows that a(n) always exists. - N. J. A. Sloane, Nov 11 2020

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Eric Angelini, Primes by concatenation, Posting to the Sequence Fans Mailing List, Aug 14 2013.
Michael De Vlieger, Labeled log-log scatterplot of a(n) n = 1..2^14, showing m coprime to 10 in red, otherwise dark blue.
Index entries for primes involving decimal expansion of n

See A228324 for the primes that arise.

Cf. A069695, A228325.

f[s_] := Block[{k = 2, idj = IntegerDigits@ s[[-1]]}, While[idk = IntegerDigits@ k; MemberQ[s, k] || ( !PrimeQ@ FromDigits@ Join[idj, idk] && !PrimeQ@ FromDigits@ Join[idk, idj]), k++]; Append[s, k]]; Nest[f, {1}, 66] (* Robert G. Wilson v, Aug 20 2013 *)

from sympy import isprime
from itertools import islice
def c(s, t): return isprime(int(s+t)) or isprime(int(t+s))
def agen():
    aset, k, mink = set(), 1, 2
    while True:
        an = k; aset.add(an); yield an; s, k = str(an), mink
        while k in aset or not c(s, str(k)): k += 1
        while mink in aset: mink += 1
print(list(islice(agen(), 56))) # Michael S. Branicky, Oct 17 2022

More terms from Alois P. Heinz, Aug 20 2013

A228325 a(n) is the smallest number m>n such that the concatenation nm is prime.

Original entry on oeis.org

3, 3, 7, 7, 9, 7, 9, 9, 11, 13, 17, 13, 19, 23, 23, 19, 21, 23, 31, 27, 29, 37, 33, 37, 31, 33, 29, 33, 39, 37, 37, 51, 43, 49, 39, 37, 39, 47, 43, 49, 53, 43, 49, 47, 47, 49, 51, 61, 51, 51, 53, 61, 81, 71, 57, 57, 79, 61, 81, 67, 63, 63, 67, 69, 69, 73, 79

Offset: 1

N. J. A. Sloane, Aug 20 2013

Max Alekseyev (see link in A068695) shows that a(n) always exists. - N. J. A. Sloane, Nov 13 2020

Suggested by the existence question in A228323.

			12 is not prime but 13 is, so a(1)=3.
23 is prime so a(2)=3.
34, 35, 36 are not prime but 37 is, so a(3)=7.

Cf. A228323, A068695.

smc[n_]:=Module[{m=n+1},If[OddQ[n],m++];While[!PrimeQ[n*10^IntegerLength[ m]+ m],m=m+2];m]; Array[smc,70] (* Harvey P. Dale, Apr 30 2016 *)

from sympy import isprime
from itertools import count
def a(n): return next(k for k in count(n+1) if isprime(int(str(n)+str(k))))
print([a(n) for n in range(1, 68)]) # Michael S. Branicky, Oct 18 2022

A336893 Lexicographically earliest infinite sequence of distinct positive terms such that the sum of digits of the first n terms is coprime to their concatenation.

Original entry on oeis.org

1, 3, 7, 2, 4, 5, 9, 6, 13, 8, 19, 11, 15, 21, 10, 17, 22, 23, 12, 24, 25, 14, 27, 16, 20, 28, 26, 31, 29, 18, 33, 37, 35, 39, 40, 41, 34, 42, 44, 43, 32, 45, 30, 46, 47, 36, 49, 38, 48, 51, 55, 53, 61, 50, 57, 60, 63, 52, 59, 64, 62, 66, 67, 54, 65, 58, 68, 69

Offset: 1

David James Sycamore and Michael De Vlieger, Aug 07 2020

Conjecture: A permutation of the positive integers.
Comment from N. J. A. Sloane, Aug 15 2020: Is there a proof that this is well-defined, i.e. that the sequence exists?  If so, the condition that a(1)=1 can be omitted from the definition.
Yes, this sequence is well defined: an upper limit for a(n+1) is given by N = concatenate(M, K) with M = max{ a(k); k <= n } and K = A068695(concatenate(a(1), ..., a(n), M)). This N is distinct from (since by construction larger than) all preceding terms, it will yield a prime number for the concatenation, certainly larger than its digit sum, so satisfies all required conditions. [This proof resulted from ideas from several OEIS editors and a new proof that A068695 is always well defined, see there.] - M. F. Hasler, Nov 09 2020

			Since a(1)=1, a(2) cannot be 2 because 1+2=3 and 3|12. However, 1+3=4 and GCD(13,4)=1, so a(2)=3.

G. H. Hardy and E. M. Wright. An Introduction to the Theory of Numbers, Oxford University Press,1945,Chapter II.
G.A. Jones and J. Mary Jones, Elementary Number Theory, London: Springer-Verlag, 2005, Chapter 2.

Michael De Vlieger, Table of n, a(n) for n = 1..10000
Michael De Vlieger, Plot of 1024 terms and 3000 terms.
Michael De Vlieger, Plot of a(n) - n for 1 <= n <= 3000.

Cf. A068695, A083754, A045572

#Code by Carl Love; (Mapleprimes)
Seq1 := proc(N::posint)
local
  S:=Array(1 .. 1, [1]),
SD:=1,
C:=1,
  Used := table([1= ()]),
  k, j, C1, SD1;
  for k from 2 to N do
      for j from 2 do
          if not assigned(Used[j]) then
             C1 := Scale10(C, length(j))+j;
             SD1 := SD+`+`(convert(j, base, 10)[]);
             if igcd(C1, SD1) = 1 then
                 C := C1; SD := SD1; Used[j] :=() ; S(k) := j;
                 break
             end if
         end if
       end do
     end do;
    seq(x,x=S)
  end proc:
  Seq1(200);

Nest[Append[#, Block[{k = 2, d = Map[IntegerDigits, #]}, While[Nand[FreeQ[#, k], GCD[FromDigits[#], Total[#]] &@ Flatten@ Append[d, IntegerDigits[k]] == 1], k++]; k]] &, {1}, 100]

A343717 a(n) is the smallest number that yields a prime when appended to n!.

Original entry on oeis.org

1, 1, 3, 1, 1, 1, 7, 11, 29, 17, 43, 29, 13, 47, 19, 73, 37, 19, 41, 103, 41, 31, 43, 1, 113, 31, 37, 59, 41, 53, 41, 47, 1, 41, 149, 37, 53, 73, 337, 1, 103, 151, 293, 47, 107, 509, 127, 71, 167, 197, 167, 149, 67, 163, 139, 251, 59, 107, 241, 331, 269, 1, 149

Offset: 0

Jon E. Schoenfield, May 17 2021

Appending to n! any number k <= n yields a multiple of k; that multiple cannot be prime except at k=1, so, for every n, a(n)=1 or a(n) > n.
a(n) = 1 iff n = 0 or n is in A024912.
See A068695 for a proof that a(n) always exists. - Felix Fröhlich, May 18 2021
If a(n) is composite, then a(n) > 2n. - Michael S. Branicky, May 18 2021

			n=1: 1! = 1; appending a 1 yields 11, a prime, so a(1)=1.
n=2: 2! = 2; appending a 1 yields 21 = 3*7, and appending a 2 yields 22 = 2*11, but appending a 3 yields 23 (a prime), so a(2)=3.
n=19: 19! = 121645100408832000; appending any number < 103 yields a composite, but 121645100408832000103 is a prime, so a(19)=103.

Lucas A. Brown, Table of n, a(n) for n = 0..2630 (terms 0..1000 from Michael S. Branicky).
Michael S. Branicky, Python program for b-file and A343718, A343719

Cf. A000040, A000142, A024912, A033932, A068695, A095194, A343718, A343719.

a:= proc(n) option remember; local k, t; t:= n!;
      for k while not isprime(parse(cat(t, k))) do od; k
    end:
seq(a(n), n=0..62);  # Alois P. Heinz, May 17 2021

Array[Block[{m = #!, k = 0}, While[! PrimeQ[10^If[k == 0, 1, IntegerLength[k]]*m + k], k++]; k] &, 62] (* Michael De Vlieger, May 17 2021 *)
snp[n_]:=Module[{nf=n!,c=1},While[!PrimeQ[nf*10^IntegerLength[c]+c],c++];c]; Array[snp,70,0] (* Harvey P. Dale, Oct 17 2024 *)

for(n=0,62,my(f=digits(n!));forstep(k=1,oo,2,my(p=fromdigits(concat(f,digits(k))));if(ispseudoprime(p),print1(k,", ");break))) \\ Hugo Pfoertner, May 18 2021

# see link for faster program producing b-file
from sympy import factorial, isprime
def a(n):
  start = str(factorial(n))
  end = 1
  while not isprime(int(start + str(end))): end += 2
  return end
print([a(n) for n in range(63)]) # Michael S. Branicky, May 17 2021

a(n) = A068695(n!) = A068695(A000142(n)).

A091088 a(n) is the minimum odd number that must be appended to n to form a prime.

Original entry on oeis.org

3, 1, 3, 1, 1, 3, 1, 1, 3, 7, 1, 3, 7, 1, 9, 1, 3, 3, 1, 1, 11, 1, 3, 3, 1, 1, 3, 1, 1, 3, 7, 1, 17, 1, 7, 3, 7, 3, 3, 7, 1, 9, 1, 1, 3, 7, 1, 9, 7, 1, 3, 13, 1, 23, 1, 7, 3, 1, 7, 3, 1, 3, 11, 1, 1, 3, 1, 3, 3, 1, 1, 9, 7, 3, 3, 1, 1, 3, 7, 7, 9, 1, 1, 9, 19, 3, 3, 7, 1, 23, 7, 1, 9, 7, 1, 3, 7, 1, 3, 1, 9, 3

Offset: 0

Chuck Seggelin, Dec 18 2003

This is really a duplicate of A068695. See that entry for existence proof. - N. J. A. Sloane, Nov 07 2020
Note that of course a(n) is not allowed to begin with 0.
Many numbers become prime by appending a one-digit odd number. Some numbers (such as 20, 32, 51, etc.) require a 2 digit odd number (A032352 has these). In the first 100,000 values of n there are only 22 that require a 3 digit odd number (A091089). There probably are some values that require odd numbers of 4 or more digits, but these are likely to be very large.

			a(0)=3 because 3 is the minimum odd number which when appended to 0 forms a prime (03 = 3 = prime).
a(20)=11 because 11 is the minimum odd number which when appended to 20 forms a prime (201, 203, 205, 207, 209 are all nonprime, 2011 is prime).

Essentially the same as A068695, which is the main entry for this sequence.

Cf. A032352 (a(n) requires at least a 2 digit odd number), A091089 (a(n) requires at least a 3 digit odd number).

Table[Block[{k = 1}, While[! PrimeQ@ FromDigits[IntegerDigits[n] ~Join~ IntegerDigits[k]], k += 2]; k], {n, 0, 101}] (* Michael De Vlieger, Nov 24 2017 *)

a(n) = forstep(x=1, +oo, 2, if(isprime(eval(concat(Str(n), x))), return(x))) \\ Iain Fox, Nov 23 2017

A338366 a(n) = smallest positive number k with all digits equal such that the concatenation k||n||k is prime, or -1 if no such k exists.

Original entry on oeis.org

1, 3, 7, 1, 11, 1, 7777, 3, 1, 1, 9, -1, 7, 33, 99, 1, 3, 1, 1, 9, 1, 11, -1, 1, 7, 3, 7777777777, 1111, 111, 1, 1, 3, 1, -1, 3, 33, 1, 3, 1, 77777777777777, 111, 3, 1111111111111111111111111111111111111111, 3, -1, 1, 3, 1, 1, 999, 7, 1, 11, 1, 7, -1, 33, 1, 3, 3, 1, 3, 1

Offset: 0

N. J. A. Sloane, Nov 08 2020

See A090287 for more information.
From Robert Price, Sep 20 2023: (Start)
For a(366), k is a string of 8441 1's.
The sequence then continues: 77, 1, 1, 3, 1, 1, 9, 7777777, 1, 11, 3, 1, 11, 9, 77, 11111, 1, 1, 33333, 3, 7, 9, 3, 1, 77, 1, 1, 9, 7777777777 until a(396) where k is a sequence of 269 1's.
The sequence then continues: 9, 777, 11, 9, 1, 7, 3, 7, 1, 11, 1, 1, 9, 9, 1111, 3, 999, 77777, 99, 7, 7, 3, 7, -1, 3, 1, 11, 77, 1, 77, 3, 1, 7, 3, 3, 1, 111111, 1, 7, 99, 7, 1111, 9, 1, 1, 11, 1, 7777777, 11, 1, 1111, 3, 1111, 7, 3, 7, 11, 3, 1, 1, 111, 3, 1, 3, 3, 1, 33, 9, 11, 33, 3, 7, 3, 3, 7, 99, 1, 1, 11, 3, 1, 9, 7, 77, 9, 1, 1, 3, 1, 7777, 33, 3, 1, 33, 3, 77, 77, 9, 1, 3, 33, 11111, 9, 9. (End)

			a(3) = 1 because 131 is prime.
a(4) = 11 because 11411 is prime, and all of 141, 242, 343, ..., 949 are composite.

Robert Price, Table of n, a(n) for n = 0..365
Index entries for primes involving decimal expansion of n

Cf. A090287.

Related sequences: A010785, A068695, A091088, A228323, A228325, A336893, A338712 (see also the Index link above).

More terms from Alois P. Heinz, Nov 08 2020

A090920 Primes of the form n followed by the least k == 1 (mod n).

Original entry on oeis.org

11, 23, 31, 41, 521, 61, 71, 89, 919, 101, 1123, 1213, 131, 1429, 151, 1697, 17137, 181, 191, 2081, 211, 2267, 2347, 241, 251, 26183, 271, 281, 29581, 3061, 311, 32257, 331, 3469, 3571, 3637, 37223, 3877, 39157, 401, 41411, 421, 431, 44221, 4591, 461, 47189

Offset: 1

Amarnath Murthy, Dec 16 2003

Conjecture: For n > 1, if a(n) = n concatenated with k then k < n^2.

			a(5) = 521, as 51,56,511 and 516 are all composite.

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

Cf. A068695.

f:= proc(n) local k,p;
   for k from 1 by n do
      p:= n*10^(1+ilog10(k))+k;
      if isprime(p) then return p fi
   od
end proc:
map(f, [$1..100]); # Robert Israel, Jan 13 2017

a(n)=my(t); forstep(k=1,oo,n, if(isprime(t=10^#digits(k)*n+k), return(t))) \\ Charles R Greathouse IV, Jan 13 2017

More terms from David Wasserman, Feb 14 2006

cp's OEIS Frontend

A018800 Smallest prime that begins with n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A030665 Smallest nontrivial extension of n which is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Extensions

A091089 Numbers which form a prime by appending a 3-digit odd number and form no primes by appending any 1- or 2-digit odd number not beginning with 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A228323 a(1)=1; thereafter a(n) is the smallest number m not yet in the sequence such that at least one of the concatenations a(n-1)||m or m||a(n-1) is prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Extensions

A228325 a(n) is the smallest number m>n such that the concatenation nm is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

A336893 Lexicographically earliest infinite sequence of distinct positive terms such that the sum of digits of the first n terms is coprime to their concatenation.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

A343717 a(n) is the smallest number that yields a prime when appended to n!.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs