A071071 -id:A071071 - cp's OEIS frontend

A071062 Minimal set of prime-strings in base 10.

2, 3, 5, 7, 11, 19, 41, 61, 89, 409, 449, 499, 881, 991, 6469, 6949, 9001, 9049, 9649, 9949, 60649, 666649, 946669, 60000049, 66000049, 66600049

Offset: 1

Benoit Cloitre, May 26 2002

Any prime number contains in its digits at least one of the terms of this sequence and there is no smaller set. There are 26 terms in the sequence.

Ioulia N. Baoulina, Martin Kreh, and Jörn Steuding, Deleting digits, arXiv:1607.01548 [math.NT], 2016.
David Butler, 65536, Making Your Own Sense blog, June 2017.
C. K. Caldwell, The Prime Glossary, minimal prime
J.-P. Delahaye, Nombres premiers inévitables et pyramidaux, Pour la science, (French edition of Scientific American), Juin 2002, p. 99.
Ernest G. Hibbs, Component Interactions of the Prime Numbers, Ph. D. Thesis, Capitol Technology Univ. (2022), see p. 33.
J. Shallit, Minimal primes, pdf, J. Recreational Mathematics, vol. 30.2, pp. 113-117, 1999-2000.

Cf. A071070, A071071, A071072, A071073.

Typo corrected by T. D. Noe, Nov 15 2006

Typo corrected by Walter Kehowski, Feb 22 2007

A071070 Minimal set of composite-strings in base 10.

Original entry on oeis.org

4, 6, 8, 9, 10, 12, 15, 20, 21, 22, 25, 27, 30, 32, 33, 35, 50, 51, 52, 55, 57, 70, 72, 75, 77, 111, 117, 171, 371, 711, 713, 731

Offset: 1

Benoit Cloitre, May 26 2002

Any composite number contains in its digits at least one of the term of this sequence and there is no smaller set.

J.-P. Delahaye, "Pour la science", (French edition of Scientific American), Juin 2002, p. 99
J. Shallit, Minimal primes, in J.Recreational Mathematics, vol. 30.2, pp. 113-117,1999-2000

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

Cf. A071062, A071071, A071072, A071073.

