Find the largest palindrome made from the product of two 3-digit numbers."

Here is my code

The number I am getting from this code is "580085" which does fulfill the requirements but it's the wrong answer. How can I fix my code to get the right answer?

For example, the reverse of 89:

89 % 10 = 9

89 / 10 = 8

9 * 10 = 90

90 + 8 = 98

98 != 89 therefore 89 is not a palindrome

77 % 10 = 7

77 / 10 = 7

7 * 10 = 70

70 + 7 = 77

77 == 77 therefore 77 is a palindrome

---

Exercise for you is to generalize this and put it into a loop.

I would break the problem down into two parts:

1 - find the reverse of a number

2 - find the largest palindromic number that is the product of X-digit numbers

*Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

Junilu Lacar wrote:Since you're dealing with integer values, you can just use % and / (integer division) to reverse the number. If the reverse of a number and the original number are the same then it's a palindromic number.

For example, the reverse of 89:

89 % 10 = 9

89 / 10 = 8

9 * 10 = 90

90 + 8 = 98

98 != 89 therefore 89 is not a palindrome

77 % 10 = 7

77 / 10 = 7

7 * 10 = 70

70 + 7 = 77

77 == 77 therefore 77 is a palindrome

---

Exercise for you is to generalize this and put it into a loop.

I would break the problem down into two parts:

1 - find the reverse of a number

2 - find the largest palindromic number that is the product of X-digit numbers

I looked up how to reverse a number online and I implemented it into my code. The thing the new number I am getting is not even a palindrome. Here is my new code

This code prints out the number "99700" so I think I am doing this wrong. How can I fix this?

EDIT- I just realized I am getting my error because I reversed the number but I never compared it to the original. How would I go about doing this?

ANOTHER EDIT- Okay I tried comparing them and my code compliles but then it does not print anything. Here is my new code

And just a suggestion: you might find it easier to do testing and debugging if you broke down your code into methods which each do one thing. Reversing the digits of a number is an ideal candidate for a method. Remember, there's more to testing a program than just running the thing and observing whether it outputs the correct results.

Liutauras Vilda wrote:

3. In case it is, check if product (number) has factors

I'm curious, what is this going to get you?

The checking for products is an O(n * n) problem - you have to set up a nested for-loop.

*Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

Junilu Lacar wrote:

Liutauras Vilda wrote:

3. In case it is, check if product (number) has factors

I'm curious, what is this going to get you?

The checking for products is an O(n * n) problem - you have to set up a nested for-loop.

Besides which, it's actually necessary to check that the number has factors which are both < 1000.

Paul Clapham wrote:Besides which, it's actually necessary to check that the number has factors which are both < 1000.

I don't get it. I just solved this and I didn't have to do any such kind of check. The loop limits ensure that the numbers you're using to calculate the products are both < 1000

*Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

Junilu Lacar wrote:I'm curious, what is this going to get you?

999 * 999 = 998001

The largest theoretical palindrome could be 997799, but that number you can't get by product of 3 digit number.

Yes, that would be O(n^n). Not sure if would be quicker actually to work it out with %, as in this case numbers are quite big, using % could be slow.Junilu Lacar wrote:The checking for products is an O(n * n) problem - you have to set up a nested for-loop.

And the exercise is asking largest palindrome made of product of 3-digit number, basically xxx * xxx.

You start at 999 * 999 and work your way through all possible products, keeping track of the largest palindrome that you've found so far. That's all. It's an O(n*n) problem.

Practice mindfully by doing the right things and doing things right.

[How to Ask Questions] [How to Answer Questions]

Liutauras Vilda wrote:using % could be slow.

Yeah, that smells like premature optimization to me. I see no requirements in the problem statement that says to find the fastest method.

Practice mindfully by doing the right things and doing things right.

[How to Ask Questions] [How to Answer Questions]

Of course you're right here. My mistake.Junilu Lacar wrote:(n^n) != (n*n)

But that second point is basically the same what I wroteJunilu Lacar wrote:I would break the problem down into two parts:

1 - find the reverse of a number

2- find the largest palindromic number that is the product of X-digit numbers

Earlier me wrote:3. In case it is, check if product (number) has factors

Thanks

Practice mindfully by doing the right things and doing things right.

[How to Ask Questions] [How to Answer Questions]

Practice mindfully by doing the right things and doing things right.

