Wikipedia:Reference desk/Archives/Mathematics/2023 September 25

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 25

Are there infinitely many primes of the form 1000…0007, 333…3331, 7111…111, or 3444…4447 in base 10?

Are there infinitely many primes of the form 1000…0007, 333…3331, 7111…111, or 3444…4447 in base 10? (i.e. are (sequence A088274 in the OEIS) and (sequence A055557 in the OEIS) and (sequence A056719 in the OEIS) and (sequence A102969 in the OEIS) infinite?) Are there infinitely many primes of the form 3*2^n+1, 3*2^n-1, 2^n+3, or 2^n-3 (they are primes of the form 11000…0001, 10111…111, 1000…00011, 111…11101, respectively, in base 2)? In general, give a base b and a digit d and two strings (may be empty) x and y, are there infinitely many primes of the form xddd…dddy in base b? I know that, like Bunyakovsky conjecture and Schinzel's hypothesis H, some conditions (divisible by small primes or have an algebraic factorization) are necessary, e.g.

1. There are no primes of the form 9444…4449 in base 10, since all such numbers are divisible by 3, 7, 11, or 13.
2. There are no primes of the form 2777…777 in base 9 (not count the prime 2), since all such numbers are divisible by either 2 or 5.
3. There are no primes of the form 3888…888 in base 9 (not count the prime 3), since all such numbers have a difference of two squares factorization.
4. There are no primes of the form 1000…0001 in base 8, since all such numbers have a sum of two cubes factorization.
5. There are no primes of the form BBB…BBB9B in base 12, since all such numbers are either divisible by 13 or have a difference of two squares factorization.
6. There are no primes of the form 8DDD…DDD in base 14, since all such numbers are either divisible by 5 or have a difference of two squares factorization.

And thus I made a conjecture like Bunyakovsky conjecture and Schinzel's hypothesis H:

If b >= 2 and d is a digit in base b and x and y are two strings (may be empty) of the base b digits, there are infinitely many primes of the form xddd…dddy in base b unless it can be proved that there are no primes or only finitely many primes of this form, by the divisible by small primes or the algebraic factorizations, or a combination of them.

This conjecture is that the conditions above are not only necessary but also sufficient, can someone prove or disprove this conjecture (I think that this conjecture may be more difficult to prove than Schinzel's hypothesis H, but I really don’t know why this conjecture is not as famous as Schinzel's hypothesis H, and does not have an official name?)? 118.170.53.159 (talk) 02:33, 25 September 2023 (UTC)

Many such sequences probably have infinitely many primes but it hasn't been proved for any of them. "Small primes" is too vague for a conjecture but it's probably false even if we allow any finite set of primes. Fermat number says:

"If 2^k + 1 is prime and k > 0, then k itself must be a power of 2, so 2^k + 1 is a Fermat number; such primes are called Fermat primes."

Fermat numbers 2²ⁿ+1 grow so fast that there are probably only the five known primes for n = 0 to 4. It's similar for generalized Fermat primes with other bases. For example, 10^k + 1 is prime for k = 0 to 2 but probably no other value. k>0 has to be a power of 2. PrimeHunter (talk) 00:54, 26 September 2023 (UTC)

Well, “small primes” is really vague for a conjecture, indeed, I meant finite covering congruence (just like 78557*2^n+1, see Sierpinski number), like the fixed prime factor in Bunyakovsky conjecture and Dickson's conjecture and Schinzel's hypothesis H, for polynomial sequence, the conditions only need to consider the fixed prime factors and the algebraic factors, but for the exponential sequences xddd…dddy, the conditions need to consider the covering congruence with finite prime factors and the algebraic factors, in polynomial sequences (Schinzel's hypothesis H) it is not possible for covering congruence with more than one prime factor, even need to consider the combination of them, such as 12^n-25, which is divisible by 13 if n is odd and has a difference of two squares factorization if n is even, such situation does not exist in polynomial sequences (Schinzel's hypothesis H). 220.132.230.56 (talk) 04:05, 26 September 2023 (UTC)

So this conjecture is true for all such sequences which does not have a Fermat number behavior and is false for all such sequences which have a Fermat number behavior, the sequences which have a Fermat number behavior are the generalized Fermat numbers sequences b^n+1, i.e. 1000…0001 in even bases (in odd bases all numbers of the form 1000…0001 are divisible by 2), and their subsets (e.g. 2000…0001 and 4000…0001 in base 8, and 2000…0001, 4000…0001, 8000…0001, G000…0001 in base 32), also generalized half Fermat sequences (b^n+1)/2 with odd b, i.e. 111…1112 in base 3, 222…2223 in base 5, 333…3334 in base 7, 444…4445 in base 9, etc. and their subsets (e.g. 1DDD…DDDE and 4DDD…DDDE in base 27), maybe I need to make a new conjecture, i.e. the conjecture is true if and only if the sequence is not generalized Fermat numbers sequence or generalized half Fermat numbers sequence, or their subset. 220.132.230.56 (talk) 04:11, 26 September 2023 (UTC)

An interesting one is 5777…777 in base 11, its first prime (not count the prime 5) is 5777…777 with 62668 7’s, this number has 65263 digits in decimal, since this number is too large to be proved primality (and neither N-1 nor N+1 is trivially fully factored), it is only a probable prime. 220.132.230.56 (talk) 04:14, 26 September 2023 (UTC)