subs[digits_List] := Select[Subsets[digits], CompositeQ[FromDigits[#]]&] //. {a___List, b_List, c___List, d_List, e___List} /; MemberQ[Subsets[d], b] :> {a, b, c, e};
aa = {};
Do[aa = Union[aa, subs[IntegerDigits[n]]], {n, Select[Range[1000], CompositeQ]}];
A071070 = FromDigits /@ aa (* Jean-François Alcover, Dec 20 2017 *)

A071073 Minimal "multiples of 3" set in base 10.

Original entry on oeis.org

0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 42, 45, 48, 51, 54, 57, 72, 75, 78, 81, 84, 87, 111, 114, 117, 141, 144, 147, 171, 174, 177, 222, 225, 228, 252, 255, 258, 282, 285, 288, 411, 414, 417, 441, 444, 447, 471, 474, 477, 522, 525, 528, 552, 555, 558, 582, 585, 588

Offset: 1

Benoit Cloitre, May 26 2002

Any multiple of 3 contains in its digits at least one of the terms of this sequence. There are 76 terms in the sequence; Delahaye gives all 76 terms and proves that there are no further terms (his statement that there are 280 terms seems to be a typo). There is no smaller set.

Nathaniel Johnston, Table of n, a(n) for n = 1..76 (full sequence)
J.-P. Delahaye, Nombres premiers inévitables et pyramidaux, Pour la Science 296 (2002), p 102.

Cf. A071062, A071071, A071072, A071070.

A071072 Minimal "multiples of 4" set in base 10.

Original entry on oeis.org

0, 4, 8, 12, 16, 32, 36, 52, 56, 72, 76, 92, 96

Offset: 1

Benoit Cloitre, May 26 2002

Any multiple of 4 contains in its digits at least one of the terms of this sequence, and there is no smaller set.

J.-P. Delahaye, "Pour la science" (French edition of Scientific American), Juin 2002, p. 98

Cf. A071062, A071071, A071070, A071073.

A137998 Least k such that floor(16^n / 10^k) = 1, 2, 4 or 8 (mod 10), or zero if no such k exists.

Original entry on oeis.org

1, 2, 3, 0, 3, 1, 2, 2, 5, 4, 1, 4, 2, 4, 4, 1, 2, 4, 2, 2, 1, 3, 2, 7, 5, 1, 2, 4, 3, 3, 1, 2, 2, 3, 4, 1, 4, 2, 4, 3, 1, 2, 4, 2, 2, 1, 5, 2, 5, 3, 1, 2, 5, 7, 4, 1, 2, 2, 3, 4, 1, 3, 2, 7, 3, 1, 2, 4, 2, 2, 1, 12, 2, 3, 7, 1, 2, 3, 5, 7, 1, 2, 2, 3, 4, 1, 3, 2, 5, 3, 1, 2, 3, 2, 2, 1, 6, 2, 3, 5, 1, 2, 3, 4, 3

Offset: 1

M. F. Hasler, Mar 26 2008

Equivalent definition: position of least significant decimal digit in 16^n equal to one of {1,2,4,8}, or zero if none of these occur. Since this is the true meaning, the sequence is flagged "base", even if the actual definition does not explicitly refer to a base.
This is related to A071071, i.e., the conjecture by J. Shallit that {1,2,4,8,65536} is a minimal set for powers of 2 written in base 10. This amounts to saying that any power of 2 contains either a digit among {1,2,4,8}, or 65536 as subword (obtained by deleting zero or more digits of the number).
Any power 2^k ends in a digit among {1,2,4,8} except for k=4n, n>0, in which case 2^k=16^n ends in 6.
The present sequence gives the position of the first digit (starting with units) of these powers which is among {1,2,4,8}. It appears as if 16^4=65536 is the only power of 2 which does not contain any of these four digits. This would imply the conjecture (and be an even stronger statement).
The sequence has a repeating pattern of length 25 of the form
( 1 2 A B C 1 2 2 D E 1 F 2 G H 1 2 J 2 2 1 K 2 L M )... where A-M follow again a repeating pattern:
A=(3,p,q,3,3)... ; C=(3,3,r,s,3)...; D=(t,3,3,3,u)...; etc.

			a(1)=1 since 16^1 has a 1 in position 1 (10^1).
a(2)=2 since 16^2=256 has a 2 in position 2 (10^2).
a(3)=3 since 16^3=4096 has a 4 in position 3 (10^3).
a(4)=0 since 16^4=65536 has no digit 1,2,4 or 8.
If we arrange the terms in a 25-column matrix, we can see the pattern:
[1 2 3 0 3 1 2 2 5 4 1 4 2 4 4 1 2 4 2 2 1  3 2 7 5]
[1 2 4 3 3 1 2 2 3 4 1 4 2 4 3 1 2 4 2 2 1  5 2 5 3]
[1 2 5 7 4 1 2 2 3 4 1 3 2 7 3 1 2 4 2 2 1 12 2 3 7]
[1 2 3 5 7 1 2 2 3 4 1 3 2 5 3 1 2 3 2 2 1  6 2 3 5]
[1 2 3 4 3 1 2 2 5 3 1 3 2 3 8 1 2 5 2 2 1  4 2 3 4]
[1 2 3 4 3 1 2 2 6 5 1 6 2 5 4 1 2 5 2 2 1  3 2 5 4]
[1 2 7 3 3 1 2 2 3 7 1 8 2 7 3 1 2 5 2 2 1  7 2 4 3]
[1 2 4 5 4 1 2 2 3 7 1 3 2 4 3 1 2 4 2 2 1  4 2 3 5]
[1 2 3 4 4 1 2 2 3 7 1 3 2 6 3 1 2 3 2 2 1  4 2 3 8]
[1 2 3 5 3 1 2 2 4 3 1 3 2 3 4 1 2 6 2 2 1  5 2 3 6]
[1 2 3 4 3 1 2 2 9 4 1 5 2 4 5 1 2 8 2 2 1  3 2 4 5] etc.

J. Shallit, Minimal primes, J. Recreational Mathematics 30 (2) (1999-2000), 113-117.

Cf. A071071.

A137998(n,S=Vec("1248"))={ forstep( i=#n=Vec(Str(16^n)),1,-1, setsearch(S,n[i]) & return( #n-i ))}

t=0;matrix(25,20/*# of rows*/,i,j,A137998(t++))~

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

cp's OEIS Frontend

A071062 Minimal set of prime-strings in base 10.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A071070 Minimal set of composite-strings in base 10.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

A071073 Minimal "multiples of 3" set in base 10.

Views

Author

Keywords

Comments

Links

Crossrefs

A071072 Minimal "multiples of 4" set in base 10.

Views

Author

Keywords

Comments

References

Crossrefs

A137998 Least k such that floor(16^n / 10^k) = 1, 2, 4 or 8 (mod 10), or zero if no such k exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs