A071070 -id:A071070 - cp's OEIS frontend

A327282 Cardinalities of the minimal sets of base-n representations of the composite numbers.

3, 4, 9, 10, 19, 18, 26, 28, 32, 32, 46, 43, 52, 54, 60, 60, 95, 77, 87, 90, 94, 97, 137, 117, 111, 115, 131, 123, 207, 147, 160, 163, 201, 169, 216, 173, 185, 195, 242, 205, 331, 229, 242, 252, 277, 261, 411, 294, 292, 290, 322, 299, 438, 331, 304, 331, 356, 339, 659, 375, 379, 404, 461, 412

Offset: 2

Hugo Pfoertner, Nov 29 2019

nonn

Second column |M(S_b)| of Figure 4 on page 20 of the Bright, Devillers, Shallit article.

			a(10) = 32 because there are 32 elements in the minimal set of composite-strings in base 10, given in A071070.

Curtis Bright, Raymond Devillers, and Jeffrey Shallit, Minimal Elements for the Prime Numbers, June 11, 2015.
Curtis Bright, Computed data for the MEPN project, data for composites, GitHub, 2015.
Raymond Devillers, Minimal primes and left-right-truncatable primes, GitHub repository, 2021.
Mersenneforum, Generalized minimal (probable) primes, Jan 2021.

Cf. A071070, A330048.

a(31)-a(65) from Hugo Pfoertner using data from Raymond Devillers, Jan 12 2021

A347819 Minimal elements for the base-10 representations of the primes greater than 10.

Original entry on oeis.org

11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 227, 251, 257, 277, 281, 349, 409, 449, 499, 521, 557, 577, 587, 727, 757, 787, 821, 827, 857, 877, 881, 887, 991, 2087, 2221, 5051, 5081, 5501, 5581, 5801, 5851, 6469, 6949, 8501

Offset: 1

Eric Chen, Sep 16 2021

