A071062 -id:A071062 - cp's OEIS frontend

A111055 The set of primes of the form 4n+1 that is minimal in the sense of A071062.

5, 13, 17, 29, 37, 41, 61, 73, 89, 97, 101, 109, 149, 181, 233, 277, 281, 349, 409, 433, 449, 677, 701, 709, 769, 821, 877, 881, 1669, 2221, 3001, 3121, 3169, 3221, 3301, 3833, 4969, 4993, 6469, 6833, 6949, 7121, 7477, 7949, 9001, 9049, 9221, 9649, 9833

Offset: 1

Walter Kehowski, Oct 06 2005

This means: by removing any (possibly none) of the decimal digits of any member of A002144 one can obtain some number of this sequence here.
The basic algorithm is: if no substring of p matches any previously found prime, add p to the list.
The basic theorem of minimal sets says that the minimal set is always finite.

			a(11)=101 since the pattern "*1*0*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 109 is the next prime in the list.

Walter A. Kehowski and Curtis Bright, Table of n, a(n) for n = 1..146 (first 135 terms from Walter A. Kehowski)
Carlos Rivera, Puzzle 178. Shallit Minimal Primes Set, The Prime Puzzles & Problems Connection.
Jeffrey Shallit, Minimal primes, J. Recreational Mathematics, vol. 30.2, pp. 113-117, 1999-2000.

Cf. A071062, A071070, A110600, A110615.

with(StringTools);
wc := proc(s) cat("*",Join(convert(s,list),"*"),"*") end;
M1:=[]: wcM1:=[]: p:=1: for z from 1 to 1 do for k while p<10^11 do p:=nextprime(p);
if k mod 100000 = 0 then print(k,p,evalf((time()-st)/60,4)) fi;
if p mod 4 = 1 then sp:=convert(p,string); if andmap(proc(w) not(WildcardMatch(w,sp)) end, wcM1) then
M1:=[op(M1),p]; wcM1:=[op(wcM1), wc(sp)]; print(p) fi fi od od;

Shortened definition; moved some material from the examples to the comments - R. J. Mathar, May 24 2010

A110600 Minimal set of prime-strings in base 12 in the sense of A071062.

Original entry on oeis.org

2, 3, 5, 7, 11, 13, 73, 97, 109, 577, 1489, 7537, 17401, 226201, 1097113, 32555521, 388177921

Offset: 1

Walter Kehowski, Sep 14 2005

Maple worksheet available upon request. Here is the minimal set in base 12 where X is 10 and E is 11. 2, 3, 5, 7, E, 11, 61, 81, 91, 401, X41, 4441, X0X1, XXXX1, 44XXX1, XXX0001, XX000001. This minimal set demonstrates the elegance of base 12 generally since you can mentally follow the process of elimination, all primes after E end in the neutral digit 1 and the last two entries only contain X, 0 and 1. There are no primes of the form X0...01 since the sum of its digits is E and hence it is divisible by E.

The smallest prime found to date that satisfies all patterns in the minimal set is 1234456789X04XXX00E0001 (656969693573113867991809 in base 10). [Walter Kehowski, May 18 2012]

			a(10)=401 since no earlier prime in the list contained the pattern "*4*0*1*" where "*" stands for zero or more digits. The list can be manually constructed using a sieve-like process: eliminate all subsequent primes of the form "*4*0*1*" from the list of all primes. Assuming all previous elements have also been similarly determined, the next remaining prime should be X41.

Cf. A071062, A071070.

A111056 Minimal set of prime-strings in base 10 for primes of the form 4n+3 in the sense of A071062.

Original entry on oeis.org

3, 7, 11, 19, 59, 251, 491, 499, 691, 991, 2099, 2699, 2999, 4051, 4451, 4651, 5051, 5651, 5851, 6299, 6451, 6551, 6899, 8291, 8699, 8951, 8999, 9551, 9851, 22091, 22291, 66851, 80051, 80651, 84551, 85451, 86851, 88651, 92899, 98299, 98899

Offset: 1

Walter Kehowski, Oct 06 2005

The basic rule is: if no substring of p matches any smaller prime of the form 4n+3, add p to the list. The basic theorem of minimal sets says that the minimal set is always finite.

The sequence b-file is complete except for the number (2*10^19153 + 691)/9, i.e., the decimal number consisting of 19151 "2"s followed by two "9"s. - Curtis Bright, Jan 23 2015

			From _Danny Rorabaugh_, Mar 26 2015: (Start)
a(5) is not 23, even though 23 is the fifth prime of the form 4n+3, since 23 contains a(1)=3 as a substring. Similarly: 31 and 43 contain 3 and 47 contains a(2)=7. Thus a(5)=59.
This sequence contains 2099 since 2, 0, 9, 20, 09, 99, 209, 299, and 099 are not primes of the form 4n+3.
(End)