[How to Ask Questions] [How to Answer Questions]

John Sing wrote:"!Find the largest palindrome made from the product of two 3-digit numbers."

The number I am getting from this code is "580085" which does fulfill the requirements but it's the wrong answer. How can I fix my code to get the right answer?

Not exactly sure, but here's a few things that might help:

1. There are 900 palindromic numbers between 100000 and 999999, which are, from highest to lowest, 999 + 999 down to 100 + 001.

2. All palindromic numbers with an even number of digits divide by 11. Therefore

__one__of the three-digit factors must also divide by eleven, so you only need to check every 11th number between 110 and 999.

3. If for a given palindromic number p, you check this factor (f) in reverse order from 999 down, you can stop as soon as p / f > 999 or you find a factor that divides p exactly.

There may be some other tweaks as well, but that's what I see off the bat.

Hope it helps.

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

- X 2

I may be reading your response wrong but here are a few things I'd point out:

1. The requirement is to find the largest palindromic product of two 3-digit numbers.

So, the range of possible solutions is [100*100 .. 999*999] or [10,000 .. 998,001]

2. That means that you'll have a mix of odd and even numbered digits in the range of possible solutions

I have implemented the two different algorithms alluded to in this thread:

1. Iterate through all possible

**products**, stop at the first palindromic number that is the product of two N-digit numbers.

2. Iterate through all possible

**factors**and keep track of the largest palindromic product.

Both approaches work. In my implementation for Algorithm 1, I started from the greatest possible product and worked my way down. See the following snippet.

In my implementation of algorithm 1, in the

`hasEligibleFactors()`method, I start from the greatest possible factor,

`high`, and work my way down to see if the palindrome is evenly divisible by it and return as soon as two eligible factors are found; this loop also increments the iteration count variable,

`iters`. My implementation of this approach resulted in far more iterations performed than the second approach when the second includes optimizations to eliminate possible factors as iteration progresses.

Here are my results:

I did not wait for Algorithm 1 to finish calculations for 6-digit number products because it was taking too long

EDIT: I decided I'd wait. Here are the results for 6-digit numbers using Algorithm 1:

Practice mindfully by doing the right things and doing things right.

[How to Ask Questions] [How to Answer Questions]

Junilu Lacar wrote:Winston,

I may be reading your response wrong but here are a few things I'd point out:

1. The requirement is to find the largest palindromic product of two 3-digit numbers.

So, the range of possible solutions is [100*100 .. 999*999] or [10,000 .. 998,001]

2. That means that you'll have a mix of odd and even numbered digits in the range of possible solutions

Oops. You're quite right. However, I suspect you can then break it down into two halves:

1. As I described above, on the assumption that a 6-digit palindrome has fewer combinations to check since one of the factors must divide by 11.

2. (If step1 didn't yield an answer) Check palindromes between 10000 and 99,999 (also 900 of them), which are likely to have far fewer pairs of three digit factors to start with - specifically, you can start from 316 (

`int(√99999)`) and go down to 100.

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

- 1

First I encountered issues with used data type as the numbers I had to work with got increased signifanctly, so I had to choose other data type to work with. But problems didn't finish there. Algorithm worked slow enough, so I wasn't patient enough to wait till the end. After cracking my head for a while last night, I improved my algorithm, so at the moment it finds product of 5-digit numbers product palindrome in around 1.5 seconds - not that bad, BUT, I was curious to try out what would happen with 6-digit and finally 7-digit...

As expected, since algorithm looks pretty straight forward, the time to find 6-digit numbers product palindrome gone significantly up. From 1.5 second to around 51 second. So will have to look into it further, to get closer to Junilu's figures

Cow for Junilu for a great challenge, which helped me not to stop on the first found algorithm to satisfy original OP's requirements. It is interesting to see, how small tweaks in a program increases signifantly its performance.

Junilu Lacar wrote:1. Iterate through all possible

products, stop at the first palindromic number that is the product of two N-digit numbers.

2. Iterate through all possiblefactorsand keep track of the largest palindromic product.

I have to admit, I haven't tried either of those approaches because (I think) the number of

*palindromes*is likely to be smaller than either of those above.

Specifically, for any pair of factors of length n, I suspect there will be < 2 x 10ⁿ palindromes to check (half of length 2n, half of length 2n-1), and the check of the first half (the one that hopefully gives you a result) is further factored by the fact that you only need to check factors that divide by 11; and the latter by the fact that you only have to check factors < √10ⁿ.

