Wikipedia:Reference desk/Archives/Mathematics/2023 May 20

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.

May 20

For which natural numbers n, this sequence contains infinitely many primes?

For which natural numbers n, the sequence n*(generalized pentagonal numbers)+1 (i.e. n+1, 2*n+1, 5*n+1, 7*n+1, 12*n+1, 15*n+1, 22*n+1, 26*n+1, ...) contains infinitely many primes? Assuming Bunyakovsky conjecture is true.

I think that for all natural numbers n except 24, 25, 27, 32, this sequence contains infinitely many primes, for these four values of n, this sequence contains no primes because:

• generalized pentagonal numbers * 24 + 1 are always squares
• generalized pentagonal numbers * 25 + 1 are always generalized pentagonal numbers
• generalized pentagonal numbers * 27 + 1 are always triangular numbers
• generalized pentagonal numbers * 32 + 1 are always generalized octagonal numbers

And all generalized polygonal numbers (other than the trivial cases, i.e. the generalized pentagonal numbers 1, 2, 5, 7, the triangular numbers 1, 3, the generalized octagonal numbers 1, 5) are composite. 211.75.79.246 (talk) 00:19, 20 May 2023 (UTC)

Note that the Bunyakovsky conjecture still holds if we change the third condition so that $f(0),f(1),f(2),\ldots$ have no common factor. This is because if $P(x)$ satisfies the two normal conditions and the one modified condition, then $P(x-1)$ satisfies all three normal conditions and produces infinitely many primes, implying that $P(x)$ produces infinitely many primes.

Now, onto the actual problem. First things first, we have to formalize this in terms of polynomials. Since we are using generalized pentagonal numbers, we have to actually consider two polynomials over positive $k$:

$P_{+}(k)={\frac {3n}{2}}k^{2}-{\frac {n}{2}}k+1$

$P_{-}(k)=P_{+}(-k)={\frac {3n}{2}}k^{2}+{\frac {n}{2}}k+1$

We can notice right away that when $n$ is even, this is an integer-coefficient polynomial, which the Bunyakovsky conjecture can handle, no problem. For odd $n$, however, we have to split into odd and even inputs to get:

$P^{o}(k)=P(2k-1)$

$P^{e}(k)=P(2k)$

where $P$ refers to either $P_{+}$ or $P_{-}$.

The first condition is easily satisfied by all polynomials under consideration. The third condition is satisfied by even $n$ and odd $n$ on even inputs, as their values at $0$ are always $1$. For odd $n$ and odd inputs, we would have to spend some more effort to prove that there are no shared factors. Luckily, however, we don't have to do that.

The reason why we don't is because of the second condition. In particular, for odd $n$, $P^{o}(k)$ is irreducible over the rationals if and only if $P^{e}(k)$ is also irreducible over the rationals. So if $P^{e}(k)$ is irreducible, then $P^{e}(k)$ generates infinitely many primes, and thus so does $P(k)$, and if $P^{e}(k)$ is reducible, then so is $P^{o}(k)$, and $P(k)$ does not produce infinitely many primes. In other words, for odd $n$, $P(k)$ generates infinitely many primes if and only if $P^{e}(k)$ is irreducible.

Now all we need to point out is that $P_{-}(k)=P_{+}(-k)$ is irreducible if and only if $P_{+}(k)$ is, and also $P^{e}(k)$ is irreducible if and only if $P(k)$ is, to prove that, really, for all $n$ regardless of parity, the sequence written in the question generates infinitely many primes if and only if $P_{+}(k)$ is irreducible over the rationals. Solving the quadratic yields roots of the form:

${\frac {1}{6}}\pm {\frac {1}{6}}{\sqrt {1-{\frac {24}{n}}}}$

so for our constant input $n$, the sequence produces infinitely many primes if and only if ${\sqrt {1-24/n}}$ is irrational.

Now, if $n-24$ is $0$, then naturally ${\sqrt {1-24/n}}=0$ is rational. With that out of the way, if we take $n>24$, then $n-24>1$, and we can consider the highest common factor of $n-24$ and $n$.

If $n-24$ and $n$ are coprime, then naturally $1-24/n$ is the square of a rational if and only if both $n-24$ and $n$ are squares of integers. This is only the case if $n=25,49$.

If $n-24$ and $n$ share a highest common factor of $2$, then writing $n=2n'$ and using the same argument as before, since $n'-12$ and $n'$ are squares of integers if and only if $n'=16$, we get that $n=32$.

By the same method, $n-24$ and $n$ sharing a highest common factor of $3$ yields a solution of $n=27$.

Highest common factors of $4,12$ yield nothing. Highest common factors of $6,8,24$ yield repeat answers.

We conclude that the only $n$ for which the sequence does not produce infinitely many primes are $n=24,25,27,32,49$. This is the same as the supplied list, with the addition of $49$. GalacticShoe (talk) 21:50, 21 May 2023 (UTC)

