mersenneforum.org Minimal set of the strings for primes with at least two digits
 Register FAQ Search Today's Posts Mark Forums Read

2022-04-06, 14:06   #320
Dr Sardonicus

Feb 2017
Nowhere

577210 Posts

Quote:
 Originally Posted by kruoli Edit, clarification: By 1…1, I do not mean only ones. It should be understood as starting with a one, other digits, and ending with a one.
For possible future reference, giving the first two (or more) most significant digits and the last two (or more) digits of a many-digit number is common practice. Sometimes the number of intervening digits is also given.

In the present instance, 14...91 or 14... (24862044 digits) ...91 would be much clearer.

The most significant digits of Mp are determined by the fractional part of p*log(2)/log(10).

EDIT: Although there is no upper bound on the number of leading 1's in a Mersenne number 2n - 1, or AFAIK for 2p - 1 with p prime, there is an upper bound for the number of terminal 1's. Three. The proof is easy.

(The Mersenne number 2888689 - 1 has 4 leading 1's and 3 terminal 1's. M888689 has a small factor q = 24*p + 1, and the cofactor is proven composite.)

Last fiddled with by Dr Sardonicus on 2022-04-06 at 19:47 Reason: As indicated

2022-04-07, 03:12   #321
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

22×5×132 Posts

