Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
I don't have an intuition either way. Having infinitely many solutions is not sufficient because all of them might have the same obstacle with the stray 2, but it would be quite interesting if that were in fact the case.
In the same question, Elkies gives a solution to $X^4 - Y^4$ is powerful, but it's not a solution to this problem solely because $\nu_2(X^2 + Y^2) = 1$.
It appears that the typical maximum one-free multisets contain few distinct elements each with multiplicity one less than its order, and that makes some intuitive sense because repeating an element as much as possible reduces the number of distinct products. Thus one strategic idea we can take is to test multisets of this form first in order to get lower bounds.
OEIS A000043 notes that "It is believed (but unproved) that this sequence is infinite." A proof of your claim would also be a proof that there are infinitely many Mersenne primes, since otherwise $\pi$ must be rational. Therefore either the answer is "No, no-one can provide a proof" or OEIS needs to be updated.
By extending the Pochhammer symbol one step more and cancelling out, it's possible to subsume the leading $4$ as the $n=0$ term, which IMO is more elegant: $$\frac{\pi}{4} = \sum_{n=0}^\infty \frac{1 - 4\lambda - 2n}{(2n+1)(1 - 4\lambda + 4n^2)} \binom{\frac{4n^2 - 4\lambda + 1}{4n+4\lambda}}{n}$$
I think you've missed the offset when converting from the Pochhammer symbol (which is a notation I avoid because IMO it's easier to misread than to read correctly) to the binomial: I think it should be $$\frac{\pi}{4} = \sum_{n=0}^\infty \frac{1 - 2n}{(2n+1)(1 + 4n^2)} \binom{\frac{4n^2 + 1}{4n}}{n}$$
@ClaudeLeibovici, the value $\lambda=\frac14$ also looks interesting because it allows some simplification: we get $$\frac{\pi}{4} = \sum_{n=0}^\infty \frac{- 1}{2n(2n+1)} \binom{\frac{4n^2}{4n+1}}{n}$$
Not quite an arbitrary complex number: it needs to avoid the poles at negative integers. Also worth noting (as they do in the paper) that the $\lambda \to \infty$ limit gives the Leibniz formula, which may be useful in literature searches.
@fedja, I can't figure out that step either. It seems like a plausible starting point for hill-climbing, but your DP approach looks more promising to me.
In response to your question about n-ary search requiring sorted arrays, I think the concept here is to preprocess your array into an array of prefix sums and then search for the appropriate fractions of the total sum.
It's hard to find squares in the recurrence, but to lower bound them it's quite straightforward to test for quadratic residues against a number of small primes. Using the $24$ largest primes under $10^6$ for a first filter and then testing any which pass that against odd primes from 3 until rejection, with 3 hours of runtime I calculate that $n > 8000000000$, which gives a lower bound for $c$ on the order of $10^{12248800000}$.
