Largest palindrome product: Difference between revisions
(add FreeBASIC) |
|||
Line 468:
Largest palindromic product of two 6-digit integers: 999001 × 999999 = 999000000999
Largest palindromic product of two 7-digit integers: 9997647 × 9998017 = 99956644665999</pre>
=={{header|Phix}}==
Translated from python by Lucy_Hedgehog as found on page 5 of the project euler discussion page (dated 25 Sep 2011),
and further optimised as per the C# comments (on this very rosettacode page).
<!--<lang Phix>(phixonline)-->
<span style="color: #000080;font-style:italic;">-- demo\rosetta\Largest_palindrome_product.exw</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1.0.1"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (mpz_fdiv_qr(), mpz_si_sub() added to mpfr.js, mpz_mod_ui(), mpz_fdiv_q_ui(), mpz_fdiv_r(), mpz_fdiv_ui() fixed)</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">ispalindrome</span><span style="color: #0000FF;">(</span><span style="color: #004080;">mpz</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">==</span> <span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">inverse</span><span style="color: #0000FF;">(</span><span style="color: #004080;">mpz</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Compute the modular inverse of x modulo power(10,m).
-- Return -1 if the inverse does not exist.
-- This function uses Hensel lifting.</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">}[</span><span style="color: #7060A8;">mpz_fdiv_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">!=-</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">ax</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ax</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_mod_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ax</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ax</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_cmp_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ax</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)==</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">mpz_si_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ax</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ax</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ax</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ax</span><span style="color: #0000FF;">,</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_fdiv_q_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ax</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ax</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">a</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">pal2</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">mpz</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">best</span><span style="color: #0000FF;">,</span><span style="color: #000000;">factor</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_inits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">4</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">even</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">// (as per the C# comments)</span>
<span style="color: #7060A8;">mpz_ui_pow_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">factor</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_sub_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">factor</span><span style="color: #0000FF;">,</span><span style="color: #000000;">factor</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_ui_pow_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">best</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">best</span><span style="color: #0000FF;">,</span><span style="color: #000000;">best</span><span style="color: #0000FF;">,</span><span style="color: #000000;">factor</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">best</span><span style="color: #0000FF;">,</span><span style="color: #000000;">best</span><span style="color: #0000FF;">,</span><span style="color: #000000;">factor</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ispalindrome</span><span style="color: #0000FF;">(</span><span style="color: #000000;">best</span><span style="color: #0000FF;">))</span>
<span style="color: #7060A8;">mpz_ui_pow_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">factor</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_sub_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">factor</span><span style="color: #0000FF;">,</span><span style="color: #000000;">factor</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ispalindrome</span><span style="color: #0000FF;">(</span><span style="color: #000000;">factor</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">else</span>
<span style="color: #000080;font-style:italic;">// Get a lower bound:</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">mpz</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">maxf</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxf11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">minf</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxy</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_inits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">7</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">mpz_ui_pow_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">maxf</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_sub_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">maxf</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxf</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_sub_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">maxf11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxf</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_fdiv_q_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">maxf11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxf11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">22</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">maxf11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxf11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">22</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_add_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">maxf11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxf11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_ui_pow_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">minf</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">minf</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxf</span><span style="color: #0000FF;">,</span><span style="color: #000000;">minf</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_add_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">minf</span><span style="color: #0000FF;">,</span><span style="color: #000000;">minf</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">best</span><span style="color: #0000FF;">,</span><span style="color: #000000;">minf</span><span style="color: #0000FF;">,</span><span style="color: #000000;">minf</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_set_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">factor</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">// This palindrome starts with k 9's.
// Hence the largest palindrom must also start with k 9's and
// therefore end with k 9's.
// Thus, if p = x * y is the solution then
// x * y + 1 is divisible by m.</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (should not exceed 1e8)</span>
<span style="color: #7060A8;">mpz_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxf11</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">while</span> <span style="color: #7060A8;">mpz_cmp_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)>=</span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxf</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_cmp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">best</span><span style="color: #0000FF;">)=-</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ry</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">inverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ry</span><span style="color: #0000FF;">!=-</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">mpz_add_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">maxy</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxf</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">-</span><span style="color: #000000;">ry</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxy</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">while</span> <span style="color: #7060A8;">mpz_cmp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">best</span><span style="color: #0000FF;">)></span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ispalindrome</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">mpz_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">best</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">factor</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">mpz_sub_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">22</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_cmp_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">factor</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">mpz_fdiv_qr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">best</span><span style="color: #0000FF;">,</span><span style="color: #000000;">factor</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_cmp_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">best</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">factor</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">fmt</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"Largest palindromic product of two %d-digit integers: %s = %s x %s (%s)\n"</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">12</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">mpz</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pal2</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">sp</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">sx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">sy</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t1</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fmt</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sy</span><span style="color: #0000FF;">,</span><span style="color: #000000;">e</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</lang>-->
{{out}}
<pre>
Largest palindromic product of two 2-digit integers: 9009 = 99 x 91 (0s)
Largest palindromic product of two 3-digit integers: 906609 = 913 x 993 (0s)
Largest palindromic product of two 4-digit integers: 99000099 = 9999 x 9901 (0s)
Largest palindromic product of two 5-digit integers: 9966006699 = 99979 x 99681 (0s)
Largest palindromic product of two 6-digit integers: 999000000999 = 999999 x 999001 (0s)
Largest palindromic product of two 7-digit integers: 99956644665999 = 9997647 x 9998017 (0.0s)
Largest palindromic product of two 8-digit integers: 9999000000009999 = 99999999 x 99990001 (0s)
Largest palindromic product of two 9-digit integers: 999900665566009999 = 999920317 x 999980347 (0.8s)
Largest palindromic product of two 10-digit integers: 99999000000000099999 = 9999999999 x 9999900001 (0s)
Largest palindromic product of two 11-digit integers: 9999994020000204999999 = 99999996349 x 99999943851 (0.1s)
Largest palindromic product of two 12-digit integers: 999999000000000000999999 = 999999999999 x 999999000001 (0s)
</pre>
After that it starts to struggle a bit:
<pre>
Largest palindromic product of two 13-digit integers: 99999963342000024336999999 = 9999996340851 x 9999999993349 (40.4s)
Largest palindromic product of two 14-digit integers: 9999999000000000000009999999 = 99999999999999 x 99999990000001 (0s)
Largest palindromic product of two 15-digit integers: 999999974180040040081479999999 = 999999998341069 x 999999975838971 (1 minute and 12s)
Largest palindromic product of two 16-digit integers: 99999999000000000000000099999999 = 9999999999999999 x 9999999900000001 (0s)
</pre>
=={{header|Raku}}==
|
Revision as of 08:28, 7 November 2021
- Task
Task description is taken from Project Euler (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.
- Stretch Goal
Find the largest palindrome made from the product of two n-digit numbers, where n ranges from 4 to 7.
- Extended Stretch Goal
Find the largest palindrome made from the product of two n-digit numbers, where n ranges beyond 7,
ALGOL 68
<lang algol68>BEGIN # find the highest palindromic multiple of various sizes of numbers #
# returns n with the digits reversed # PROC reverse = ( LONG INT v )LONG INT: BEGIN LONG INT r := 0 ; LONG INT n := v; WHILE n > 0 DO r *:= 10; r +:= n MOD 10; n OVERAB 10 OD; r END # reverse # ; LONG INT pow := 10; FOR n FROM 2 TO 7 DO LONG INT low := pow * 9; pow *:= 10; LONG INT high := pow - 1; print( ( "Largest palindromic product of two ", whole( n, 0 ), "-digit integers: " ) ); BOOL next n := FALSE; LONG INT i := high + 1; WHILE i -:= 1; i >= low AND NOT next n DO LONG INT j = reverse( i ); LONG INT p = ( i * pow ) + j; # k can't be even nor end in 5 to produce a product ending in 9 # LONG INT k := high + 2; WHILE k -:= 2; IF k < low THEN FALSE ELIF k MOD 10 = 5 THEN TRUE ELIF LONG INT l = p OVER k; l > high THEN FALSE ELIF p MOD k = 0 THEN print( ( whole( k, 0 ), " x ", whole( l, 0 ), " = ", whole( p, 0 ), newline ) ); next n := TRUE; FALSE ELSE TRUE FI DO SKIP OD OD OD
END</lang>
- Output:
Largest palindromic product of two 2-digit integers: 99 x 91 = 9009 Largest palindromic product of two 3-digit integers: 993 x 913 = 906609 Largest palindromic product of two 4-digit integers: 9999 x 9901 = 99000099 Largest palindromic product of two 5-digit integers: 99979 x 99681 = 9966006699 Largest palindromic product of two 6-digit integers: 999999 x 999001 = 999000000999 Largest palindromic product of two 7-digit integers: 9998017 x 9997647 = 99956644665999
Also showing the maximum for 2 and 4 .. 7 digit numbers. Tests for a better product before testing for palindromicity. <lang algol68>BEGIN # find the highest palindromic multiple of various sizes of numbers #
PROC is pal = ( LONG INT n )BOOL: BEGIN STRING x = whole( n, 0 ); INT l := UPB x + 1; BOOL result := TRUE; FOR i FROM LWB x WHILE i < l AND result DO l -:= 1; result := x[ i ] = x[ l ] OD; result END # is pal # ;
# maximum 2 digit number # LONG INT max := 99; # both factors must be >= 10for a 4 digit product # LONG INT limit start := 10; FOR w FROM 2 TO 7 DO LONG INT best prod := 0; # one factor must be divisible by 11 # LONG INT limit end = 11 * ( max OVER 11 ); LONG INT second := limit start; LONG INT first := 1; # loop from hi to low to find the best result in the fewest steps # LONG INT n := limit end + 11; WHILE n -:= 11; n >= limit start DO # with n falling, the lower limit of m can rise with # # the best-found-so-far second number. Doing this # # lowers the iteration count by a lot. # LONG INT m := max + 2; WHILE m -:= 2; IF m < second THEN FALSE ELIF LONG INT prod = n * m; best prod > prod THEN FALSE ELIF NOT is pal( prod ) THEN TRUE ELSE # maintain the best-found-so-far result # first := n; second := m; best prod := prod; TRUE FI DO SKIP OD OD; print( ( "Largest palindromic product of two ", whole( w, 0 ) , "-digit numbers: ", whole( first, 0 ), " * ", whole( second, 0 ) , " = ", whole( best prod, 0 ) , newline ) ); max *:= 10; max +:= 9; limit start *:= 10 OD
END</lang>
- Output:
Largest palindromic product of two 2-digit numbers: 99 * 91 = 9009 Largest palindromic product of two 3-digit numbers: 913 * 993 = 906609 Largest palindromic product of two 4-digit numbers: 9999 * 9901 = 99000099 Largest palindromic product of two 5-digit numbers: 99979 * 99681 = 9966006699 Largest palindromic product of two 6-digit numbers: 999999 * 999001 = 999000000999 Largest palindromic product of two 7-digit numbers: 9997647 * 9998017 = 99956644665999
C#
Main Task
<lang csharp>using System; class Program {
static bool isPal(int n) { int rev = 0, lr = -1, rem; while (n > rev) { n = Math.DivRem(n, 10, out rem); if (lr < 0 && rem == 0) return false; lr = rev; rev = 10 * rev + rem; if (n == rev || n == lr) return true; } return false; }
static void Main(string[] args) { var sw = System.Diagnostics.Stopwatch.StartNew(); int x = 900009, y = (int)Math.Sqrt(x), y10, max = 999, max9 = max - 9, z, p, bp = x, ld, c; var a = new int[]{ 0,9,0,3,0,0,0,7,0,1 }; string bs = ""; y /= 11; if ((y & 1) == 0) y--; if (y % 5 == 0) y -= 2; y *= 11; while (y <= max) { c = 0; y10 = y * 10; z = max9 + a[ld = y % 10]; p = y * z; while (p >= bp) { if (isPal(p)) { if (p > bp) bp = p; bs = string.Format("{0} x {1} = {2}", y, z - c, bp); } p -= y10; c += 10; } y += ld == 3 ? 44 : 22; } sw.Stop(); Console.Write("{0} {1} μs", bs, sw.Elapsed.TotalMilliseconds * 1000.0); }
}</lang>
- Output @ Tio.run:
913 x 993 = 906609 245.2 μs
Stretch
<lang csharp>using System;
class Program {
static bool isPal(long n) { long rev = 0, lr = -1, rem; while (n > rev) { n = Math.DivRem(n, 10, out rem); if (lr < 0 && rem == 0) return false; lr = rev; rev = 10 * rev + rem; if (n == rev || n == lr) return true; } return false; }
static void doOne(int n) { int ld, c; string bs = ""; string sx = "9" + new string('0', (n - 1) << 1) + "9", sm = new string('9', n); long x = long.Parse(sx), y = (long)Math.Sqrt(x), oy, max = long.Parse(sm), max9 = max - 9, z, yy, p, bp = x; var a = new long[] { 0, 9, 0, 3, 0, 0, 0, 7, 0, 1 }; y /= 11; if ((y & 1) == 0) y--; if (y % 5 == 0) y -= 2; y *= 11; oy = y; while (y <= max) y += 22; y -= 22; while (y >= oy) { c = 0; yy = y * 10; z = max9 + a[ld = (int)(y % 10)]; //Console.WriteLine("y,z: {0},{1}", y, z); p = y * z; while (p >= bp) { if (isPal(p)) { if (p > bp) bp = p; bs = string.Format(" {0,2} {1,10} x {2,-10} = {3}{4}", n, y, z - c, new string(' ', 10 - n), bp); } p -= yy; c += 10; } y -= ld == 7 ? 44 : 22; } Console.WriteLine(bs); }
static void Main(string[] args) { Console.WriteLine("digs factor factor palindrome"); var sw = System.Diagnostics.Stopwatch.StartNew(); for (int i = 2, h = 1; i <= 10; h = ++i >> 1) { if ((i & 1) == 0) { string b = new string('9', i), a = new string('9', h) + new string('0', (h) - 1) + "1", c = new string('9', h) + new string('0', i) + new string('9', h); Console.WriteLine(" {0,2} {1,10} x {2,-10} = {3}{4}", i, a, b, new string(' ', 10 - i), c); } else doOne(i); } sw.Stop(); Console.Write("{0} sec", sw.Elapsed.TotalSeconds); }
}</lang>
- Output @ Tio.run:
Showing results for 2 through 10 digit factors.
digs factor factor palindrome 2 91 x 99 = 9009 3 913 x 993 = 906609 4 9901 x 9999 = 99000099 5 99979 x 99681 = 9966006699 6 999001 x 999999 = 999000000999 7 9997647 x 9998017 = 99956644665999 8 99990001 x 99999999 = 9999000000009999 9 999920317 x 999980347 = 999900665566009999 10 9999900001 x 9999999999 = 99999000000000099999 2.1622142 sec
Wow! how did that go so fast? The results for the even-number-of-digit factors were manufactured by string manipulation instead of calculation (since the pattern was obvious). This algorithm can easily be adapted to BigIntegers for higher n-digit factors, but the execution time is unspectacular.
F#
<lang fsharp> // Largest palindrome product. Nigel Galloway: November 3rd., 2021 let fN g=let rec fN g=[yield g%10; if g>=10 then yield! fN(g/10)] in let n=fN g in n=List.rev n printfn "%d" ([for n in 100..999 do for g in n..999->n*g]|>List.filter fN|>List.max) </lang>
- Output:
906609
FreeBASIC
<lang freebasic>function make_pal( n as ulongint ) as ulongint
'turn a number into a palindrom with twice as many digits dim as string ns, ret ns = str(n) : ret = ns for i as uinteger = len(ns) to 1 step -1 ret += mid(ns, i, 1) next i return val(ret)
end function
function has_dig( n as ulongint, d as uinteger ) as boolean
'does the number n have d decimal digits? if 10^(d-1)<=n and n<10^d then return true else return false
end function
dim as integer np
for d as uinteger = 2 to 7
for n as ulongint = 10^d - 1 to 10^(d-1) step -1 'count down from 999... 'since the first good number we encounter 'must be the highest np = make_pal( n ) 'produce a 2d-digit palindrome from it for f as ulongint = 10^d - 1 to 10^(d-1) step -1 'look for highest d-digit factor if np mod f = 0 then if has_dig( np/f, d ) then 'if np/f also has d digits we are done :) print f;" *";np/f;" =";np goto nextd end if end if next f next n nextd: 'yes, I used a goto. sue me.
next d</lang>
- Output:
99 * 91 = 9009 993 * 913 = 906609 9999 * 9901 = 99000099 99979 * 99681 = 9966006699 999999 * 999001 = 999000000999 9998017 * 9997647 = 99956644665999
Go
18 digit integers are within the range of Go's uint64 type though finding the result for 9-digit number products takes a while - around 15 seconds on my machine. <lang go>package main
import "fmt"
func reverse(n uint64) uint64 {
r := uint64(0) for n > 0 { r = n%10 + r*10 n /= 10 } return r
}
func main() {
pow := uint64(10)
nextN:
for n := 2; n < 10; n++ { low := pow * 9 pow *= 10 high := pow - 1 fmt.Printf("Largest palindromic product of two %d-digit integers: ", n) for i := high; i >= low; i-- { j := reverse(i) p := i*pow + j // k can't be even nor end in 5 to produce a product ending in 9 for k := high; k > low; k -= 2 { if k % 10 == 5 { continue } l := p / k if l > high { break } if p%k == 0 { fmt.Printf("%d x %d = %d\n", k, l, p) continue nextN } } } }
}</lang>
- Output:
Largest palindromic product of two 2-digit integers: 99 x 91 = 9009 Largest palindromic product of two 3-digit integers: 993 x 913 = 906609 Largest palindromic product of two 4-digit integers: 9999 x 9901 = 99000099 Largest palindromic product of two 5-digit integers: 99979 x 99681 = 9966006699 Largest palindromic product of two 6-digit integers: 999999 x 999001 = 999000000999 Largest palindromic product of two 7-digit integers: 9998017 x 9997647 = 99956644665999 Largest palindromic product of two 8-digit integers: 99999999 x 99990001 = 9999000000009999 Largest palindromic product of two 9-digit integers: 999980347 x 999920317 = 999900665566009999
Julia
<lang julia>using Primes
function twoprodpal(factorlength)
maxpal = Int128(10)^(2 * factorlength) - 1 dig = digits(maxpal) halfnum = dig[1:length(dig)÷2] while any(halfnum .!= 0) prodnum = evalpoly(Int128(10), [reverse(halfnum); halfnum]) facs = twofac(factorlength, prodnum) if !isempty(facs) println("For factor length $factorlength, $(facs[1]) * $(facs[2]) = $prodnum") break end halfnum = digits(evalpoly(Int128(10), halfnum) - 1) end
end
function twofac(faclength, prodnum)
f = [one(prodnum)] for (p, e) in factor(prodnum) f = reduce(vcat, [f * p^j for j in 1:e], init=f) end possiblefacs = filter(x -> length(string(x)) == faclength, f) for i in possiblefacs j = prodnum ÷ i j ∈ possiblefacs && return sort([i, j]) end return typeof(prodnum)[]
end
@Threads.threads for i in 2:12
twoprodpal(i)
end
</lang>
- Output:
For factor length 2, 91 * 99 = 9009 For factor length 3, 913 * 993 = 906609 For factor length 4, 9901 * 9999 = 99000099 For factor length 5, 99681 * 99979 = 9966006699 For factor length 6, 999001 * 999999 = 999000000999 For factor length 7, 9997647 * 9998017 = 99956644665999 For factor length 8, 99990001 * 99999999 = 9999000000009999 For factor length 9, 999920317 * 999980347 = 999900665566009999 For factor length 10, 9999986701 * 9999996699 = 99999834000043899999 For factor length 11, 99999943851 * 99999996349 = 9999994020000204999999 For factor length 12, 999999000001 * 999999999999 = 999999000000000000999999
Paper & Pencil
<lang>find two 3-digit factors, that when multiplied together, yield the highest 6-digit palindrome.
lowest possible 6 digit palindrome starting with 9 is 900009 floor(sqrt(900009)) = 948 one factor must be an odd multiple of 11 floor(948 / 11) = 86 it must not be even or a multiple of 5, so use 83 83 * 11 = 913 <- this is the lowest possible first factor the last digit of the second factor must multiply with the last digit of the first factor to get 9 the highest suitable second factor (for 913) is 993 913 x 993 = 906609, a palindrome, now check suitable higher first factors 913 + 22 = 935, an unsuitable multiple of 5, so skip it and use 913 + 44 = 957 957 x 997 = 954129, not a palindrome, so continue (just subtract 9570) 957 x 987 = 944559, not a palindrome, so continue 957 x 977 = 934989, not a palindrome, so continue 957 x 967 = 925429, not a palindrome, so continue 957 x 957 = 915849, not a palindrome, so continue 957 x 947 = 906279, not a palindrome, and less than the best found so far, so stop and continue to the next suitible first number, 957 + 22 = 979 979 x 991 = 970189, not a palindrome, so continue (just subtract 9790) 979 x 981 = 960399, not a palindrome, so continue 979 x 971 = 950609, not a palindrome, so continue 979 x 961 = 940819, not a palindrome, so continue 979 x 951 = 931029, not a palindrome, so continue 979 x 941 = 921239, not a palindrome, so continue 979 x 931 = 911449, not a palindrome, so continue 979 x 921 = 901659, not a palindrome, and less than the best found so far, so stop done because 979 + 22 = 1001</lang>
Perl
<lang perl>use strict; use warnings; use feature 'say'; use ntheory 'divisors';
for my $l (2..7) {
LOOP: for my $p (reverse map { $_ . reverse $_ } 10**($l-1) .. 10**$l - 1) { my @f = reverse grep { length == $l } divisors $p; next unless @f >= 2 and $p == $f[0] * $f[1]; say "Largest palindromic product of two @{[$l]}-digit integers: $f[1] × $f[0] = $p" and last LOOP; }
}</lang>
- Output:
Largest palindromic product of two 2-digit integers: 91 × 99 = 9009 Largest palindromic product of two 3-digit integers: 913 × 993 = 906609 Largest palindromic product of two 4-digit integers: 9901 × 9999 = 99000099 Largest palindromic product of two 5-digit integers: 99681 × 99979 = 9966006699 Largest palindromic product of two 6-digit integers: 999001 × 999999 = 999000000999 Largest palindromic product of two 7-digit integers: 9997647 × 9998017 = 99956644665999
Phix
Translated from python by Lucy_Hedgehog as found on page 5 of the project euler discussion page (dated 25 Sep 2011), and further optimised as per the C# comments (on this very rosettacode page).
-- demo\rosetta\Largest_palindrome_product.exw with javascript_semantics requires("1.0.1") -- (mpz_fdiv_qr(), mpz_si_sub() added to mpfr.js, mpz_mod_ui(), mpz_fdiv_q_ui(), mpz_fdiv_r(), mpz_fdiv_ui() fixed) include mpfr.e function ispalindrome(mpz x) string s = mpz_get_str(x) return s == reverse(s) end function function inverse(mpz x, integer m) -- Compute the modular inverse of x modulo power(10,m). -- Return -1 if the inverse does not exist. -- This function uses Hensel lifting. integer a = {-1, 1, -1, 7, -1, -1, -1, 3, -1, 9}[mpz_fdiv_ui(x,10)+1] if a!=-1 then mpz ax = mpz_init() while true do mpz_mul_si(ax,x,a) {} = mpz_mod_ui(ax,ax,m) if mpz_cmp_si(ax,1)==0 then exit end if mpz_si_sub(ax,2,ax) mpz_mul_si(ax,ax,a) a = mpz_fdiv_q_ui(ax,ax,m) end while end if return a end function function pal2(integer n) assert(n>1) mpz {best,factor,y,r} = mpz_inits(4) if even(n) then // (as per the C# comments) mpz_ui_pow_ui(factor,10,n/2) mpz_sub_si(factor,factor,1) mpz_ui_pow_ui(best,10,n/2*3) mpz_mul(best,best,factor) mpz_add(best,best,factor) assert(ispalindrome(best)) mpz_ui_pow_ui(factor,10,n) mpz_sub_si(factor,factor,1) assert(ispalindrome(factor)) else // Get a lower bound: integer k = floor(n/2) mpz {maxf,maxf11,minf,x,t,maxy,p} = mpz_inits(7) while true do mpz_ui_pow_ui(maxf,10,n) mpz_sub_si(maxf,maxf,1) mpz_sub_si(maxf11,maxf,11) {} = mpz_fdiv_q_ui(maxf11,maxf11,22) mpz_mul_si(maxf11,maxf11,22) mpz_add_si(maxf11,maxf11,11) mpz_ui_pow_ui(minf,10,n-k) mpz_sub(minf,maxf,minf) mpz_add_si(minf,minf,2) mpz_mul(best,minf,minf) mpz_set_si(factor,0) // This palindrome starts with k 9's. // Hence the largest palindrom must also start with k 9's and // therefore end with k 9's. // Thus, if p = x * y is the solution then // x * y + 1 is divisible by m. integer m = power(10,k) -- (should not exceed 1e8) mpz_set(x,maxf11) while mpz_cmp_si(x,1)>=0 do mpz_mul(t,x,maxf) if mpz_cmp(t,best)=-1 then exit end if integer ry = inverse(x, m) if ry!=-1 then mpz_add_si(maxy,maxf,1-ry) mpz_mul(p,maxy,x) while mpz_cmp(p,best)>0 do if ispalindrome(p) then mpz_set(best,p) mpz_set(factor,x) end if mpz_mul_si(t,x,m) mpz_sub(p,p,t) end while end if mpz_sub_si(x,x,22) end while if mpz_cmp_si(factor,0)!=0 then exit end if k -= 1 end while end if mpz_fdiv_qr(y,r,best,factor) assert(mpz_cmp_si(r,0)=0) return {best, factor, y} end function constant fmt = "Largest palindromic product of two %d-digit integers: %s = %s x %s (%s)\n" for n=2 to 12 do atom t1 = time() mpz {p,x,y} = pal2(n) string sp = mpz_get_str(p), sx = mpz_get_str(x), sy = mpz_get_str(y), e = elapsed(time()-t1) printf(1,fmt,{n,sp,sx,sy,e}) end for
- Output:
Largest palindromic product of two 2-digit integers: 9009 = 99 x 91 (0s) Largest palindromic product of two 3-digit integers: 906609 = 913 x 993 (0s) Largest palindromic product of two 4-digit integers: 99000099 = 9999 x 9901 (0s) Largest palindromic product of two 5-digit integers: 9966006699 = 99979 x 99681 (0s) Largest palindromic product of two 6-digit integers: 999000000999 = 999999 x 999001 (0s) Largest palindromic product of two 7-digit integers: 99956644665999 = 9997647 x 9998017 (0.0s) Largest palindromic product of two 8-digit integers: 9999000000009999 = 99999999 x 99990001 (0s) Largest palindromic product of two 9-digit integers: 999900665566009999 = 999920317 x 999980347 (0.8s) Largest palindromic product of two 10-digit integers: 99999000000000099999 = 9999999999 x 9999900001 (0s) Largest palindromic product of two 11-digit integers: 9999994020000204999999 = 99999996349 x 99999943851 (0.1s) Largest palindromic product of two 12-digit integers: 999999000000000000999999 = 999999999999 x 999999000001 (0s)
After that it starts to struggle a bit:
Largest palindromic product of two 13-digit integers: 99999963342000024336999999 = 9999996340851 x 9999999993349 (40.4s) Largest palindromic product of two 14-digit integers: 9999999000000000000009999999 = 99999999999999 x 99999990000001 (0s) Largest palindromic product of two 15-digit integers: 999999974180040040081479999999 = 999999998341069 x 999999975838971 (1 minute and 12s) Largest palindromic product of two 16-digit integers: 99999999000000000000000099999999 = 9999999999999999 x 9999999900000001 (0s)
Raku
<lang perl6>use Inline::Perl5; my $p5 = Inline::Perl5.new(); $p5.use: 'ntheory'; my &divisors = $p5.run('sub { ntheory::divisors $_[0] }');
.say for (2..12).map: {.&lpp};
multi lpp ($oom where {!($_ +& 1)}) { # even number of multiplicand digits
my $f = +(9 x $oom); my $o = $oom / 2; my $pal = +(9 x $o ~ 0 x $oom ~ 9 x $o); sprintf "Largest palindromic product of two %2d-digit integers: %d × %d = %d", $oom, $pal div $f, $f, $pal
}
multi lpp ($oom where {$_ +& 1}) { # odd number of multiplicand digits
my $p; (+(1 ~ (0 x ($oom - 1))) .. +(9 ~ (9 x ($oom - 1)))).reverse.map({ +($_ ~ .flip) }).map: -> $pal { for my @factors = divisors("$pal")».Int.grep({ .chars == $oom }).sort( -* ) { next unless $pal div $_ ∈ @factors; $p = sprintf("Largest palindromic product of two %2d-digit integers: %d × %d = %d", $oom, $pal div $_, $_, $pal); last; } last if $p; } $p
}</lang>
Largest palindromic product of two 2-digit integers: 91 × 99 = 9009 Largest palindromic product of two 3-digit integers: 913 × 993 = 906609 Largest palindromic product of two 4-digit integers: 9901 × 9999 = 99000099 Largest palindromic product of two 5-digit integers: 99681 × 99979 = 9966006699 Largest palindromic product of two 6-digit integers: 999001 × 999999 = 999000000999 Largest palindromic product of two 7-digit integers: 9997647 × 9998017 = 99956644665999 Largest palindromic product of two 8-digit integers: 99990001 × 99999999 = 9999000000009999 Largest palindromic product of two 9-digit integers: 999920317 × 999980347 = 999900665566009999 Largest palindromic product of two 10-digit integers: 9999900001 × 9999999999 = 99999000000000099999 Largest palindromic product of two 11-digit integers: 99999943851 × 99999996349 = 9999994020000204999999 Largest palindromic product of two 12-digit integers: 999999000001 × 999999999999 = 999999000000000000999999
Ring
<lang ring>? "working..."
prod = 1 bestProd = 0 // maximum 3 digit number max = 999 // both factors must be >100 for a 6 digit product limitStart = 101 // one factor must be divisible by 11 limitEnd = 11 * floor(max / 11) second = limitStart iters = 0
// loop from hi to low to find the best result in the fewest steps for n = limitEnd to limitStart step -11
// with n falling, the lower limit of m can rise with // the best-found-so-far second number. Doing this // lowers the iteration count by a lot. for m = max to second step -2 prod = n * m if isPal(prod) iters++ // exit when the product stops increasing if bestProd > prod exit ok // maintain the best-found-so-far result first = n second = m bestProd = prod ok next
next
put "The largest palindrome is: " ? "" + bestProd + " = " + first + " * " + second ? "Found in " + iters + " iterations" put "done..."
func isPal n
x = string(n) l = len(x) + 1 i = 0 while i < l if x[i++] != x[l--] return false ok end return true</lang>
- Output:
working... The largest palindrome is: 906609 = 913 * 993 Found in 6 iterations done...
Wren
The approach here is to manufacture palindromic numbers of length 2n in decreasing order and then see if they're products of two n-digit numbers. <lang ecmascript>var reverse = Fn.new { |n|
var r = 0 while (n > 0) { r = n%10 + r*10 n = (n/10).floor } return r
}
var pow = 10 for (n in 2..7) {
var low = pow * 9 pow = pow * 10 var high = pow - 1 System.write("Largest palindromic product of two %(n)-digit integers: ") var nextN = false for (i in high..low) { var j = reverse.call(i) var p = i * pow + j // k can't be even nor end in 5 to produce a product ending in 9 var k = high while (k > low) { if (k % 10 != 5) { var l = p / k if (l > high) break if (p % k == 0) { System.print("%(k) x %(l) = %(p)") nextN = true break } } k = k - 2 } if (nextN) break }
}</lang>
- Output:
Largest palindromic product of two 2-digit integers: 99 x 91 = 9009 Largest palindromic product of two 3-digit integers: 993 x 913 = 906609 Largest palindromic product of two 4-digit integers: 9999 x 9901 = 99000099 Largest palindromic product of two 5-digit integers: 99979 x 99681 = 9966006699 Largest palindromic product of two 6-digit integers: 999999 x 999001 = 999000000999 Largest palindromic product of two 7-digit integers: 9998017 x 9997647 = 99956644665999
XPL0
<lang XPL0>func Rev(A); \Reverse digits int A, B; [B:= 0; repeat A:= A/10;
B:= B*10 + rem(0);
until A = 0; return B; ];
int Max, M, N, Prod; [Max:= 0; for M:= 100 to 999 do
for N:= M to 999 do [Prod:= M*N; if Prod/1000 = Rev(rem(0)) then if Prod > Max then Max:= Prod; ];
IntOut(0, Max); ]</lang>
- Output:
906609