A213321 -id:A213321 - cp's OEIS frontend

A213302 Smallest number with n nonprime substrings (Version 1: substrings with leading zeros are considered to be nonprime).

2, 1, 11, 10, 103, 101, 100, 1017, 1011, 1002, 1000, 10037, 10023, 10007, 10002, 10000, 100137, 100073, 100023, 100003, 100002, 100000, 1000313, 1000037, 1000033, 1000023, 1000003, 1000002, 1000000, 10000337, 10000223, 10000137, 10000037, 10000023, 10000013, 10000002, 10000000, 100001733

Offset: 0

Hieronymus Fischer, Aug 26 2012

The sequence is well-defined in that for each n the set of numbers with n nonprime substrings is not empty. Proof: Define m(n)=2*sum_{j=i..k} 10^j, where k=floor((sqrt(8*n+1)-1)/2), i:= n-A000217(k). For n=0,1,2,3,… the m(n) are 2, 22, 20, 222, 220, 200, 2222, 2220, 2200, 2000, 22222, 22220, ... . m(n) has k+1 digits and (k-i+1) 2’s, thus, the number of nonprime substrings of m(n) is ((k+1)*(k+2)/2)-k-1+i=(k*(k+1)/2)+i=n, which proves the statement.

The 3 versions according to A213302 - A213304 are quite different. Example: 1002 has 9 nonprime substrings in version 1 (0, 0, 00, 02, 002, 1, 10 100, 1002), in version 2 there are 6 nonprime substrings (02, 002, 1, 10, 100, 1002) and there are 4 nonprime substrings in version 3 (1, 10, 100, 1002).

			a(0)=2, since 2 is the least number with zero nonprime substrings.
a(1)=1, since 1 has 1 nonprime substrings.
a(2)=11, since 11 is the least number with 2 nonprime substrings.
a(3)=10, since 10 is the least number with 3 nonprime substrings, these are 1, 0 and 10 (‘0’ will be counted).

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

Cf. A019546, A035232, A039996, A046034, A069489, A085823, A211681, A211682, A211684, A211685.

Cf. A035244, A079307, A213300 - A213321.

a(n) >= 10^floor((sqrt(8*n-7)-1)/2) for n>0, equality holds if n is a triangular number > 0 (cf. A000217).

a(A000217(n)) = 10^(n-1), n>0.

a(A000217(n)-k) >= 10^(n-1)+k, n>0, 0<=k

a(A000217(n)-1) = 10^(n-1)+2, n>3, provided 10^(n-1)+1 is not a prime (which is proved to be true for all n-1 <= 50000 (cf. A185121) except n-1=16384 and is generally true for n-1 unequal to a power of 2).

a(A000217(n)-k) = 10^(n-1)+p, where p is the minimal number such that 10^(n-1) + p, has k prime substrings, n>0, 0<=k

Min(a(A000217(n)-k-i), 0<=i<=m) <= 10^(n-1)+p, where p is the minimal number with k prime substrings and m is the number of digits of p, and k+m

