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
Examples
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).
Links
- Hieronymus Fischer, Table of n, a(n) for n = 0..200
Crossrefs
Formula
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).
A217102 Minimal number (in decimal representation) with n nonprime substrings in binary representation (substrings with leading zeros are considered to be nonprime).
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
Comments
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.
Examples
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).
Links
- Hieronymus Fischer, Table of n, a(n) for n = 1..2015
Crossrefs
Formula
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).
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
Comments
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.
Examples
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).
Links
- Hieronymus Fischer, Table of n, a(n) for n = 0..210
Crossrefs
Formula
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).
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
Comments
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.
Examples
(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.
Links
- Hieronymus Fischer, Table of n, a(n) for n = 1..1000
Crossrefs
Formula
a(n) >= A217102(n).
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).
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
Comments
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.
Examples
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.
Links
- Hieronymus Fischer, Table of n, a(n) for n = 0..40
Crossrefs
Formula
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.
A085557 Numbers that have more prime digits than nonprime digits.
2, 3, 5, 7, 22, 23, 25, 27, 32, 33, 35, 37, 52, 53, 55, 57, 72, 73, 75, 77, 122, 123, 125, 127, 132, 133, 135, 137, 152, 153, 155, 157, 172, 173, 175, 177, 202, 203, 205, 207, 212, 213, 215, 217, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232
Offset: 1
Comments
Begins to differ from A046034 at the 21st term (which is the first 3-digit term).
Examples
133 is in the sequence as the prime digits are 3 and 3 (those are two digits; counted with multiplicity) and one nonprime digit 1 and so there are more prime digits than nonprime digits. - _David A. Corneth_, Sep 06 2020
Links
- David A. Corneth, Table of n, a(n) for n = 1..10000
Crossrefs
Programs
-
PARI
is(n) = my(d = digits(n), c = 0); for(i = 1, #d, if(isprime(d[i]), c++)); c<<1 > #d \\ David A. Corneth, Sep 06 2020
-
Python
from itertools import count, islice def A085557_gen(startvalue=1): # generator of terms return filter(lambda n:len(s:=str(n))<(sum(1 for d in s if d in {'2','3','5','7'})<<1),count(max(startvalue,1))) A085557_list = list(islice(A085557_gen(),20)) # Chai Wah Wu, Feb 08 2023
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).
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
Comments
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).
Examples
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.
Links
- Hieronymus Fischer, Table of n, a(n) for n = 0..100
Crossrefs
A213303 Smallest number with n nonprime substrings (Version 2: substrings with leading zeros are counted as nonprime if the corresponding number is > 0).
2, 1, 10, 14, 101, 104, 144, 1001, 1014, 1044, 1444, 10010, 10014, 10144, 10444, 14444, 100101, 100104, 100144, 101444, 104444, 144444, 1000144, 1001014, 1001044, 1001444, 1014444, 1044444, 1444444, 10001044, 10001444, 10010144, 10010444, 10014444, 10144444, 10444444, 14444444, 100010144
Offset: 0
Comments
The sequence is well defined since for each n >= 0 there is a number with n nonprime substrings.
Different from A213304, first different term is a(16).
Examples
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.
Links
- Hieronymus Fischer, Table of n, a(n) for n = 0..100
Crossrefs
A213306 Minimal prime with n nonprime substrings (Version 2: substrings with leading zeros are counted as nonprime if the corresponding number is > 0).
2, 13, 11, 103, 101, 149, 1009, 1021, 1049, 1481, 10039, 10069, 10169, 11681, 14669, 100109, 100189, 100169, 101681, 104681, 146669, 1000669, 1001041, 1001081, 1004669, 1014469, 1046849, 1468469, 10001081, 10004669, 10010851
Offset: 0
Examples
a(0) = 2, since 2 is the least number with zero nonprime substrings. a(1) = 13, since 13 has 1 nonprime substring (=’1’). a(2) = 11, since 11 is the least number with 2 nonprime substrings (= 2 times ‘1’). a(3) = 103, since 103 is the least number with 3 nonprime substrings, these are ‘1’ and ‘10’ and ‘03’ (‘0’ is not a valid substring in version 2).
Links
- Hieronymus Fischer, Table of n, a(n) for n = 0..100
Crossrefs
A213307 Minimal prime with n nonprime substrings (Version 3: substrings with leading zeros are counted as nonprime if the corresponding number is not a prime).
2, 13, 11, 127, 101, 149, 1009, 1063, 1049, 1481, 10091, 10069, 10169, 11681, 14669, 100129, 100189, 100169, 101681, 104681, 146669, 1000669, 1001219, 1001081, 1004669, 1014469, 1046849, 1468469, 10001081, 10004669, 10010851
Offset: 0
Examples
a(0) = 2, since 2 is the least number with zero nonprime substrings. a(1) = 13, since 13 there is one nonprime substring (=1). a(2) = 11, since 11 is the least number with 2 nonprime substrings (2 times ‘1’). a(3) = 127, since 127 is the least number with 3 nonprime substrings, these are 1 and 12 and 27 (according to version 3).
Links
- Hieronymus Fischer, Table of n, a(n) for n = 0..100
Comments