Quote:
 Originally Posted by sweety439 An interesting and difficult problem is find the smallest prime p such that all strings not containing any element in S (S is the set of the minimal primes (start with b+1) in base b) as subsequence, when read as base b representation, which are > b, are divisible by at least one prime <= p (such prime may not exist, as in some bases (such as 8, 9, 12, 14, 16), there are some families which are ruled out as only contain composite numbers by all or partial algebraic factors, in these bases we find the smallest prime p such that all strings not containing any element in S (S is the set of the minimal primes (start with b+1) in base b) as subsequence, when read as base b representation, which are > b, are either "divisible by at least one prime <= p" or "of the special form", the special forms are: Code: base (b) forms 8 1{0}1 9 {1}, 3{1}, 3{8}, 3{8}35, {8}5 12 {B}9B 14 8{D}, {D}5 16 10{5}, 1{5}, {4}1, 7{3}, 8{5}, 8{F}, B{4}1, {C}D, {C}DD, {F}7 17 1{9}, {9}8 19 1{6}, {6}5, 7{2}, 89{6} 24 3{N}, 5{N}, {6}1, 8{N} 25 {1}, 1{3}, 1{8}, 2{1}, {3}2, 5{1}, 5{8}, 7{1}, {8}3, {8}7, C{1}, F{1}, M{1}, 27{1} 27 1{0}8, 7{Q}, 8{0}1, 9{G}, {D}E, {G}7, {Q}J 32 1{0}1, {1} 33 F{W}, L{4}, {W}H 34 1{B}, 8{X}, G{B}, L{B}, {X}P 36 3{7}, 3{Z}, 8{Z}, 9{5}, G{7}, O{Z}, {Z}B The sequence of the smallest prime factor of the numbers in these families is very likely to be unbounded above, thus such p in these bases very unlikely to exist. Equivalently, finding the smallest prime p such that "the set of the minimal ("the primes > b and <= p" and "the numbers > b not divisible by any prime <= p") in base b" is the same as "the set of the minimal primes (start with b+1) in base b" In base b=10 such prime is 214741, which is needed to remove the composite number 5(0^24)27, see factorization of 5{0}27 and factorization of {5}1 In base b=2 such prime is 10 (decimal 2), since all numbers > 1 not divisible by 2 (i.e. the odd numbers > 1) have first digit 1 and last digit 1 in base b=2, thus the only minimal prime (start with b+1) 11 (decimal 3) must be a subsequence. In base b=3 such prime is 10 (decimal 3); first, 10 (decimal 3) is needed, since this prime is needed to remove the numbers 1{0} (i.e. 100, 1000, 10000, 100000, ...); second, for the numbers not divisible by 2 or 3, such number cannot end with 0 (of course also cannot begin with 0) and must have an odd number of 1, thus either 111 (i.e. 3 1's) or 12 or 21 must be a subsequence, unless the number is 1, which is not allowed in this research. In base b=4 such prime is 3 (decimal 3), which is used to remove the numbers: 21 (decimal 9), all numbers of the form 2{0}1, and the numbers containing only 0 and 3 In base b=5 such prime is 11332432 (decimal 105367), which is used to remove the number 1(0^53)13, see factorization of 1{0}13 in base 5 In base b=6 such prime is 21 (decimal 13), which is used to remove the number 441 (decimal 169), note that 4041 (decimal 889) is divisible by 7 In base b=7 such prime is 15421 (decimal 4327), see factorization of {3}1 in base 7 and factorization of 51{0}1 in base 7 In base b=8 such prime does not exist, since the family 1{0}1 has infinite subset whose elements are pairwise coprime but the family 1{0}1 can be ruled out as only contain composite numbers, but if we only consider the numbers not in the family 1{0}1, such prime will be the smallest prime factor of (4*8^217+17)/7 (if it is > 7885303569123738614221) or 7885303569123738614221, which is needed to remove the composites (4^216)7 and (4^116)7, respectively, see factorization of {4}7 in base 8 In base b=9 such prime does not exist, since the families {1}, 3{1}, 3{8}, 3{8}35, {8}5 has infinite subset whose elements are pairwise coprime but the families {1}, 3{1}, 3{8}, 3{8}35, {8}5 can be ruled out as only contain composite numbers, but if we only consider the numbers not in the families {1}, 3{1}, 3{8}, 3{8}35, {8}5, such prime exists, but is very hard to find, since finding this prime requires factoring the large numbers in the families 3{0}11, 2{7}07, 7{6}2 In base b=12 such prime does not exist, since the family {B}9B has infinite subset whose elements are pairwise coprime but the family {B}9B can be ruled out as only contain composite numbers, but if we only consider the numbers not in the family {B}9B, such prime will be 534AB547A0351 (decimal 47113717465069), see factorization of 4{0}77 in base 12 and factorization of B{0}9B in base 12
A highly-related problem is find the smallest set T (the set with the smallest "number of elements", then with the smallest "smallest prime", then with the smallest "second-smallest prime", then with the smallest "third-smallest prime", ...) of primes such that all strings not containing any element in S (S is the set of the minimal primes (start with b+1) in base b) as subsequence, when read as base b representation, which are > b, are divisible by at least one element in T (in some bases (such as 8, 9, 12, 14, 16), there are some families which are ruled out as only contain composite numbers by all or partial algebraic factors, thus in these bases, the set T is infinite)

In base b=2, T={2}, since all numbers > 1 not divisible by 2 (i.e. the odd numbers > 1) have first digit 1 and last digit 1 in base b=2, thus the only minimal prime (start with b+1) 11 (decimal 3) must be a subsequence.

In base b=3, T={2,3}; first, 10 (decimal 3) is needed, since this prime is needed to remove the numbers 1{0} (i.e. 100, 1000, 10000, 100000, ...); second, for the numbers not divisible by 2 or 3, such number cannot end with 0 (of course also cannot begin with 0) and must have an odd number of 1, thus either 111 (i.e. 3 1's) or 12 or 21 must be a subsequence, unless the number is 1, which is not allowed in this research.

In base b=4, T={2,3}; since all numbers not divisible by 2 (i.e. end with 1 or 3) not contain any of {11, 13, 23, 31, 221} as subsequence are either of the form {0}2{0}1 or contain only 0 and 3, thus must be divisible by 3

In base b=5, T={2,3,5,7,11,13,17,23,31,41,47,251,691,887,5081,7219,82609,105367}, see factorization of 1{0}13 in base 5

Code:
prime    use to remove
2 (2)   1{0,4}1, 1{0}3, 11{4}4, 2{0,2,4}2, 2{0,2,4}4, 30{0}01, 33{0}31, 4{4}11, 4{0,2,4}2, 4{0,2,4}4
3 (3)   11{0}3, 3{0,3}11, 3{0,3}3, 1(0^n)13 for all even n (including n=0) and n < 93
10 (5)   all numbers ending with 0
12 (7)   144, 331, 1(0^n)13 for all n == 1 mod 6 and n < 93
21 (11)   3301, 441, 1(0^n)13 for all n divisible by 5 and n < 93
23 (13)   1(0^n)13 for all n == 3 mod 4 and n < 93
32 (17)   3031
43 (23)   1(0^81)13
111 (31)   30031
131 (41)   1(0^17)13, 1(0^57)13, 1(0^77)13
142 (47)   1(0^29)13
2001 (251)   1(0^89)13
10231 (691)   1(0^9)13
12022 (887)   1(0^21)13
130311 (5081)   1(0^41)13
212334 (7219)   1(0^69)13
10120414 (82609)   1(0^33)13
11332432 (105367)   1(0^53)13
In base b=6, T={2,3,5,7,13}; since all numbers not divisible by 2 or 3 (i.e. end with 1 or 5) not contain any of {11, 15, 21, 25, 31, 35, 45, 51, 4401, 4441, 40041} as subsequence (except 441 (divisible by 13) and 4041 (divisible by 7)) are either of the form {0}4{0}1 or contain only 0 and 5, thus must be divisible by 5

 2022-04-07, 03:25 #322 sweety439     "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 338010 Posts Since finding the set T requiring finding the set M(Lb) first, finding T is much harder than finding M(Lb) For b = 8 and b = 9 and b = 12, T contains infinitely many numbers: * For b = 8, T contains the smallest prime factor of 8^(2^n)+1 for all n * For b = 9, T contains the smallest prime factor of (9^n-1)/8 for all prime n, also contain the smallest prime factor of (25*9^n-1)/8, 4*9^n-49, 4*9^n-1, 9^n-4 for all n * For b = 12, T contains the smallest prime factor of 12^n-25 for all even n (for all odd n, the smallest prime factor is 13) Theorem: For all base b, T must contain all primes <= b Proof: For primes p < b, consider the combination of the digits divisible by p (including 0), and for prime p = b, consider the family 1{0} We find the T for b = 10: * T must contain {2,3,5,7} * The smallest prime of the form 2{0}21 is 20021 --> 221 (=13*17) and 2021 (=43*47) must be removed, thus either 13 or 17 is needed, and either 43 or 47 is needed * The smallest prime of the form 22{0}1 is 22000001 --> 221, 2201, 22001, 220001, 2200001 must be removed, thus the primes {13,31,19,73} are needed (7 is already in the set) * The smallest prime of the form 5{5}1 is 555555555551 --> All smaller numbers in this family must be removed * 581 must be removed, but 581 is divisible by 7 and 7 is already in the set * The smallest prime of the form 5{0}27 is 5000000000000000000000000000027 --> All smaller numbers in this family must be removed * The smallest prime of the form 52{0}7 is 5200007 --> 527, 5207, 52007, 520007 must be removed, thus the primes {17,41,131,23} are needed *
 2022-04-08, 11:44 #323 sweety439     "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 D3416 Posts
2022-04-11, 02:13   #324
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

22·5·132 Posts

Quote:
 Originally Posted by sweety439 List of primes of given forms: 1{z}, 2{0}1, {z}y, 1{0}2: (I am now computing ....)
for k = 2:

* A = numbers n such that 2*b^n-1 is prime --> family 1{z}
* B = numbers n such that (2*b^n+1)/gcd(b-1,3) is prime --> for b not == 1 mod 3, family 2{0}1 (for b == 1 mod 3, family 2{0}1 can be ruled out as only contain composite numbers, as all numbers in this family are divisible by 3)
* C = numbers n such that (b^n-2)/gcd(b,2) is prime --> for odd b, family {z}y (for even b, family {z}y can be ruled out as only contain composite numbers, as all numbers in this family are divisible by 2)
* D = numbers n such that (b^n+2)/gcd(b,2)/gcd(b-1,3) is prime --> for b == 3 or 5 mod 6, family 1{0}2 (for b == 1 mod 3, family 1{0}2 can be ruled out as only contain composite numbers, as all numbers in this family are divisible by 3, also, for even b, family 1{0}2 can be ruled out as only contain composite numbers, as all numbers in this family are divisible by 2)

for k = 3:

* A = numbers n such that (3*b^n-1)/gcd(b-1,2) is prime --> for even b, family 2{z} (for odd b, family 2{z} can be ruled out as only contain composite numbers, as all numbers in this family are divisible by 2)
* B = numbers n such that (3*b^n+1)/gcd(b-1,4) is prime --> for even b, family 3{0}1 (for odd b, family 3{0}1 can be ruled out as only contain composite numbers, as all numbers in this family are divisible by 2)
* C = numbers n such that (b^n-3)/gcd(b,3)/gcd(b-1,2) is prime --> for b == 2 or 4 mod 6, family {z}x (for odd b, family {z}x can be ruled out as only contain composite numbers, as all numbers in this family are divisible by 2, also, for b divisible by 3, family {z}x can be ruled out as only contain composite numbers, as all numbers in this family are divisible by 3)
* D = numbers n such that (b^n+3)/gcd(b,3)/gcd(b-1,4) is prime --> for b == 2 or 4 mod 6, family 1{0}3 (for odd b, family 1{0}3 can be ruled out as only contain composite numbers, as all numbers in this family are divisible by 2, also, for b divisible by 3, family 1{0}3 can be ruled out as only contain composite numbers, as all numbers in this family are divisible by 3)
Attached Files
 k=2.txt (13.6 KB, 18 views) k=3.txt (12.9 KB, 18 views)

 2022-04-11, 02:39 #325 sweety439     "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 22·5·132 Posts We can expect the length of the largest minimal prime (start with b+1) in base b, and expect the number of unsolved families in base b when searched to certain limit (e.g. 10000 digits or 50000 digits), like expectations of the length of the largest left truncatable primes in base b and expectations of the length of the largest right truncatable primes in base b There are examples of expectations related to this: https://mersenneforum.org/showpost.p...8&postcount=22 https://mersenneforum.org/showpost.p...0&postcount=20 https://mersenneforum.org/showpost.p...65&postcount=7 https://mersenneforum.org/showthread.php?t=26228 https://oeis.org/A055557/a055557.txt https://listserv.nodak.edu/cgi-bin/w...;417ab0d6.0906 http://www.fermatquotient.com/PrimSerien/GenRepu.txt http://www.fermatquotient.com/PrimSerien/GenRepuP.txt Last fiddled with by sweety439 on 2022-04-11 at 02:42
2022-04-21, 18:25   #326
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

22×5×132 Posts

Attached Files
 minimal primes in bases 2 to 16.pdf (1.79 MB, 35 views)

Last fiddled with by sweety439 on 2022-04-30 at 06:23

2022-05-07, 12:39   #327
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

64648 Posts

Attached Files
 kernel9.txt (3.1 KB, 22 views)

2022-05-08, 14:14   #328
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

22·5·132 Posts

bases 9, 10, 12
Attached Files
 kernel.zip (1.1 KB, 21 views)

2022-05-12, 12:59   #329
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

22·5·132 Posts

The possible length of a prime in the families (in any base b) are: (the length is possible if and only if the corresponding polynomial of the base b satisfies the condition in Bunyakovsky conjecture, and if Bunyakovsky conjecture is true, then there are infinitely many bases b such that the number with these lengths in the families are primes)

1{0}1: length is of the form 2^r+1 (b^n+1 is divisible by b^k+1 if k divides n and n/k is odd > 1, and b^n+1 satisfies both conditions in Bunyakovsky conjecture if n is of the form 2^r)
1{0}2: any length >= 2 (b^n+2 always satisfies both conditions in Bunyakovsky conjecture)
1{0}3: any length >= 2 (b^n+3 always satisfies both conditions in Bunyakovsky conjecture)
1{0}4: length not == 1 mod 4 (b^n+4 = (b^(n/2)-2*b^(n/4)+2) * (b^(n/2)+2*b^(n/4)+2) if n == 0 mod 4, and b^n+4 satisfies both conditions in Bunyakovsky conjecture if n not == 0 mod 4)
1{0}z: length not == 0 mod 6 (b^n+(b-1) has factor b^2-b+1 (z1 in base b) if n == 5 mod 6, and b^n+(b-1) satisfies both conditions in Bunyakovsky conjecture if n not == 5 mod 6)
{1}: length is prime ((b^n-1)/(b-1) is divisible by (b^k-1)/(b-1) if k divides n and k > 1 and n/k > 1 (for k = 1, (b^k-1)/(b-1) = 1), and (b^n-1)/(b-1) satisfies both conditions in Bunyakovsky conjecture if n is prime)
1{z}: any length >= 2 (2*b^n-1 always satisfies both conditions in Bunyakovsky conjecture)
2{0}1: any length >= 2 (2*b^n+1 always satisfies both conditions in Bunyakovsky conjecture)
2{z}: any length >= 2 (3*b^n-1 always satisfies both conditions in Bunyakovsky conjecture)
3{0}1: any length >= 2 (3*b^n+1 always satisfies both conditions in Bunyakovsky conjecture)
3{z}: length == 0 mod 2 (4*b^n-1 = (2*b^(n/2)-1) * (2*b^(n/2)+1) if n == 0 mod 2, and 4*b^n-1 satisfies both conditions in Bunyakovsky conjecture if n == 1 mod 2)
4{0}1: length not == 1 mod 4 (4*b^n+1 = (2*b^(n/2)-2*b^(n/4)+1) * (2*b^(n/2)+2*b^(n/4)+1) if n == 0 mod 4, and 4*b^n+1 satisfies both conditions in Bunyakovsky conjecture if n not == 0 mod 4)
{y}z: any length >= 2 (((b-2)*b^n+1)/(b-1) always satisfies both conditions in Bunyakovsky conjecture)
y{z}: length not == 5 mod 6 ((b-1)*b^n-1 has factor b^2-b+1 (z1 in base b) if n == 4 mod 6, and (b-1)*b^n-1 satisfies both conditions in Bunyakovsky conjecture if n not == 4 mod 6)
z{0}1: length 2 and length not == 2 mod 6 ((b-1)*b^n+1 has factor b^2-b+1 (z1 in base b) if n == 1 mod 6 and n > 1 (for n = 1, (b-1)*b^n+1 is exactly b^2-b+1 (z1 in base b) itself), and (b-1)*b^n+1 satisfies both conditions in Bunyakovsky conjecture if n not == 1 mod 6)
{z}1: length 2 and length not == 2 mod 6 (b^n-(b-1) has factor b^2-b+1 (z1 in base b) if n == 2 mod 6 and n > 2 (for n = 2, b^n-(b-1) is exactly b^2-b+1 (z1 in base b) itself), and b^n-(b-1) satisfies both conditions in Bunyakovsky conjecture if n not == 2 mod 6)
{z}w: length == 1 mod 2 (b^n-4 = (b^(n/2)-2) * (b^(n/2)+2) if n == 0 mod 2, and b^n-4 satisfies both conditions in Bunyakovsky conjecture if n == 1 mod 2)
{z}x: any length >= 2 (b^n-3 always satisfies both conditions in Bunyakovsky conjecture)
{z}y: any length >= 2 (b^n-2 always satisfies both conditions in Bunyakovsky conjecture)

These are the cyclotomic polynomials Phi(n,b) written in base b for n = 1 to 10000, since all cyclotomic polynomials satisfy both conditions in Bunyakovsky conjecture, it is conjectured that there are infinitely many bases b such that the number is prime, the smallest such base b are listed in A085398 (note: 1 cannot be the base of a numeral system)

Interesting things: except GFN and GRU (see this post) (the smallest GFN in base b and the smallest GRU in base b is always both minimal prime (start with b+1) in base b and unique prime in base b (with period length "power of 2" and "prime", respectively), for some bases b, there are other numbers which are both minimal prime (start with b+1) in base b and unique prime in base b (the period length is neither prime nor power of 2)

* z1 (period = 6): see next post (if z1 is prime, then it is always such number, it is interesting not only because unique prime, but also because the Williams families z{0}1 and {z}1, whose 2-digit numbers are both z1)
* z0z1 (period = 10): 12, 20, 37, 38, 47, 71, 126, 131, 157, 158, 180, 223, 251, 257, 268, 276, 342, 361, 363, 375, 377, 385, 388, 438, 452, 462, 487, 507, 551, 588, 603, 628, 641, 652, 658, 676, 693, 707, 716, 738, 758, 760, 768, 782, 791, 792, 812, 850, 935, 973, 978, ... (z0z1 is prime, but z1, z01, zz1 are all composite)
* zz01 (period = 12): 12, 17, 27, 30, 38, 56, 61, 65, 94, 105, 109, 114, 126, 131, 166, 172, 183, 185, 196, 198, 225, 229, 231, 257, 261, 263, 269, 270, 296, 302, 308, 313, 324, 328, 339, 346, 350, 363, 374, 407, 412, 413, 424, 426, 429, 434, 437, 438, 443, 447, 463, 468, 480, 485, 502, 503, 507, 511, 515, 533, 545, 549, 558, 559, 571, 582, 593, 595, 599, 612, 614, 632, 638, 640, 641, 653, 659, 676, 699, 701, 707, 716, 718, 724, 725, 738, 742, 749, 767, 768, 777, 794, 797, 798, 801, 805, 811, 832, 842, 862, 868, 871, 872, 893, 905, 909, 923, 949, 953, 958, 963, 967, 974, 978, 1009, 1015, 1018 (zz01 is prime, but z1, z01, zz1 are all composite)

Code:
b   primes which are both minimal prime (start with b+1) in base b and unique prime in base b
2   11 (3, period 2, both GFN and GRU)
3   12 (5, period 4, GFN), 21 (7, period 6), 111 (13, period 3, GRU)
4   11 (5, period 2, both GFN and GRU), 13 (7, period 3), 31 (13, period 6), 221 (41, period 10, this prime is completely a coincidence, since 41 = Phi(10,4)/gcd(Phi(10,4),10) and gcd(Phi(10,4),10) > 1)
5   12 (7, period 6), 23 (13, period 4, GFN), 111 (31, period 3, GRU)
6   11 (7, period 2, both GFN and GRU), 51 (31, period 6)
7   25 (19, period 3), 61 (43, period 6), 3334 (1201, period 8, GFN), 11111 (2801, period 5, GRU)
8   23 (19, period 6), 111 (73, period 3, GRU)
9   45 (41, period 4, GFN), 81 (73, period 6)
10  11 (11, period 2, both GFN and GRU), 37 (period 3)
11  34 (37, period 6), 61 (period 4, GFN)
12  11 (13, period 2, both GFN and GRU), B0B1 (19141, period 10), BB01 (20593, period 12)
They are usually 2-digit numbers (with period 2, 3, 4, 6) (3 only for bases == 1 mod 3, and 4 only for bases == 1 mod 2), very few > 2-digit numbers.
Attached Files
 cyclotomic.zip (71.6 KB, 10 views)

Last fiddled with by sweety439 on 2022-05-13 at 10:40

 Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 sweety439 139 2022-04-23 20:44 sweety439 Miscellaneous Math 6 2019-11-25 07:37 davar55 Puzzles 13 2018-03-15 14:46 Flatlander Puzzles 40 2011-02-10 09:42 davar55 Puzzles 5 2008-11-02 00:08

All times are UTC. The time now is 17:56.

Fri May 20 17:56:06 UTC 2022 up 36 days, 15:57, 0 users, load averages: 1.56, 1.52, 1.47