Prime numbers are not base dependent and many serious mathematicians dislike base-dependent things but like theorems and conjectures to be very general. Your number sequences can be written as (k×bⁿ+c)/d for fixed k, b, c, d. For example, 9444...4449 = (85×10ⁿ+41) / 9. I think a general conjecture about when such exponential sequences will produce infinitely many primes would be more interesting and have better chance to become widely known. All sequences of "random" numbers with such growth are expected to give infinitely many primes based on a random x having primality chance 1/log(x) per prime number theorem. The challenge for a plausible conjecture is to identify all conditions which can prevent a sequence from behaving sufficiently randomly. Keeping the case of generalized Fermat numbers in mind, this may mean that if there are sequence members x without a systematic way to get a factor then they must grow so fast that their sum of 1/log(x) becomes finite. If they are known to avoid a certain finite set of prime factors then their primality chance only increases by a constant factor and it doesn't affect whether the sum is finite. I'm not trying to find all conditions for such a conjecture and don't know whether others have tried. I suspect a proof of the conjecture may be harder than Schinzel's hypothesis H. PrimeHunter (talk) 14:00, 26 September 2023 (UTC)

So you think that this conjecture is true? And why this conjecture is not as famous as Schinzel's hypothesis H, and does not have an official name? 220.132.230.56 (talk) 02:25, 27 September 2023 (UTC)

I didn't make an actual conjecture but basically just said there will probably be infinitely many primes unless there is something preventing it. An actual conjecture would have to be speific about what can prevent it, preferably a list of things which can all be tested relatively easy for a given expression. PrimeHunter (talk) 13:29, 27 September 2023 (UTC)

As I said, I think that only covering congruence and algebraic factorization and a combination of them can prevent (k×bⁿ+c)/d to have infinitely many primes, this is exactly my conjecture. 220.132.230.56 (talk) 15:12, 27 September 2023 (UTC)

A precise conjecture should clarify the possible ways to have algebraic factorizations. I'm not sure that's simple. And the Generalized Fermat case shows a third "way" to probably get a finite number of primes: The other ways leave so few candidates that the sum of 1/log(x) is finite. PrimeHunter (talk) 19:10, 27 September 2023 (UTC)

Well, an example is 64*b^n+1 for any b, if n is divisible by 3 or/and by 4, than 64*b^n+1 have algebraic factorization and thus cannot be prime. 220.132.230.56 (talk) 02:17, 28 September 2023 (UTC)

But for generalized Fermat numbers there is still no proof, unlike the forms with covering congruence and algebraic factorization and a combination of them (such as 12^n-25) there is a know proof, so for generalized Fermat numbers there is still no way to ruled out them (except the cases like 8*128^n+1, which have no possible prime since 7n+3 cannot be power of 2). 220.132.230.56 (talk) 02:19, 28 September 2023 (UTC)

Alternate calendar algorithms

Do other calendars (excluding the Gregorian and Julian calendars) have anything similar to the Doomsday algorithm, where I can plug the dates into some equation and find out the day of the week? Primal Groudon (talk) 04:23, 25 September 2023 (UTC)

Any hypothetical calendar system with the same months (Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec) and month lengths (31, 28/29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31) as the Gregorian and Julian calendars would have a similar Doomsday algorithm. So, the algorithm would also work in the Revised Julian calendar (where the rule for century leap years is that year mod 900 $\in \{200,600\}$). The only difference in the Revised Julian calendar is that there are 14 possible dominical letters for century years (in contrast with the Gregorian calendar, where only BA (= 0 mod 400), C (= 100 mod 400), E (= 200 mod 400), and G (= 300 mod 400) are possible). GeoffreyT2000 (talk) 14:15, 25 September 2023 (UTC)

I’m inclined to say that the Milanković calendar doesn’t count. My intention was to find out if other calendars (Coptic, Ethiopian, Hebrew, Chinese, Hijri, Solar Hijri, Mesoamerican Long Count, etc) have any algorithms that serve a similar function as the Doomsday algorithm. Primal Groudon (talk) 01:57, 2 October 2023 (UTC)

I had a look round when the answer to this question came up. One thing I noticed in relation to the lunar calendar of the Eastern Orthodox Church Wikipedia:Reference desk/Archives/Humanities/2023 June 1#Japanese rokuyō (6-day cycle), which is typical of lunar calendars generally, is that any five-month period beginning with a "hollow" (29-day) month generally contains exactly 21 weeks. This is different from the normal calendar, in which any period of five months which does not include the transition from February to March always contains 153 days, a relationship which is the basis of the formula for calculating the number of days in any month Calendrical calculation#Examples. 2A02:C7B:225:5200:D81E:ADD:CE57:73E9 (talk) 10:52, 2 October 2023 (UTC)

2+2

There are no primes of the form 9444…4449 in base 10, since all such numbers are divisible by 3, 7, 11, or 13. 181.205.22.11 (talk) 21:34, 25 September 2023 (UTC)

Yes, this is called a covering set.Your example is listed in that article:

• (85·10ⁿ + 41) / 9 or 94⁺9

Do you have a question? PrimeHunter (talk) 23:51, 25 September 2023 (UTC)

The IP copied this sentence literally from a question posed above by a different IP.  --Lambiam 04:16, 26 September 2023 (UTC)