Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Can someone help me fix the math in my code?  RSS feed

 
John Sing
Ranch Hand
Posts: 58
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
Junilu Lacar
Sheriff
Posts: 11138
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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

 
Paul Clapham
Sheriff
Posts: 22480
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Liutauras Vilda
Marshal
Posts: 4634
316
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 11138
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 22480
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 11138
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 4634
316
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 11138
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
(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: 11138
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 4634
316
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 11138
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 11138
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Fred Kleinschmidt
Bartender
Posts: 560
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Why do you initialize num2 to 999 and then immediately decrement it, thus ignoring any possible answers where num2=999?
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 11138
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 4634
316
BSD
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 4634
316
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 11138
    160
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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: 11138
    160
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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!
     
    Carey Brown
    Bartender
    Posts: 2992
    46
    Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    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: 10573
    65
    Eclipse IDE Hibernate Ubuntu
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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 - [Edit] and Junilu's for length 9, so I'm ).

    Winston
     
    Junilu Lacar
    Sheriff
    Posts: 11138
    160
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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: 10573
    65
    Eclipse IDE Hibernate Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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: 10573
    65
    Eclipse IDE Hibernate Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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: 10573
    65
    Eclipse IDE Hibernate Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
     
    Piet Souris
    Rancher
    Posts: 1979
    67
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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: 10573
    65
    Eclipse IDE Hibernate Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Rancher
    Posts: 1979
    67
    • Likes 2
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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: 10573
    65
    Eclipse IDE Hibernate Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
     
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!