(Correction: < 10ⁿ⁻¹ * √10)

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

Approach I am using is:

Another interesting thing I noticed was that Algorithm 2 actually took fewer iterations to find the largest palindromic product of two 6-digit numbers than it took to find the one for 5-digit numbers. Algorithm 1 seems to need increasingly more iterations as N increases.

Practice mindfully by doing the right things and doing things right.

[How to Ask Questions] [How to Answer Questions]

- 1

My results for two 9-digit numbers.

I figure it would be OK to show the actual numbers as this is way beyond what OP is trying to get. The progress messages also will give you a hint as to what optimizations I found for the algorithm. As you find each possible maximum palindromic product, you can eliminate more possible factors, thus significantly reducing the overall number of iterations it takes to find the final solution.

Keep up, son!

Practice mindfully by doing the right things and doing things right.

[How to Ask Questions] [How to Answer Questions]

- 1

Junilu Lacar wrote:Keep up, son!

With my prog using 2 phases as described above. Results:

`Length: 3, largest: ******, factors: ***,***`

Length: 4, largest: 99000099, factors: 9999,9901

Length: 5, largest: 9966006699, factors: 99979,99681

Length: 6, largest: 999000000999, factors: 999999,999001

Length: 7, largest: 99956644665999, factors: 9997647,9998017

Length: 8, largest: 9999000000009999, factors: 99999999,99990001

Length: 9, largest: 999900665566009999, factors: 999920317,999980347

Length: 4, largest: 99000099, factors: 9999,9901

Length: 5, largest: 9966006699, factors: 99979,99681

Length: 6, largest: 999000000999, factors: 999999,999001

Length: 7, largest: 99956644665999, factors: 9997647,9998017

Length: 8, largest: 9999000000009999, factors: 99999999,99990001

Length: 9, largest: 999900665566009999, factors: 999920317,999980347

Takes approx 6 seconds on my laptop using a really crappy algorithm for generating palindromes (Strings would you believe?).

Lengths up to 8 take less than a second.

I've blanked out the length 3 results, but wanted to see if the others tally (seem to agree with Carey's up to length 7 - [Edit] and Junilu's for length 9, so I'm ).

Winston

Articles by Winston can be found here

Winston Gutkowski wrote:

Lengths up to 8 take less than a second.

Well, dang, looks like you got me beat.

I want to see some proof, otherwise it's just hearsay!

Practice mindfully by doing the right things and doing things right.

[How to Ask Questions] [How to Answer Questions]

Winston Gutkowski wrote:Takes approx 6 seconds on my laptop...

Actually slightly more (my internal clock must be slow). Over ten iterations of lengths 3-9:

`Palindrome complete`

Event: Palindrome

Number of timings: 10

Total elapse time: 82.487484337s

Total active time: 82.487484337s

Avg. active time: 8248.748ms

Event: Palindrome

Number of timings: 10

Total elapse time: 82.487484337s

Total active time: 82.487484337s

Avg. active time: 8248.748ms

I can also hear the fan ramp up while it's executing.

Winston

Articles by Winston can be found here

Junilu Lacar wrote:

Winston Gutkowski wrote:Lengths up to 8 take less than a second.

I want to see some proof, otherwise it's just hearsay!

For lengths 3-8 over 100 iterations:

`Palindrome complete`

Event: Palindrome

Number of timings: 100

Total elapse time: 10.564605297s

Total active time: 10.564605297s

Avg. active time: 105.646ms

Event: Palindrome

Number of timings: 100

Total elapse time: 10.564605297s

Total active time: 10.564605297s

Avg. active time: 105.646ms

Winston

Articles by Winston can be found here

Junilu Lacar wrote:I want to see some proof, otherwise it's just hearsay!

I added an iteration count for comparison. Here are the results:

`Size: 4 Palindrome: 99000099 Factors: 9999,9901`

------- Iterations: 487

Size: 5 Palindrome: 9966006699 Factors: 99979,99681

------- Iterations: 4817

Size: 6 Palindrome: 999000000999 Factors: 999999,999001

------- Iterations: 45774

Size: 7 Palindrome: 99956644665999 Factors: 9997647,9998017

------- Iterations: 849095

Size: 8 Palindrome: 9999000000009999 Factors: 99999999,99990001