Walter A. Kehowski and Curtis Bright, Table of n, a(n) for n = 1..112 (first 103 terms from Walter A. Kehowski)
Walter A. Kehowski, Full list of terms
F. Morain, Primality certificate for the largest number of A111056, May 4 2015.
Carlos Rivera, Puzzle 178. Shallit Minimal Primes Set, The Prime Puzzles & Problems Connection.
Jeffrey Shallit, Minimal primes, J. Recreational Mathematics, vol. 30.2, pp. 113-117, 1999-2000.

Cf. A071062, A071070, A110600, A110615.

with(StringTools); wc := proc(s) cat("*",Join(convert(s,list),"*"),"*") end; M3:=[]: wcM3:=[]: p:=1: for z from 1 to 1 do for k while p<10^11 do p:=nextprime(p); if k mod 100000 = 0 then print(k,p,evalf((time()-st)/60,4)) fi; if p mod 4 = 3 then sp:=convert(p,string); if andmap(proc(w) not(WildcardMatch(w,sp)) end, wcM3) then M3:=[op(M3),p]; wcM3:=[op(wcM3),wc(sp)]; print(p) fi fi od od; # Let it run for a couple of days.

A114835 Minimal set of palindrome prime-strings in base 10 in the sense of A071062.

Original entry on oeis.org

2, 3, 5, 7, 11, 919, 94049, 94649, 94849, 94949, 96469, 98689, 9809089, 9888889, 9889889, 9908099, 9980899, 9989899, 900808009, 906686609, 906989609, 908000809, 908444809, 908808809, 909848909, 960898069, 968999869, 988000889

Offset: 1

Walter Kehowski, Feb 19 2006

The one-digit primes are palindrome by default so the sequence starts off 2, 3, 5, 7 and so from now on all primes fitting one of the patterns *2*, *3*, *5*, *7* are excluded. The first palindrome prime that is not excluded is 11 so our list is now 2, 3, 5, 7, 11. Observe that from now on all the only palindrome primes allowed have first and last digit 9 and the only middle digits allowed are then 0, 1, 4, 6, 8, 9. But the first and only 3 digit palindrome to occur is 919, so from now on the only middle digits allowed are 0, 4, 6, 8, 9. The five digit palindrome primes that do not fit the patterns *2*, *3*, *5*, *7*, *1*1* and *9*1*9* are 94049, 94649, 94849, 94949, 96469, 98689. The rest of the sequence is determined in this recursive manner.

			a(6)=919 since it is the first 3-digit palindrome prime that does not fit the wildcard pattern established by the previous 5 elements, 2, 3, 5, 7, 11.

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

Walter A. Kehowski, Full list of terms
C. K. Caldwell, The Prime Glossary, minimal prime
J. Shallit, Minimal primes, J. Recreational Mathematics, vol. 30.2, pp. 113-117, 1999-2000.

Cf. A071062, A071070.

Maple
```
Maple worksheet available upon request.
```

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.

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

Original entry on oeis.org

2, 5, 10, 17, 28, 47, 88, 149, 238, 647, 1096, 1595, 2476, 3467, 9936, 16885, 25886, 34935, 44584, 54533, 115182, 781831, 1728500, 61728549, 127728598, 194328647

Offset: 1

Jonathan Vos Post, Feb 06 2010

The subsequence of primes is: 2, 5, 47, 149, 647, 3467, of which only 2 and 5 are in the original sequence.

			a(26) = 194328647 = 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.

Cf. A000040, A071062, A071070, A071071, A071072, A071073.

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 *)

A062115 Numbers with no prime substring in their decimal expansion.

Original entry on oeis.org

0, 1, 4, 6, 8, 9, 10, 14, 16, 18, 40, 44, 46, 48, 49, 60, 64, 66, 68, 69, 80, 81, 84, 86, 88, 90, 91, 94, 96, 98, 99, 100, 104, 106, 108, 140, 144, 146, 148, 160, 164, 166, 168, 169, 180, 184, 186, 188, 400, 404, 406, 408, 440, 444, 446, 448, 460, 464, 466

Offset: 1

Erich Friedman, Jun 28 2001

This is a 10-automatic sequence, a consequence of the finitude of A071062. - Charles R Greathouse IV, Sep 27 2011

Subsequence of A202259 (right-truncatable nonprimes). Supersequence of A202262 (composite numbers in which all substrings are composite), A202265 (nonprime numbers in which all substrings and reversal substrings are nonprimes). - Jaroslav Krizek, Jan 28 2012

			25 is not included because 5 is prime.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Jeffrey Shallit, Minimal primes, Journal of Recreational Mathematics 30:2 (1999-2000), pp. 113-117.
Index entries for 10-automatic sequences.

Subsequence of A084984. [Arkadiusz Wesolowski, Jul 05 2011]
Cf. A071062.
Cf. A163753 (complement).

