A035244 Smallest number with exactly n prime substrings.

1, 2, 13, 23, 113, 137, 373, 1137, 1733, 1373, 11317, 11373, 13733, 31373, 113173, 131373, 137337, 337397, 1113173, 1137337, 1373373, 2337397, 3733797, 11373137, 11373379, 13733797, 37337397, 111373379, 123733739

Offset: 0

Author

Erich Friedman

Keywords

• base
• easy
• nonn

Comments

No leading 0's allowed in substrings.

The sequence is well-defined in that for each n the set of numbers with n prime substrings is not empty. Proof by induction: '1' has 0 prime substrings and '2' has 1 prime substring. Let m be a number with n prime substrings. Then 10m+2 is a number with n+1 prime substrings (since m and 10m have identical prime substrings, and '2' is one additional prime substring, but 10m+2 cannot be prime). - Hieronymus Fischer, Aug 26 2012

Examples

			a(4)=113 since 3, 11, 13 and 113 are prime and no smaller number works.
		

Links

• Hieronymus Fischer, Table of n, a(n) for n = 0..40

Crossrefs

Cf. A035232, A079397.

Programs

Mathematica

f[n_] := Block[{s = IntegerDigits[n], c = 0, d = {}}, l = Length[s]; t = Flatten[ Table[ Take[s, {i, j}], {i, 1, l}, {j, i, l}], 1]; k = l(l + 1)/2; While[k > 0, If[ t[[k]][[1]] != 0, d = Append[d, FromDigits[ t[[k]] ]]]; k-- ]; Count[ PrimeQ[d], True]]; a = Table[0, {25}]; Do[ b = f[n]; If[ a[[b + 1]] == 0, a[[b + 1]] = n], {n, 1, 15000000}]; a

Formula

a(n) > 10^floor((sqrt(8*n-7)-1)/2) for n > 0. - Hieronymus Fischer, Jun 25 2012

Min_{k>=n} a(k) <= A079397(n-1), n > 0. - Hieronymus Fischer, Aug 26 2012

a(n+1) <= 10*a(n) + 2. - Hieronymus Fischer, Aug 26 2012

Extensions

Edited by Robert G. Wilson v, Feb 25 2003

a(25)-a(40) from Hieronymus Fischer, Jun 25 2012 and Aug 25 2012