Sequence is finite with 77 terms, the largest being 5*10^30 + 27 (which can be written 5(0_28)27, where 0_28 means the string of 28 0's). See text file for proof (this file also has proofs for bases 2, 3, 4, 5, 6, 8, 12).
Minimal elements for the base b representations of the primes > b for other bases b: (see the text file for 9 <= b <= 16) (all written in base b)
b=2: {11}
b=3: {12, 21, 111}
b=4: {11, 13, 23, 31, 221}
b=5: {12, 21, 23, 32, 34, 43, 104, 111, 131, 133, 313, 401, 414, 3101, 10103, 14444, 30301, 33001, 33331, 44441, 300031, 10^95 + 13}
b=6: {11, 15, 21, 25, 31, 35, 45, 51, 4401, 4441, 40041}
b=7: {14, 16, 23, 25, 32, 41, 43, 52, 56, 61, 65, 113, 115, 131, 133, 155, 212, 221, 304, 313, 335, 344, 346, 364, 445, 515, 533, 535, 544, 551, 553, 1022, 1051, 1112, 1202, 1211, 1222, 2111, 3031, 3055, 3334, 3503, 3505, 3545, 4504, 4555, 5011, 5455, 5545, 5554, 6034, 6634, 11111, 11201, 30011, 30101, 31001, 31111, 33001, 33311, 35555, 40054, 100121, 150001, 300053, 351101, 531101, 1100021, 33333301, 5100000001, 33333333333333331} (conjectured, not proven)
b=8: {13, 15, 21, 23, 27, 35, 37, 45, 51, 53, 57, 65, 73, 75, 107, 111, 117, 141, 147, 161, 177, 225, 255, 301, 343, 361, 401, 407, 417, 431, 433, 463, 467, 471, 631, 643, 661, 667, 701, 711, 717, 747, 767, 3331, 3411, 4043, 4443, 4611, 5205, 6007, 6101, 6441, 6477, 6707, 6777, 7461, 7641, 47777, 60171, 60411, 60741, 444641, 500025, 505525, 3344441, 4444477, 5500525, 5550525, 55555025, 444444441, 744444441, 77774444441, 7777777777771, 555555555555525, (10^220-1)/9*40 + 7}.
Equivalently: primes > 10 such that no proper substring (i.e., deleting any positive number of digits) is again a prime > 10. - M. F. Hasler, May 03 2022

			277 is in this sequence because none of 2, 7, 27, 77 is a prime > 10.
857 is in this sequence because none of 8, 5, 7, 85, 87, 57 is a prime > 10.
991 is in this sequence because none of 9, 1, 99, 91 is a prime > 10.
149 is not in this sequence because 19 is subsequence of 149 and 19 is a prime > 10.
389 is not in this sequence because 89 is subsequence of 389 and 89 is a prime > 10.
439 is not in this sequence because 43 is subsequence of 439 and 43 is a prime > 10.

Jinyuan Wang, Table of n, a(n) for n = 1..77
Curtis Bright, Raymond Devillers, and Jeffrey Shallit, Minimal Elements for the Prime Numbers, Experimental Mathematics 25 (3) (2016), pp. 321-331. DOI:10.1080/10586458.2015.1064048
Eric Chen, Minimal elements for the base b representations of the primes which are > b
Eric Chen, Data for minimal elements for the base b representations of the primes which are > b for 2 <= b <= 16
Eric Chen, Proof for that the data for bases 2, 3, 4, 5, 6, 8, 10, 12 is complete
Eric Chen, Known values or lower bounds of the largest minimal element for the base b representations of the primes which are > b for 2 <= b <= 36
Eric Chen, Condensed table for the status of the minimal element for the base b representations of the primes which are > b for 2 <= b <= 16
Prime Glossary, Minimal prime
J. Shallit, Minimal primes, J. Recreational Math., 30:2 (2000) pp. 113-117.

Cf. A071062 (primes > 10 are not required).

Minimal sets for other sets: A071070 (for composites), A071071 (powers of 2), A071072 (multiples of 4), A071073 (multiples of 3), A111055 (primes of the form 4*n+1), A111056 (primes of the form 4*n+3), A114835 (palindromic primes), A130448 (minimal set of squares).

a(n, k, b)=v=[]; for(r=1, length(digits(n, b)), if(r+length(digits(k, 2))-length(digits(n, b))>0 && digits(k, 2)[r+length(digits(k, 2))-length(digits(n, b))]==1, v=concat(v, digits(n, b)[r]))); fromdigits(v, b)
iss(n, b)=for(k=1, 2^length(digits(n, b))-2, if(ispseudoprime(a(n, k, b)) && a(n, k, b)>b, return(0))); 1
is(n, b=10)=isprime(n) && n>b && iss(n, b) \\ Test whether n is a minimal element for the base b representations of the primes > b. Default value b = 10 for this sequence.
select( {is_A347819(n,b=10)=for(L=2, #n=digits(n,b), forvec(d=vector(L, i, [1,#n]), n[d[1]]&& isprime(fromdigits(vecextract(n,d),b))&& return(L==#n), 2))}, [1..8888]) \\ Better select among primes([1,N]). - M. F. Hasler, May 03 2022

Edited by M. F. Hasler, May 03 2022

A111057 Minimal set in the sense of A071062 of prime-strings in base 12 for primes of the form 4n+1.

Original entry on oeis.org

5, 13, 37, 73, 97, 109, 313, 337, 373, 409, 421, 577, 601, 661, 709, 1009, 1033, 1093, 1129, 1489, 1609, 1669, 3457, 7537, 12721, 13729, 17401, 17569, 19009, 19141, 20593, 20641, 165877, 208501, 221173, 225781, 226201, 226357, 228793, 246817, 246937, 248821, 1097113, 2695813, 2735269, 2736997, 2737129, 32555521, 388177921

Offset: 1

Walter Kehowski, Oct 06 2005

Maple worksheet available upon request. Here is the minimal set of primes of the form 4n+1 in base 12, where X is ten and E is eleven. 5, 11, 31, 61, 81, 91, 221, 241, 271, 2X1, 2E1, 401, 421, 471, 4E1, 701, 721, 771, 7X1, X41, E21, E71, 2001, 4441, 7441, 7E41, X0X1, X201, E001, E0E1, EE01, EE41, 7EEE1, X07E1, X7EE1, XX7E1, XXXX1, XXEE1, E04X1, EXX01, EXXX1, EEEE1, 44XXX1, XX00E1, XEXXE1, XEEXE1, XEEEX1, XXX0001, XX000001. Note that the last prime in the set is the same as the last prime in the minimal set of all primes. See A110600. I am checking certain ranges past this last prime but flow-charting the possibilities leads me to believe I have found the full sequence. The minimal set of prime strings in base 12 for primes of the form 4n+3 is [3, 7, E] since every 4n+3 prime greater than 3 ends in either 7 or E.

			a(11)=421="2E1" since the pattern "*2*E*1*" does not occur in any previously found prime of the form 4n+1. Assuming all previous members of the list have been similarly recursively constructed, then "401" (577 in base 10) is the next prime in the list. The basic rule is: if no substring of p matches any previously found prime, add p to the list. The basic theorem of minimal sets says that this process will terminate, that is, the minimal set is always finite.

J. Shallit, Minimal primes, J. Recreational Mathematics, vol. 30.2, pp. 113-117, 1999-2000.

Cf. A071062, A071070, A110600, A110615.

cp's OEIS Frontend

A327282 Cardinalities of the minimal sets of base-n representations of the composite numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A347819 Minimal elements for the base-10 representations of the primes greater than 10.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A111057 Minimal set in the sense of A071062 of prime-strings in base 12 for primes of the form 4n+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A172982 Partial sums of minimal set of prime-strings in base 10 (A071062).

Views

Author

Keywords

Comments

Examples

Crossrefs