TAOCP 7.2.2.2 Exercise 46

Exercise 46. [30] $[30]$ Find the largest perfect square less than $2^{100}$ that is a binary palindrome.

Verified: no
Solve time: 11m46s

Correctness

The solution gives a candidate square and correctly checks that the proposed number is a binary palindrome. It also correctly reduces the search to square roots satisfying $y<2^{50}$.

However, the exercise asks for the largest such square, so the solution must prove that no larger perfect square below $2^{100}$ has a palindromic binary representation. The proposed solution does not provide a self-contained argument for this exclusion. It relies on the statement that an "exhaustive generation" of palindromic-square roots produces the largest candidates, but the generation procedure, completeness argument, and verification are not supplied.

The construction part is therefore essentially correct: the number

$$ 90859797323621704030788342601 $$

does appear to be a valid binary palindromic square. The extremal proof, however, is incomplete.

Gaps and Errors

The main issue occurs in the sentence:

"The exhaustive generation of the binary palindromic-square roots below $2^{50}$ gives the largest three candidates..."

This is an unsupported claim. The solution does not describe the enumeration method, prove that it considers every possible binary palindrome below $2^{100}$, or prove that the listed candidates are consecutive elements of the relevant sequence.

This is a Critical error for an optimization problem. The candidate may be correct, but the argument does not establish maximality.

A second unsupported claim appears earlier:

"The numbers $y$ with this property are the binary palindromic-square roots. The relevant increasing sequence begins ..."

The sequence values are quoted without derivation or proof. Using a known sequence is not itself invalid, but a TAOCP solution must justify why the quoted finite portion suffices. The solution never explains how these values were obtained or why no missing terms occur between the listed values.

This is a Justification gap if the sequence is being used as an externally verified computational result, but without that external computation the gap becomes part of the critical maximality failure.

The verification of the binary palindrome is also somewhat incomplete. The decimal square is stated, and a binary representation is stated, but the solution does not independently check that the binary string corresponds to the decimal value. This is a minor Justification gap, since the central issue is maximality rather than the arithmetic conversion.

The final statement:

"Hence no root larger than $301429589329949$ can produce a square below $2^{100}$ with palindromic binary expansion."

does not follow from the preceding argument unless the completeness of the enumeration has already been established. The inequality alone only eliminates the next listed candidate, not all possible larger roots.

Summary

The proposed answer identifies a plausible correct extremal value and verifies that it is a binary palindromic square, but it does not prove that it is the largest one. The missing exhaustive-search argument is essential because the problem is an optimization problem requiring both construction and a lower-bound or exclusion argument.

VERDICT: FAIL, the solution's maximality claim depends on an unproved exhaustive enumeration of all possible palindromic-square roots below $2^{50}$.