a062115 n = a062115_list !! (n-1)
a062115_list = filter ((== 0) . a039997) a084984_list
-- Reinhard Zumkeller, Jan 31 2012

from sympy import isprime
def ok(n):
    s = str(n)
    ss = (int(s[i:j]) for i in range(len(s)) for j in range(i+1, len(s)+1))
    return not any(isprime(k) for k in ss)
print([k for k in range(500) if ok(k)]) # Michael S. Branicky, May 02 2023

# faster for initial segment of sequence; uses ok, import above
from itertools import chain, count, islice, product
def agen(): # generator of terms
    yield from chain((0,), (int(t) for t in (f+"".join(r) for d in count(1) for f in "14689" for r in product("014689", repeat=d-1)) if ok(t)))
print(list(islice(agen(), 100))) # Michael S. Branicky, May 02 2023

A039997(a(n)) = 0. - Reinhard Zumkeller, Jul 16 2007
From Charles R Greathouse IV, Mar 23 2010: (Start)
a(n) = O(n^(log_4 10)) = O(n^1.661) because numbers containing only 0,4,6,8 are in this sequence.
a(n) = Omega(n^(log_13637 1000000)) = Omega(n^1.451) for similar reasons; this bound can be increased by considering longer sequences of digits. (End)

Offset corrected by Arkadiusz Wesolowski, Jul 27 2011

A202262 Composite numbers in which all substrings are composite.

Original entry on oeis.org

4, 6, 8, 9, 44, 46, 48, 49, 64, 66, 68, 69, 84, 86, 88, 94, 96, 98, 99, 444, 446, 448, 464, 466, 468, 469, 484, 486, 488, 494, 496, 498, 644, 646, 648, 649, 664, 666, 668, 669, 684, 686, 688, 694, 696, 698, 699, 844, 846, 848, 849, 864, 866, 868, 869, 884, 886

Offset: 1

Jaroslav Krizek, Dec 25 2011

Subsequence of A062115, A202260, A029581.
Supersequence of A202265.
This is a 10-automatic sequence, see A071062. - Charles R Greathouse IV, Jan 01 2012

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Rémy Sigrist, PARI program for A202262
Index entries for 10-automatic sequences

Cf. A085823 (primes in which all substrings are primes), A068669 (noncomposite numbers in which all substrings are noncomposite), A062115 (nonprimes in which all substrings are nonprimes).

Cf. A010051.

sub[n_] := Block[{d = IntegerDigits[n]}, Union@ Reap[ Do[Sow@ FromDigits@ Take[d, {i, j}], {j, Length@ d}, {i, j}]][[2, 1]]]; Select[ Range@ 900, Union[{4, 6, 8, 9}, IntegerDigits[#]] == {4, 6, 8, 9} && AllTrue[sub[#], CompositeQ] &] (* Giovanni Resta, Dec 20 2019 *)

PARI
```
See Links section.
```

Data corrected by Reinhard Zumkeller, May 05 2012
Data corrected by Rémy Sigrist, Dec 19 2019
Incorrect Haskell program deleted by M. F. Hasler, Dec 20 2019

A071071 Minimal "powers of 2" set in base 10: any power of 2 contains at least one term of this sequence in its decimal expansion.

Original entry on oeis.org

1, 2, 4, 8, 65536

Offset: 1

Benoit Cloitre, May 26 2002

Conjectured by J. Shallit to be complete.

A possible exception are powers of 16. It can be proved that 16^(5^(k-1) + floor((k+3)/4)) == 16^floor((k+3)/4) (mod 10^k) (see attached proof). Thus it may be that there is a power of 16 that does not contain any of the digits 1, 2, 4, and 8 or the number 65536 as a substring. - Bassam Abdul-Baki, Apr 10 2019

J.-P. Delahaye, Nombres premiers inévitables et pyramidaux, Pour la science, (French edition of Scientific American), Juin 2002, p. 98

Bassam Abdul-Baki, Minimal Sets for Powers of 2
David Butler, 65536, Making Your Own Sense, June 21 2017.
Jeffrey Shallit, The Prime Game, Recursivity, December 01 2006.
Index to divisibility sequences

Cf. A071062, A071070, A071072, A071073.

cp's OEIS Frontend

A111055 The set of primes of the form 4n+1 that is minimal in the sense of A071062.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Extensions

A110600 Minimal set of prime-strings in base 12 in the sense of A071062.

Views

Author

Keywords

Comments

Examples

Crossrefs

A111056 Minimal set of prime-strings in base 10 for primes of the form 4n+3 in the sense of A071062.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A114835 Minimal set of palindrome prime-strings in base 10 in the sense of A071062.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

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

A071070 Minimal set of composite-strings in base 10.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

A062115 Numbers with no prime substring in their decimal expansion.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Python

Python

Formula

Extensions

A202262 Composite numbers in which all substrings are composite.