Min(a(A000217(n)-k-i), 0<=i<=A055642(A035244(k)) <= 10^(n-1)+A035244(k).

a(A000217(n)-k) <= 10^(n-1)+max(p(i), k<=i<=k+m), where p(i) is the minimal number with i prime substrings and m is the number of digits of p(i), and k+m

a(A000217(n)-k) <= 10^(n-1)+max(A035244(i), k<=i<=k+ A055642(i).

a(n) <= A213305(n).

A217102 Minimal number (in decimal representation) with n nonprime substrings in binary representation (substrings with leading zeros are considered to be nonprime).

Original entry on oeis.org

1, 2, 7, 5, 4, 11, 10, 12, 8, 22, 21, 19, 17, 16, 60, 39, 37, 34, 36, 32, 83, 71, 74, 69, 67, 66, 64, 143, 139, 141, 135, 134, 131, 130, 128, 283, 271, 269, 263, 267, 262, 261, 257, 256, 541, 539, 527, 526, 523, 533, 519, 514, 516, 512, 1055, 1053, 1047, 1067

Offset: 1

Hieronymus Fischer, Dec 12 2012

There are no numbers with zero nonprime substrings in binary representation. For all bases > 2 there is always a number (=2) with zero nonprime substrings (Cf. A217103-A217109, A213302).

If p is a number with k prime substrings and d digits (in binary representation), p even, m>=d, than b := p*2^(m-d) has m*(m+1)/2 - k nonprime substrings, and a(A000217(n)-k) <= b.

			a(1) = 1, since 1 = 1_2 is the least number with 1 nonprime substring in binary representation.
a(2) = 2, since 2 = 10_2 is the least number with 2 nonprime substrings in binary representation (0 and 1).
a(3) = 7, since 7 = 111_2 is the least number with 3 nonprime substrings in binary representation (3-times 1, the prime substrings are 2-times 11 and 111).
a(10) = 22, since 22 = 10110_2 is the least number with 10 nonprime substrings in binary representation, these are 0, 0, 1, 1, 1, 01, 011, 110, 0110 and 10110 (remember, that substrings with leading zeros are considered to be nonprime).

Hieronymus Fischer, Table of n, a(n) for n = 1..2015

Cf. A019546, A035232, A039996, A046034, A069489, A085823, A211681, A211682, A211684, A211685, A035244, A079397, A213300-A213321, A217103-A217109, A217302-A217309.

a(n) >= 2^floor((sqrt(8*n-7)-1)/2) for n>=1, equality holds if n=1 or n+1 is a triangular number (cf. A000217).
a(n) >= 2^floor((sqrt(8*n+1)-1)/2) for n>1, equality holds if n+1 is a triangular number.
a(A000217(n)-1) = 2^(n-1), n>1.
a(A000217(n)-k) >= 2^(n-1) + k-1, 1<=k<=n, n>1.
a(A000217(n)-k) = 2^(n-1) + p, where p is the minimal number >= 0 such that 2^(n-1) + p, has k prime substrings in binary representation, 1<=k<=n, n>1.

A217109 Minimal number (in decimal representation) with n nonprime substrings in base-9 representation (substrings with leading zeros are considered to be nonprime).

Original entry on oeis.org

2, 1, 12, 9, 83, 84, 81, 748, 740, 731, 729, 6653, 6581, 6563, 6564, 6561, 59222, 59069, 59068, 59051, 59052, 59049, 531614, 531569, 531464, 531460, 531452, 531443, 531441, 4784122, 4783142, 4783147, 4783070, 4782989, 4782971, 4782972, 4782969, 43048283

Offset: 0

Hieronymus Fischer, Dec 12 2012

The sequence is well-defined in that for each n the set of numbers with n nonprime substrings is not empty. Proof: Define m(n):=2*sum_{j=i..k} 9^j, where k:=floor((sqrt(8*n+1)-1)/2), i:= n-A000217(k). For n=0,1,2,3,... the m(n) in base-9 representation are 2, 22, 20, 222, 220, 200, 2222, 2220, 2200, 2000, 22222, 22220, .... m(n) has k+1 digits and (k-i+1) 2’s, thus, the number of nonprime substrings of m(n) is ((k+1)*(k+2)/2)-k-1+i = (k*(k+1)/2)+i = n, which proves the statement.

If p is a number with k prime substrings and d digits (in base-9 representation), m>=d, than b := p*9^(m-d) has m*(m+1)/2 - k nonprime substrings, and a(A000217(n)-k) <= b.

			a(0) = 2, since 2 = 2_9 is the least number with zero nonprime substrings in base-9 representation.
a(1) = 1, since 1 = 1_9 is the least number with 1 nonprime substring in base-9 representation.
a(2) = 12, since 12 = 13_9 is the least number with 2 nonprime substrings in base-9 representation (1 and 13).
a(3) = 9, since 9 = 10_9 is the least number with 3 nonprime substrings in base-9 representation (0, 1 and 10).
a(4) = 83, since 83 = 102_9 is the least number with 4 nonprime substrings in base-9 representation, these are 0, 1, 10, and 02 (remember, that substrings with leading zeros are considered to be nonprime).

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

Cf. A019546, A035232, A039996, A046034, A069489, A085823, A211681, A211682, A211684, A211685.
Cf. A035244, A079397, A213300-A213321.
Cf. A217102-A217109.
Cf. A217302-A217309.

a(n) >= 9^floor((sqrt(8*n-7)-1)/2) for n>0, equality holds if n is a triangular number (cf. A000217).
a(A000217(n)) = 9^(n-1), n>0.
a(A000217(n)-k) >= 9^(n-1) + k, 0<=k0.
a(A000217(n)-k) = 9^(n-1) + p, where p is the minimal number >= 0 such that 9^(n-1) + p, has k prime substrings in base-9 representation, 0<=k0.

A217112 Greatest number (in decimal representation) with n nonprime substrings in binary representation (substrings with leading zeros are considered to be nonprime).

Original entry on oeis.org

1, 3, 7, 6, 15, 14, 31, 29, 30, 63, 61, 62, 127, 54, 125, 126, 255, 117, 251, 254, 189, 511, 479, 509, 510, 379, 502, 1023, 1021, 1007, 1022, 958, 1018, 1014, 2047, 2045, 1791, 2046, 2042, 2027, 2037, 4091, 4095, 4063, 3069, 4094, 4090, 4085, 8159, 8187, 8191, 8189, 8127

Offset: 1

Hieronymus Fischer, Dec 20 2012

There are no numbers with zero nonprime substrings in binary representation. For all bases > 2 there is always a number (=2) with zero nonprime substrings.

The set of numbers with n nonprime substrings is finite. Proof: Evidently, each 1-digit binary number represents 1 nonprime substring. Hence, each (n+1)-digit number has at least n+1 nonprime substrings. Consequently, there is a boundary b < 2^n, such that all numbers > b have more than n nonprime substrings.

			(1) = 1, since 1 = 1_2 (binary) is the greatest number with 1 nonprime substring.
a(2) = 3 = 11_2 has 3 substrings in binary representation (1, 1 and 11), two of them are nonprime substrings (1 and 1), and 11_2 = 3 is the only prime substrings. 3 is the greatest number with 2 nonprime substrings.
a(8) = 29 = 11101_2 has 15 substrings in binary representation (0, 1, 1, 1, 1, 11, 11, 10, 01, 111, 110, 101, 1110, 1101, 11101), exactly 8 of them are nonprime substrings (0, 1, 1, 1, 1, 01, 110, 1110). There is no greater number with 8 nonprime substrings in binary representation.
a(14) = 54 = 110110_2 has 21 substrings in binary representation, only 7 of them are prime substrings (10, 10, 11, 11, 101, 1011, 1101), which implies that exactly 14 substrings must be nonprime. There is no greater number with 14 nonprime substrings in binary representation.

Hieronymus Fischer, Table of n, a(n) for n = 1..1000

Cf. A019546, A035232, A039996, A046034, A069489, A085823, A211681, A211682, A211684, A211685.
Cf. A035244, A079397, A213300 - A213321.
Cf. A217102 - A217109, A217113 - A217119.
Cf. A217302 - A217309.

a(n) >= A217102(n).
a(n) >= A217302(A000217(A070939(a(n)))-n).
Example: a(9)=30=11110_2, A000217(A070939(31))=15, hence, a(9)>=A217302(15-9)=27.
a(n) <= 2^n.
a(n) <= 2^min(6 + n/6, 20*floor((n+125)/126)).
a(n) <= 64*2^(n/6).
With m := floor(log_2(a(n))) + 1:
a(n+m+1) >= 2*a(n), if a(n) is even.
a(n+m) >= 2*a(n), if a(n) is odd.

A217119 Greatest number (in decimal representation) with n nonprime substrings in base-9 representation (substrings with leading zeros are considered to be nonprime).

Original entry on oeis.org

47, 428, 1721, 6473, 14033, 35201, 58961, 58967, 465743, 530701, 530710, 1733741, 4250788, 4723108, 4776398, 25051529, 37327196, 42450640, 42986860, 42987589, 42996409, 225463817, 382055767, 382571822, 386888308, 386888419, 387356789

Offset: 0

Hieronymus Fischer, Dec 20 2012

The sequence is well-defined in that for each n the set of numbers with n nonprime substrings is not empty and finite. Proof of existence: Define m(n):=2*sum_{j=i..k} 9^j, where k:=floor((sqrt(8n+1)-1)/2), i:= n-(k(k+1)/2). For n=0,1,2,3,... the m(n) in base-9 representation are 2, 22, 20, 222, 220, 200, 2222, 2220, 2200, 2000, 22222, 22220, .... m(n) has k+1 digits and (k-i+1) 2’s. Thus, the number of nonprime substrings of m(n) is ((k+1)(k+2)/2)-k-1+i=(k(k+1)/2)+i=n. This proves the statement of existence. Proof of finiteness: Each 3-digit base-9 number has at least 1 nonprime substring. Hence, each 3(n+1)-digit number has at least n+1 nonprime substrings. Consequently, there is a boundary b < 9^(3n+2) such that all numbers > b have more than n nonprime substrings. It follows, that the set of numbers with n nonprime substrings is finite.

			a(0) = 47, since 47 = 52_9 (base-9) is the greatest number with zero nonprime substrings in base-9 representation.
a(1) = 428 = 525_9 has 1 nonprime substring in base-9 representation (= 525_9). All the other base-9 substrings (2, 5, 5, 25, 52) are prime substrings. 525_9 is the greatest number with 1 nonprime substring.
a(2) = 1721 = 2322_9 has 10 substrings in base-9 representation, exactly 2 of them are nonprime substrings (22_9 and 23_3=8), and there is no greater number with 2 nonprime substrings in base-9 representation.
a(7) = 58967= 88788_9 has 15 substrings in base-9 representation, exactly 7 of them are nonprime substrings (4-times 8, 2-times 88, and 8788), and there is no greater number with 7 nonprime substrings in base-9 representation.

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

Cf. A019546, A035232, A039996, A046034, A069489, A085823, A211681, A211682, A211684, A211685.
Cf. A035244, A079397, A213300 - A213321.
Cf. A217102 - A217109, A217112 - A217118.
Cf. A217302 - A217309.

a(n) >= A217109(n).
a(n) >= A217309(A000217(num_digits_9(a(n)))-n), where num_digits_9(x)=floor(log_9(x))+1 is the number of digits of the base-9 representation of x.
a(n) <= 9^(n+2).
a(n) <= 9^min(n+2, 6*floor((n+7)/8)).
a(n) <= 9^((3/4)*(n + 3)).
a(n+m+1) >= 9*a(n), where m := floor(log_9(a(n))) + 1.

A213304 Smallest number with n nonprime substrings (Version 3: substrings with leading zeros are counted as nonprime if the corresponding number is not a prime).

Original entry on oeis.org

2, 1, 10, 14, 101, 104, 144, 1001, 1014, 1044, 1444, 10010, 10014, 10144, 10444, 14444, 100120, 100104, 100144, 101444, 104444, 144444, 1000144, 1001040, 1001044, 1001444, 1014444, 1044444, 1444444, 10001044, 10001444, 10010404, 10010444, 10014444, 10144444, 10444444, 14444444, 100010404, 100010444, 100014444, 100104044, 100104444, 100144444, 101444444, 104444444, 144444444

Offset: 0

Hieronymus Fischer, Aug 26 2012

The sequence is well defined since for each n >= 0 there is a number with n nonprime substrings.

Different from A213303, first difference is at a(16).

			a(0)=2, since 2 is the least number with zero nonprime substrings.
a(1)=1, since 1 has 1 nonprime substrings.
a(2)=10, since 10 is the least number with 2 nonprime substrings, these are 1 and 10 ('0' will not be counted).
a(3)=14, since 14 is the least number with 3 nonprime substrings, these are 1 and 4 and 14. 10, 11 and 12 only have 2 such substrings.

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

Cf. A019546, A035232, A039996, A046034, A069489, A085823, A211681, A211682, A211684, A211685.

Cf. A035244, A079307, A213300 - A213321.

a(m(m+1)/2) = (13*10^(m-1)-4)/9, m>0.
With b(n):=floor((sqrt(8*n-7)-1)/2):
a(n) > 10^b(n), for n>2, a(n) = 10^b(n) for n=1,2.
a(n) >= 10^b(n)+4*10^(n-1-b(n)(b(n)+1)/2)-1)/9, equality holds if n or n+1 is a triangular number > 0 (cf. A000217).
a(n) >= A213303(n).
a(n) <= A213307(n).

Showing 1-10 of 45 results. Next

The sequence is well-defined in that for each n the set of numbers with n nonprime substrings is nonempty and finite. Proof of existence: Define m(n):=2*sum_{j=i..k} 10^j, where k:=floor((sqrt(8n+1)-1)/2), i:= n - k(k+1)/2. For n=0,1,2,3,... the m(n) are 2, 22, 20, 222, 220, 200, 2222, 2220, 2200, 2000, 22222, 22220, ... . m(n) has k+1 digits and (k-i+1) 2’s. Thus the number of nonprime substrings of m(n) is ((k+1)(k+2)/2)-k-1+i=(k(k+1)/2)+i=n. This proves existence. Proof of finiteness: Each 4-digit number has at least 1 nonprime substring. Hence each 4*(n+1)-digit number has at least n+1 nonprime substrings. Consequently, there is a boundary b < 10^(4n+3) such that all numbers > b have more than n nonprime substrings. It follows that the set of numbers with n nonprime substrings is finite.
The following statements hold true:
For all n>=0 there are minimal numbers with n nonprime substrings (cf. A213302 - A213304).
For all n>=0 there are maximal numbers with n nonprime substrings (= A213300 = this sequence).
For all n>=0 there are minimal numbers with n prime substrings (cf. A035244).
The greatest number with n prime substrings does not exist. Proof: If p is a number with n prime substrings, than 10*p is a greater number with n prime substrings.
Comment from N. J. A. Sloane, Sep 01 2012: it is a surprise that any number greater than 373 has a nonprime substring!

a(n) = A002815(n) - n. - Reinhard Zumkeller, Feb 25 2012
From Hieronymus Fischer, Sep 26 2012: (Start)
Let S(n) be a string of length n, then a(n) is the number of substrings of S(n) with a prime number of characters. Example 1: "abcd" is a string of length 4; there are a(4)=5 substrings with a prime number of characters (ab, bc, cd, abc and bcd). Example 2: "abcde" is a string of length 5; there are a(5)=8 substrings with a prime number of characters (ab, bc, cd, de, abc, bcd, cde and abcde).
Also: If n is represented in base 1 (this means 1=1_1, 2=11_1, 3=111_1, 4=1111_1, etc.), then a(n) is the number of substrings of n with a prime number of digits. Example: 7=1111111_1; the number of prime substrings of 7 (in base 1) is a(7)=15, since there are 15 substrings of prime length: 6 2-digit substrings, 5 3-digit substrings, 3 5-digit substrings and 1 7-digit substring.
(End)

The sequence is well-defined in that for each n the set of numbers with n prime substrings in binary representation is not empty. Proof: A000975(n+1) has exactly n prime substrings in binary representation (see A000975).

All terms with n > 1 are odd.

The sequence is well-defined in that for each n the set of numbers with n prime substrings is not empty. Proof: Define m(0):=1, m(1):=2 and m(n+1):=9*m(n)+2 for n>0. This results in m(n)=2*sum_{j=0..n-1} 9^j = (9^n - 1)/4 or m(n)=1, 2, 22, 222, 2222, 22222, …, (in base-9) for n=0,1,2,3,…. Evidently, for n>0 m(n) has n 2’s and these are the only prime substrings in base-9 representation. This is why every substring of m(n) with more than one digit is a product of two integers > 1 (by definition) and can therefore not be a prime number.

No term is divisible by 9.

cp's OEIS Frontend

A213300 Largest number with n nonprime substrings (substrings with leading zeros are considered to be nonprime).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A046992 a(n) = Sum_{k=1..n} pi(k) (cf. A000720).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Formula

Extensions

A217302 Minimal natural number (in decimal representation) with n prime substrings in binary representation (substrings with leading zeros are considered to be nonprime).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A217309 Minimal natural number (in decimal representation) with n prime substrings in base-9 representation (substrings with leading zeros are considered to be nonprime).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A213302 Smallest number with n nonprime substrings (Version 1: substrings with leading zeros are considered to be nonprime).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A217102 Minimal number (in decimal representation) with n nonprime substrings in binary representation (substrings with leading zeros are considered to be nonprime).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A217109 Minimal number (in decimal representation) with n nonprime substrings in base-9 representation (substrings with leading zeros are considered to be nonprime).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A217112 Greatest number (in decimal representation) with n nonprime substrings in binary representation (substrings with leading zeros are considered to be nonprime).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A217119 Greatest number (in decimal representation) with n nonprime substrings in base-9 representation (substrings with leading zeros are considered to be nonprime).

Views