A035244 - OEIS

%I #31 Oct 02 2020 18:43:47

%S 1,2,13,23,113,137,373,1137,1733,1373,11317,11373,13733,31373,113173,

%T 131373,137337,337397,1113173,1137337,1373373,2337397,3733797,

%U 11373137,11373379,13733797,37337397,111373379,123733739

%N Smallest number with exactly n prime substrings.

%C No leading 0's allowed in substrings.

%C 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

%H Hieronymus Fischer, <a href="/A035244/b035244.txt">Table of n, a(n) for n = 0..40</a>

%F a(n) > 10^floor((sqrt(8*n-7)-1)/2) for n > 0. - _Hieronymus Fischer_, Jun 25 2012

%F Min_{k>=n} a(k) <= A079397(n-1), n > 0. - _Hieronymus Fischer_, Aug 26 2012

%F a(n+1) <= 10*a(n) + 2. - _Hieronymus Fischer_, Aug 26 2012

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

%t 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

%Y Cf. A035232, A079397.

%K base,easy,nonn

%O 0,2

%A _Erich Friedman_

%E Edited by _Robert G. Wilson v_, Feb 25 2003

%E a(25)-a(40) from _Hieronymus Fischer_, Jun 25 2012 and Aug 25 2012