Win a copy of Java EE 8 High Performance this week in the Java/Jakarta EE forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Can someone help me fix the math in my code?

Ranch Hand
Posts: 58
Hi I am trying to create a program to solve Project Euler Problem 4. The problem is "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."

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?

Sheriff
Posts: 11643
187
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

John Sing
Ranch Hand
Posts: 58

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

Sheriff
Posts: 23286
46
Have you done any debugging to see whether your number-reversing code actually reverses a 6-digit number correctly?

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.

Marshal
Posts: 5388
374
Another way to look at the problem is:
1. Find the largest product made of 3 digit numbers
2. Check if product single characters (digits) are palindromes (first vs last, second vs ..)
3. In case it is, check if product (number) has factors

Junilu Lacar
Sheriff
Posts: 11643
187

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.

Paul Clapham
Sheriff
Posts: 23286
46

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.

Junilu Lacar
Sheriff
Posts: 11643
187

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

Liutauras Vilda
Marshal
Posts: 5388
374

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.

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

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.

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

Junilu Lacar
Sheriff
Posts: 11643
187
(n^n) != (n*n)

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.

Junilu Lacar
Sheriff
Posts: 11643
187

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.

Liutauras Vilda
Marshal
Posts: 5388
374

Junilu Lacar wrote:(n^n) != (n*n)

Of course you're right here. My mistake.

Junilu 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

But that second point is basically the same what I wrote

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

Junilu Lacar
Sheriff
Posts: 11643
187
Ok, I see what you are doing. I did it another way. I guess mine is a more brute force method. I'll have to try your method with the factoring, too.

Thanks

Junilu Lacar
Sheriff
Posts: 11643
187
It's interesting to see how different people's brains work. I approached it from the eligible factors, then checked if their products were a palindromes. You guys started with a possible products, then checked if there were any eligible factors. you should try your program with 5 digits and see how long it takes. My way took about 100 seconds to run through the algorithm for products of two 5-digit numbers, on a MacBook Pro 2.3 GHz i7

Bartender
Posts: 585
9
Why do you initialize num2 to 999 and then immediately decrement it, thus ignoring any possible answers where num2=999?

Bartender
Posts: 10575
66

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

Junilu Lacar
Sheriff
Posts: 11643
187
• X 2
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

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:

Winston Gutkowski
Bartender
Posts: 10575
66

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

Liutauras Vilda
Marshal
Posts: 5388
374
• 1
My initial algorithm I worked out for myself based on OP's provided requirements (3-digit product number) did the job, but that wasn't good enough since Junilu suggested to try algorithm with product of 5-digit numbers.

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.

Winston Gutkowski
Bartender
Posts: 10575
66

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 possible factors and 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

Liutauras Vilda
Marshal
Posts: 5388
374
Looking to Junilu's figures, it is interesting enough, mine algorithm works significantly faster on some of the cases
Approach I am using is:
• starting from the highest possible product and going down
• checking number individual characters if these are same (StringBuilder reverse method looks nicer, only 1 line instead of 6, but slightly slower)
• checking if palindrome has factors. Looking for exact divisor, and then if second divisor is the same length
•
Junilu Lacar
Sheriff
Posts: 11643
187
Even when I revise the way I count iterations in Algorithm 1 to just increment in the factorization loop, I still get pretty high numbers:

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.

Junilu Lacar
Sheriff
Posts: 11643
187
• 1
Liutauras,

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!

Saloon Keeper
Posts: 3725
47
• 1

A brute force approach with some steps to reduce the iteration count.
I also put some effort into optimizing the isPalindrome() method.

Winston Gutkowski
Bartender
Posts: 10575
66
• 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

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 -  and Junilu's for length 9, so I'm ).

Winston

Junilu Lacar
Sheriff
Posts: 11643
187

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!

Winston Gutkowski
Bartender
Posts: 10575
66

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

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

Winston

Winston Gutkowski
Bartender
Posts: 10575
66

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

Winston

Winston Gutkowski
Bartender
Posts: 10575
66

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

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

Master Rancher
Posts: 2310
76
• 1
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. 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.

Winston Gutkowski
Bartender
Posts: 10575
66

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

Piet Souris
Master Rancher
Posts: 2310
76
• X 2
No, my little proof was no try and error.
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!

Winston Gutkowski
Bartender
Posts: 10575
66

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

 Consider Paul's rocket mass heater.