Reducing Number of Multiplications in a Loop

[rwinston]

Hi

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?

 

[ramsey2879]

Hi

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?

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.

 

[rwinston]

Thanks Ramsey. I didnt think there would be a straightforward answer to this one.

 

[CRGreathouse]

Thanks Ramsey. I didnt think there would be a straightforward answer to this one.

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?

 

[ramsey2879]

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?

If you skip ij= 0 mod 10 then you would miss 012210 = 110*111 or are leading zeros prohibited?

 

[CRGreathouse]

If you skip ij= 0 mod 10 then you would miss 012210 = 110*111 or are leading zeros prohibited?

Typically multiples of b aren't considered base-b palindromes. For example, Sloane's http://www.research.att.com/~njas/sequences/A002113 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.