------- Iterations: 4548637

Size: 9 Palindrome: 999900665566009999 Factors: 999920317,999980347

------- Iterations: 448396417

------- Iterations: 487

Size: 5 Palindrome: 9966006699 Factors: 99979,99681

------- Iterations: 4817

Size: 6 Palindrome: 999000000999 Factors: 999999,999001

------- Iterations: 45774

Size: 7 Palindrome: 99956644665999 Factors: 9997647,9998017

------- Iterations: 849095

Size: 8 Palindrome: 9999000000009999 Factors: 99999999,99990001

------- Iterations: 4548637

Size: 9 Palindrome: 999900665566009999 Factors: 999920317,999980347

------- Iterations: 448396417

So I wonder if the difference is only checking factors that are multiples of 11.

My program never does execute "phase 2" because it always finds a palindrome with an even number of digits, which makes me wonder if the following is true:

*For any length n, there is a pair of decimal numbers of length n whose product is a palindrome of length 2n*.

It certainly seems to be true for even numbers of n, since the pairs seem to be - in regex form - '

`99{x}0{x}1`' and '

`9{2x+2}`', where n = 2x+2; but I have no idea how you'd go about proving it for odd lengths.

Winston

Articles by Winston can be found here

- 1

So, an example is much better.

Take n = 7, and look at the number 5866663. That is, 5, 8, n - 3 sixes, and a 3; 7 digits altogether.

Then, 5866663 * (10^n - 5) = 5866663 * 9999995 = 58666630000000 - 5 * 5866663 =

58666630000000 - 29333315 = 58666600666685.

This holds for any odd n. So, for a 2n digit number with n odd, there is always a palindrome that is the product

of two n digit numbers.

In case n is even, we look at the product (10^n - 1) * (10^n - 10 ^(n/2) + 1) and after some transformation,

we end up with the number: 10^(3n/2) * (10 ^ (n/2) - 1) + 10 ^(n/2) - 1,

in which we recognize a number that starts and ends with n/2 nines, with zeroes in between.

But again: be aware that a frequent pattern in Project Euler is the sequence of problems:

1) easy to do with BF

2) much harder to do with BF, requiring a lot of optimisation

3) the third problem in a row is impossible to solve with BF.

Here, no solution is given for n = 3, which is indeed problem 4, but the solutions for higher n are given.

risking publishing solutions of other problems to the whole outside world.

I can only advise: if anyone likes problems like this one (or much harder ones), then go to PE, it's free of charge,

and with a problem solved one gets access to a dedicated forum full of superfast and superclever

solutions.

Piet Souris wrote:A proof for n odd is easy, albeit very tedious.

So, an example is much better.

Take n = 7, and look at the number 5866663.

Aaah. Nifty. And presumably it works for

*any*length of n >= 4, because ...

`30{n} - (5 * 586{n-3}3)`gives ...

`006{n-3}85`. It also divides by 11.

So...how do you get to such a pattern? I presume there's more than trial and error involved.

Cheers Piet. Have a cow.

Winston

Articles by Winston can be found here

- X 2

What I did was to get a divisor as fast as possible.

And I noticed what you implicitely also showed in your overview:

the patterns when it comes to the different number lengths.

For instance: when n is odd, you will always first find 99..95 and

586...63, and for n even you see 9...9 and 9...1.

From this observation it is relatively easy to get to some proof, like I did.

I do not use the fact that n is odd in my first proof. So, indeed it should

work for even n as well.

However, my intention was to get two bounding divisors as fast as possible,

and as close as possible, and for n even the 9...9 and 9...1 are much closer

together.

Anyway: the nicest problem I dealt with at PE is problem 84. Thoroughly recommended!

Piet Souris wrote:However, my intention was to get two bounding divisors as fast as possible,

and as close as possible, and for n even the 9...9 and 9...1 are much closer together.

Ah, that's sounds more like Junilu and Carey's approach, which is maybe why I missed the pattern. Since the problem asked for the

*highest*palindromic number, I decided to tackle it by checking known palindromic numbers for pairs of factors, one of which I knew had to divide by 11; so I would never have checked for 9...5.

Anyway: the nicest problem I dealt with at PE is problem 84. Thoroughly recommended!

I'll check it out. Thanks again.

Winston

Articles by Winston can be found here

Consider Paul's rocket mass heater. |