Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Reducing Number of Multiplications in a Loop

  1. Apr 1, 2008 #1

    Following on from my palindromic number question, if I am calculating a set of palindromic numbers generated as the product of two three-digit numbers, I could generate the entire product set and then test each number for the palindrome property.

    the naive approach would be a loop like

    for (i in 999:100)
    for (j in 999:100)
    p = i * j

    However, we do many redundant multiplications this way, so the obvious approach is to do

    for (i in 999:100)
    for (j in i:100)
    p= i * j

    However, I still a lot of palindromic numbers that are duplicated. for instance, the palindrome 444444 is generated by:

    962 * 462 = 444444
    924 * 481 = 444444
    858 * 518 = 444444
    814 * 546 = 444444
    777 * 572 = 444444

    Is there any way to avoid or predict these multiplications of two 3-digit numbers that will produce duplicate palindromes?
    Last edited: Apr 1, 2008
  2. jcsd
  3. Apr 1, 2008 #2
    You asked a very tough question which I doubt has an answer. It would be much simpler to just automatically sort your results and remove duplicates. I would be interested in determining how many of the palindromes between the smallest and largest in your list are unaccounted for by your program and how many of these are prime. Each answer is going to be different.
    Last edited: Apr 1, 2008
  4. Apr 1, 2008 #3
    Thanks Ramsey. I didnt think there would be a straightforward answer to this one.
  5. Apr 2, 2008 #4


    User Avatar
    Science Advisor
    Homework Helper

    There are two reasonably efficient ways of doing this that immediately spring to mind. You could loop through the three-digit numbers, letting i <= j (405,050 loops), possibly skipping ij = 0 mod 10 (reducing the possibilities slightly at the cost of overhead). Alternately, you could loop through the 5 and 6-digit palindromes (1800 loops), factoring at each step. You have to decide which is faster -- in essence, is factoring harder or easier than 225 multiplications?
  6. Apr 2, 2008 #5
    If you skip ij= 0 mod 10 then you would miss 012210 = 110*111 or are leading zeros prohibited?
  7. Apr 2, 2008 #6


    User Avatar
    Science Advisor
    Homework Helper

    Typically multiples of b aren't considered base-b palindromes. For example, Sloane's http://www.research.att.com/~njas/sequences/A002113 [Broken] doesn't include 10 = 010 or 100 = 00100. But if you wanted to consider them, you'd of course need to include the multiples of 10.
    Last edited by a moderator: May 3, 2017
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook