PHP 尋找區間內回文數且平方根亦為回文數：數學優化與效能調校

問題定義

給定區間 [X, Y]，找出所有滿足條件的數 N：

1. N 是回文數
2. N 是完全平方數
3. √N 也是回文數

條件 2+3 等價於：√N 是回文數，且 N = (√N)² 也是回文數。

關鍵優化：縮小搜尋空間

直接檢查 [X, Y] 內每個數極其低效。改為：

1. 計算 √X 與 √Y
2. 僅檢查 [√X, √Y] 區間內的整數 i
3. 若 i 是回文數，且 i² 也是回文數，則 i² 為解

搜尋空間從 Y-X 縮減至 √Y - √X，指數級優化。

完整實作

<?php
/**
 * 判斷整數是否為回文數
 */
function isPalindrome(int $num): bool {
    $str = (string)$num;
    $len = strlen($str);
    for ($i = 0; $i < $len / 2; $i++) {
        if ($str[$i] !== $str[$len - 1 - $i]) return false;
    }
    return true;
}

/**
 * 尋找區間內雙重回文平方數
 * @return array 符合條件的數列表
 */
function findDoublePalindromeSquares(int $min, int $max): array {
    $results = [];
    
    // 邊界處理
    if ($min < 1) $min = 1;
    if ($max < $min) return $results;
    
    $start = (int)ceil(sqrt($min));
    $end = (int)floor(sqrt($max));
    
    for ($i = $start; $i <= $end; $i++) {
        if (isPalindrome($i)) {
            $square = $i * $i;
            if (isPalindrome($square)) {
                $results[] = [
                    'root' => $i,
                    'square' => $square,
                    'root_palindrome' => true,
                    'square_palindrome' => true,
                ];
            }
        }
    }
    
    return $results;
}

// 測試：1 到 10^14
$startTime = microtime(true);
$results = findDoublePalindromeSquares(1, 100_000_000_000_000);
$elapsed = microtime(true) - $startTime;

echo "找到 " . count($results) . " 個雙重回文平方數\n";
echo "耗時：{$elapsed} 秒\n\n";

foreach ($results as $r) {
    echo "√{$r['square']} = {$r['root']} (雙方皆為回文數)\n";
}

// 已知序列 (OEIS A057135): 1, 4, 9, 121, 484, 10201, 12321, 14641, 40804, 44944, 1002001, 1234321, 4008004, 100020001, 102030201, 104060401, 121242121, 123454321, 125686521, 400080004, 404090404, 10000200001, 10221412201, 12102420121, 12345654321, 40000800004, 1000002000001, 1002003002001, 1004006004001, 1020304030201, 1022325232201, 1024348434201, 1210024200121, 1212225222121, 1214428244121, 1232346432321, 1234567654321, 4000008000004, 100000020000001, ...
?>

效能分析

進階優化：回文數生成器（避免逐一檢查）

/**

 * 生成指定長度的回文數
 * @param int $halfLength 前半段長度
 * @param bool $oddLength 是否為奇數長度
 * @return Generator
 */
function generatePalindromes(int $halfLength, bool $oddLength = false): Generator {
    $start = 10 ** ($halfLength - 1);
    $end = (10 ** $halfLength) - 1;
    
    for ($half = $start; $half <= $end; $half++) {
        $halfStr = (string)$half;
        $rev = strrev($halfStr);
        if ($oddLength) {
            // 奇數長度：中間數字不重複
            for ($mid = 0; $mid <= 9; $mid++) {
                yield (int)($halfStr . $mid . $rev);
            }
        } else {
            // 偶數長度
            yield (int)($halfStr . $rev);
        }
    }
}

// 使用生成器直接產生回文根，再檢查平方
function findDoublePalindromeFast(int $min, int $max): array {
    $results = [];
    $maxRoot = (int)floor(sqrt($max));
    $maxLen = strlen((string)$maxRoot);
    
    for ($len = 1; $len <= $maxLen; $len++) {
        $halfLen = (int)ceil($len / 2);
        $isOdd = $len % 2 === 1;
        
        foreach (generatePalindromes($halfLen, $isOdd) as $root) {
            if ($root > $maxRoot) break 2;
            $square = $root * $root;
            if ($square < $min) continue;
            if (isPalindrome($square)) {
                $results[] = ['root' => $root, 'square' => $square];
            }
        }
    }
    return $results;
}

結語

雙重回文平方數問題核心在於「搜尋平方根而非平方數」，將複雜度從 O(Y) 降至 O(√Y)。進一步使用回文數生成器可僅遍歷回文數，效能再提升數量級。此類數學優化思維適用於許多數論相關問題。