While generalized pentagonal numbers * 49 + 1 are of the form $(21n\pm 1)(7n\pm 2)/2$, and are thus a subset of numbers that are of the form $(3n\pm 1)(n\pm 2)/2$, I don't think this sequence corresponds to any (generalized) sequence of figurate numbers. GalacticShoe (talk) 22:42, 21 May 2023 (UTC)

generalized pentagonal numbers * 32 + 1 are 1, 33, 65, 161, 225, 385, 481, 705, 833, …, all of these numbers are generalized octagonal numbers, see OEIS: A001082 211.75.79.246 (talk) 07:08, 22 May 2023 (UTC)

Whoops, typo; I meant 49. I've corrected the error. GalacticShoe (talk) 19:01, 22 May 2023 (UTC)

Can numbers of this form be squares?

Numbers of the form 777…7776 cannot be squares, since such numbers are == 6 mod 7 and == 6, 10 mod 11, but can numbers of the form 555…5556 be squares? I cannot find any moduli to prove that such numbers cannot be squares. 211.75.79.246 (talk) 00:21, 20 May 2023 (UTC)

Another, much more brute-force way of proving there are no 777...6 squares is to observe that none of 6, 76, 776, 7776 and 77776 are squares, while no square has residue 777776 modulo 10⁶. This approach also works to prove that 16 is the only 111...6 square (6 and 116 are not squares and residue 1116 mod 10⁴ is excluded) and that 36 is the only 333...6 square (6 and 336 are not squares and residue 3336 mod 10⁴ is excluded). However, this way of attack too fails for 555...6: arbitrarily long 555...6 residues are provided by squares of the form ((250 × 10ⁿ + 2) / 3)².  --Lambiam 08:02, 20 May 2023 (UTC)

9 × 555...6 = 5000...4, so some 555...6 is square iff some number of the form 50 × 10ⁿ + 4 is a square number. While not a solution, I think this form is easier to examine.  --Lambiam 08:16, 20 May 2023 (UTC)

If 50 × 10ⁿ + 4 = r ², we have

2ⁿ⁺¹5ⁿ⁺² = (50 × 10ⁿ + 4) − 4 = r ² − 4 = (r − 2)(r + 2).

The value 5 cannot be a factor of both r − 2 and r + 2, so all factors 5 are in one of the two. The other r ± 2 is then a power of 2, so r is even. That is how far I've got by now.  --Lambiam 08:45, 20 May 2023 (UTC)

Note that for n=-1 the value _is_ a square, so the real problem is to prove there aren't any additional squares. Proving something occurs exactly once might be more difficult than proving something can't happen at all. --RDBury (talk) 16:30, 20 May 2023 (UTC)

I don't think of 9 as an instance of 5000...4, so I intended n to be a natural number, which for me includes 0. That is also why I used "50" and not "5".  --Lambiam 16:57, 20 May 2023 (UTC)

Here is a proof of impossibility. Assume some number 5000...4 is a square, or, in a formula, 50 × 10ⁿ + 4 = r ². Then we have

2ⁿ⁺¹5ⁿ⁺² = (50 × 10ⁿ + 4) − 4 = r ² − 4 = (r − 2)(r + 2).

The value 5 cannot be a factor of both r − 2 and r + 2, so all factors 5 of the prime factorization of r ² − 4 are in one of the two factors of this decomposition. We can write these two factors as

2^p         = r − t  and

2^q 5ⁿ⁺² = r + t,

where p + q = n + 1 and t = ± 2.

It is easy to see that p cannot be equal to 1 or 2, since neither of the products 2 × 6 and 4 × 8 yields a value of the form 50 × 10ⁿ. Since, for p ≥ 3, the factorization of r + t = 2^p + 2t  contains exactly two factors 2 and is also of the form 2^q 5ⁿ⁺², we conclude that q = 2. Then 2^p = 4 × 5ⁿ⁺² − 2t.

Using q = 2 and p + q = n + 1, we need to solve

2ⁿ⁻¹ = 4 × 5ⁿ⁺² − 2t.

Clearly, the left hand side is always strictly less than the right hand side, so the equation is unsatisfiable.  --Lambiam 17:05, 20 May 2023 (UTC)

Okay, another question, does there exist a square number containing only digits 5 and 6? 211.75.79.246 (talk) 07:10, 22 May 2023 (UTC)

Probably not. OEIS:A018884 (Squares using at most two distinct digits, not ending in 0) says there are none below 10⁴¹, but it's one of 21 two-digit combinations which aren't ruled out. PrimeHunter (talk) 13:41, 22 May 2023 (UTC)

A probability-based heuristic suggests that the set represented by A018884 is finite, and that it is unlikely there are any more than those already found.  --Lambiam 16:58, 22 May 2023 (UTC)