<jupyter_start><jupyter_text>"Problem 4: Largest palindrome product"> What is a palindromic number?- permalink: p4- toc: true - badges: true- comments: true- categories: [solution]  🔒 [Problem](https://projecteuler.net/problem=4)A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.Find the largest palindrome made from the product of two 3-digit numbers. 🔐 Key Idea  🔑 Solution 🧭 Initial idea$O(n^2)$ complexity, brute force method.<jupyter_code>ans = 0

n = 999
m = 999

while n > 99:
    while m > 99:
        if str(n * m) == str(n * m)[::-1]:  # check whether the string equals the reversed string
            if n * m > ans:
                ans = n * m  # find the maximum palindromic number
        m -= 1
    n -= 1
    m = 999

print(ans)<jupyter_output>906609<jupyter_text>> NOTE: Would've been a cleaner code with `for i in range(100, 999): ...`.> NOTE: Could've reduced the number of iteration to half by setting `m = n` at the end of `while` statement. It will skip doing redundant calculations such as `999 * 998` and `998 * 999`.  🎲 Difference of 80 method (from *harveyramer* in solution thread)User *harveyramer* discovered the pattern that the two factor that makes the largest palindrome doesn't differ more than 80 numbers in the range. 🔐 Key ideafinding the pattern of the answer and reducing useless iterations<jupyter_code>max = 0
k = 1000
last = 8 * k // 100 + 1  # 80 + 1 when k = 1000

for i in reversed(range(k - last, k)):  # 999, 998, 997, ...
    for j in reversed(range(i + 1 - last, i + 1)):  # i, i - 1, ... i - 80
        n = i * j
        if str(n) == str(n)[::-1]:
            if n > max:
                max = n

print(max)<jupyter_output>906609
{'fraction_non_alphanumeric': 0.10953461975028377, 'fraction_numerical': 0.055051078320090804, 'mean_word_length': 2.935267857142857, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 14, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '241786', 'license': 'Apache-2.0', 'n_tokens_mistral': 680, 'n_tokens_neox': 566, 'n_words': 246, 'path': '_notebooks/2021-06-16-p4.ipynb', 'repo_name': 'ntcho/project_euler_blog', 'size': '1762'}