Mathematics desk
< September 17	<< Aug \| September \| Oct >>	September 19 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 18

Minimal set of prime-strings in base 10.

(Inspired by the question of Sep 15)

The set is OEIS A071062 is "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"

"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."

Now the first few Prime numbers A000040 are "2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271"

Obviously primes 2,3,5,7,11 are in the set. 13 has 3. 17 has 7. 19 is in the set. 23 has 2 and 3. 29 has 2. 31,37 have 3. etc and when you get to 41 you have to add it to the set and ditto for 61 and 89. But I can't work out why 101 isn't in the set - there is no 1 nor 10. Are they really omitting digits and counting 11 as valid? The same question for 109? I find OEIS's terse descriptions very hard to follow.

If they are happy to omit digits (base 10), do they require the digits in the same order? Confusing. -- SGBailey (talk) 07:39, 18 September 2023 (UTC)[reply]

Yes, it is the difference between subsequence and substring also referred to earlier. The sequence "101" contains the subsequence "11". --Lambiam 11:59, 18 September 2023 (UTC)[reply]

Perhaps it's worth noting that the name is "Minimal set of prime-strings in base 10", requiring the entries to be primes themselves. Otherwise the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9 would work and that only has 9 terms. --RDBury (talk) 18:05, 18 September 2023 (UTC)[reply]

There are 77 elements in the minimal set of “primes > 10” strings in base 10: {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, 9001, 9049, 9221, 9551, 9649, 9851, 9949, 20021, 20201, 50207, 60649, 80051, 666649, 946669, 5200007, 22000001, 60000049, 66000049, 66600049, 80555551, 555555555551, 5000000000000000000000000000027}, e.g. 857 is a minimal prime in decimal (base b = 10) because there is no prime > 10 among the shorter subsequences of the digits: 8, 5, 7, 85, 87, 57. The subsequence does not have to consist of consecutive digits, so 149 is not a minimal prime in decimal (because 19 is prime and 19 > 10). But it does have to be in the same order; so, for example, 991 is still a minimal prime in decimal even though a subset of the digits can form the shorter prime 19 > 10 by changing the order. 220.138.46.130 (talk) 01:06, 19 September 2023 (UTC)[reply]