Project Euler

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

Numquam
Posts: 162
Joined: Wed Nov 21, 2007 3:13 am UTC

Re: Project Euler

Postby Numquam » Sun Jun 28, 2009 7:36 pm UTC

Having trouble with number 7 which is:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6^(th) prime is 13.

What is the 10001^(st) prime number?

I'm a very novice programmer and not very good at math anyways, so take caution - this code is not for the weak of heart. Shade your eyes if you can't take badly written code. (Its in Python)

Spoiler:

Code: Select all

n = 1
x = 0
check = 0

while x <= 10001:
    check = (2**(n-1))%n
    if check == 1:
        x = x + 1
        print (x)
    n = n + 1
print (n-1)
print ("done")


My "Solution"
Spoiler:
103919


What have I done wrong?
admiror, o internet, te non cecidisse (ruinis)
qui tot scriptorum taedia sustineas

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Project Euler

Postby Berengal » Sun Jun 28, 2009 8:40 pm UTC

Your check is wrong. What's 2^340 Mod 341? What's 11*31?
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

keeperofdakeys
Posts: 658
Joined: Wed Oct 01, 2008 6:04 am UTC

Re: Project Euler

Postby keeperofdakeys » Sun Jun 28, 2009 11:09 pm UTC

you may want to do some more research on prime numbers

Ended
Posts: 1459
Joined: Fri Apr 20, 2007 3:27 pm UTC
Location: The Tower of Flints. (Also known as: England.)

Re: Project Euler

Postby Ended » Sun Jun 28, 2009 11:28 pm UTC

Specifically, your check (the Fermat test with a=2) is necessary for primality but not sufficient. That is, all prime numbers will pass it but some composite numbers will also pass it.
Generally I try to make myself do things I instinctively avoid, in case they are awesome.
-dubsola

Numquam
Posts: 162
Joined: Wed Nov 21, 2007 3:13 am UTC

Re: Project Euler

Postby Numquam » Mon Jun 29, 2009 1:58 pm UTC

Thanks for the help, got the right answer and learned a thing or two in the process. :D
admiror, o internet, te non cecidisse (ruinis)
qui tot scriptorum taedia sustineas

fungfat
Posts: 5
Joined: Mon Jul 06, 2009 8:13 pm UTC

Re: Project Euler

Postby fungfat » Mon Jul 06, 2009 8:19 pm UTC

I was desperate about problem 3. Can someone help?

Problem 3 said that "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."

I found the answer is 995 x 583 = 580085. But Project Euler said it is wrong. I tried another method and still came up with the same answer 580085. What have I done wrong.

Please help.

Eddie

User avatar
JBJ
Posts: 1263
Joined: Fri Dec 12, 2008 6:20 pm UTC
Location: a point or extent in space

Re: Project Euler

Postby JBJ » Mon Jul 06, 2009 8:38 pm UTC

fungfat wrote:I was desperate about problem 3. Can someone help?

Problem 3 said that "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."

I found the answer is 995 x 583 = 580085. But Project Euler said it is wrong. I tried another method and still came up with the same answer 580085. What have I done wrong.

Please help.

Eddie

There is a larger number. Of course the spirit of Euler prevents us (at least me) from just giving out the answer. Can you post your code?
So, you sacked the cocky khaki Kicky Sack sock plucker?
The second cocky khaki Kicky Sack sock plucker I've sacked since the sixth sitting sheet slitter got sick.

fungfat
Posts: 5
Joined: Mon Jul 06, 2009 8:13 pm UTC

Re: Project Euler

Postby fungfat » Mon Jul 06, 2009 9:38 pm UTC

I have done it in html, and then excel macro. I attached both codes here.

rem ------------------------------------------------------------------------
rem this is visual basic code
rem ------------------------------------------------------------------------
For i = 999 To 100 Step -1
For j = 999 To 100 Step -1
n = i * j
f3 = Mid(n, 1, 3)
b3 = Mid(n, 6, 1) & Mid(n, 5, 1) & Mid(n, 4, 1)
If f3 = b3 Then
MsgBox "answer is: " & i & " * " & j & " = " & n & ", and f3 = " & f3 & " and b3 = " & b3
i = 0
j = 0
End If
Next j
Next i




<html>

<!- ----------------- ->
<!- This is html code ->
<!- ----------------- ->
<head>
<Script language="JavaScript" >


function calsum()
{
mainform.bsum.value = "Calculating greatest numeral palindrome for " + mainform.maxnum.value + ". Please wait...";

var sd = new Date();
var stime = sd.getTime();


var nroote = parseInt(Math.sqrt(mainform.maxnum.value));
var newnum = mainform.maxnum.value;
var n1 = 999;
var n2 = 999;
var countl=0;
var result_text = "** cannot find **";

//------------------------------------------------------
// processing loop...
//------------------------------------------------------
var nproduct = n1 * n2;
var sproduct = nproduct.toString();
var s1 = sproduct.substring(0,3);
var s2 = sproduct.substring(3,3);

var j=0;
var i=0;
var t="";
for (j=999; j>100; j--) {
n1 = j;
for (i=999; i>500; i--) {
countl++;
nproduct = n1 * i;
sproduct = nproduct.toString();
s1 = sproduct.substring(0,3);
s2 = sproduct.substring(5,6) + sproduct.substring(4,5) + sproduct.substring(3,4);
if ( s1 == s2 ) {
n2 = i;
i = -999;
result_text = " " + sproduct + " = " + n1 + " * " + n2;
}
} // inner for...

if ( i < -99 ) { j = -999; } // exit out loop if answer is found...
} // outer for...

//------------------------------------------------------
// End processing loop...
//------------------------------------------------------

var ed = new Date();
var etime = ed.getTime();
var dtime = etime-stime;
var showtime = dtime + " ms";
var sec = 0;

if ( dtime > 1000 ) {
sec = parseInt(dtime / 1000); // parseInt requires capital I...
dtime = dtime - sec * 1000;
showtime = sec + " sec " + dtime + " ms";
}

mainform.bsum.value = "\nLargest numeral palindrome for " + mainform.maxnum.value + " digit number is " + result_text + " and looped " + countl + " times and ran for " + showtime + ".";
mainform.bsum.value = mainform.bsum.value + ". \n\nTry another x value and click this button.\n\n";
mainform.maxnum.focus();
return false;
}
</script>
</head>
<title>Project Euler - Problem one</title>


<body>
<center>
<FORM NAME="mainform" onSubmit="return(calsum())">
<table>
<tr>
<td bgcolor=yellow>Problem 4: Padindrome Number</td>
</tr>
<tr>
<td> A palindromic number reads the same both ways. The largest palindrome made from <br>
the product of two 2-digit numbers is 9009 = 91 99. <br><br>
What is the largest palindrome number by multipying two x digits numbers (default to 3) ?
</td>
</tr>
<tr>
<td> <br>
My way:
<br><br>
Enter the x value to calculate the greatest numeral palindrome for production of two x digits numbers: &nbsp;&nbsp;&nbsp;
<INPUT TYPE="TEXT" SIZE=30 NAME="maxnum" value=3>
<br><br>
</td>
</tr>
<tr>
<td>
<INPUT type="button" name=bsum value="Click to find answer for the above x value: " OnClick=calsum() >
</td>
</tr>
</table>
</form>

<script>
mainform.maxnum.focus();
</script>
</body>
</html>

fungfat
Posts: 5
Joined: Mon Jul 06, 2009 8:13 pm UTC

Re: Project Euler

Postby fungfat » Mon Jul 06, 2009 11:23 pm UTC

JBJ wrote:
fungfat wrote:I was desperate about problem 3. Can someone help?

Problem 3 said that "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."

I found the answer is 995 x 583 = 580085. But Project Euler said it is wrong. I tried another method and still came up with the same answer 580085. What have I done wrong.

Please help.

Eddie

There is a larger number. Of course the spirit of Euler prevents us (at least me) from just giving out the answer. Can you post your code?



Actually, if you can tell me what the largest palindromic number is for problem 3, I can figure out what is wrong with my code.

Eddie

User avatar
phlip
Restorer of Worlds
Posts: 7573
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Project Euler

Postby phlip » Tue Jul 07, 2009 12:03 am UTC

So, your code tries 999 * everything, and if none of them are palindromic it then tries 998 * everything, and so on... and you end up with 995 * 583.

But that only maximises one of the two multiplicands, not the product... imagine if, say, 991 * 990 was palindromic (it's not, but consider if it was)... it would be much bigger than 995 * 583, since both of the multiplicands are large numbers... but your algorithm wouldn't find it, because 991 < 995.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

stephentyrone
Posts: 778
Joined: Mon Aug 11, 2008 10:58 pm UTC
Location: Palo Alto, CA

Re: Project Euler

Postby stephentyrone » Tue Jul 07, 2009 12:06 am UTC

phlip wrote:So, your code tries 999 * everything, and if none of them are palindromic it then tries 998 * everything, and so on... and you end up with 995 * 583.


That's not quite it, because 999*91 = 90909. fungfat, you really should just post your code so that we don't need to engage in speculation.

As long as we're speculating though, my guess is what phlip said together with the check for palindromes only working for 6-digit numbers.

Edit: oh, his code is already there, I just didn't recognize that as code when skimming through the thread.
Last edited by stephentyrone on Tue Jul 07, 2009 1:32 am UTC, edited 1 time in total.
GENERATION -16 + 31i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

User avatar
phlip
Restorer of Worlds
Posts: 7573
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Project Euler

Postby phlip » Tue Jul 07, 2009 12:31 am UTC

stephentyrone wrote:That's not quite it, because 999*91 = 90909.

Yeah, but his code only counts down to 100... so it doesn't try 91.

stephentyrone wrote:fungfat, you really should just post your code so that we don't need to engage in speculation.

He... already has. It's right there.

stephentyrone wrote:As long as we're speculating though, my guess is what phlip said together with the check for palindromes only working for 6-digit numbers.

The 6-digit thing is reasonable though... since we know there's at least one suitable 6-digit palindrome, so the answer must be bigger than that, and the number must be smaller than 999*999 which is also 6-digits.

So while it would be better form to have a length-agnostic "is this a palindrome" function, it's still correct as-is.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

Agent_Irons
Posts: 213
Joined: Wed Sep 10, 2008 3:54 am UTC

Re: Project Euler

Postby Agent_Irons » Tue Jul 07, 2009 2:50 pm UTC

I'm going to go with the early termination problem. Just find all palindromes, and if you find one larger than the current largest palindrome replace it. And so on. When you've tested all the combinations all the way down to 100x100 (definitely not the answer) the remaining largest palindrome must be the answer.

python code snippet:
Spoiler:

Code: Select all

if list(str(x*y)) == list(str(x*y))[::-1]:
    listpalindromes.append(x*y)
#loops and initializations left as an exercise for the reader.


I believe you might also mean problem 4. Problem three is the one about factoring a very large number.

User avatar
JBJ
Posts: 1263
Joined: Fri Dec 12, 2008 6:20 pm UTC
Location: a point or extent in space

Re: Project Euler

Postby JBJ » Tue Jul 07, 2009 2:53 pm UTC

First, I went back through my Euler folder, and this isn't problem #3, it's #4.
Project Euler #4 wrote: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.


A brute force method works okay in this instance, there are 899 3 digit numbers (100-999) which would be just over 800,000 iterations if you for-next from 100-999. That should only take a couple of seconds.

And as Philip pointed out, you are only testing the first multiplicand, not the product.

Your test for a six digit number is okay, but if you're using VB, why not use the StrReverse function?
n = i*j
If CStr(n) = StrReverse(CStr(n)) Then '// proof of palindrome

Then, you need to test if n is larger than any previous palindromic n's found.
Use another variable, say x, and initially assign it a very small value like 101.
Test if n is greater than x, and if so, reassign x as n.
When the loops finish, x will be your answer.

Note: The solution in VB with brute force and no optimization takes about 2-3 seconds for 810,000 iterations. Optimized, it runs in less than 1/10th of a second and goes through less than 10,000 iterations. That should give you something to shoot for if you are using Euler to brush up your optimization skills.

EDIT - (ninja'd on the problem number)
Agent_Irons wrote:I'm going to go with the early termination problem. Just find all palindromes, and if you find one larger than the current largest palindrome replace it. And so on. When you've tested all the combinations all the way down to 100x100 (definitely not the answer) the remaining largest palindrome must be the answer.


The problem there is that not all palindromes are the product of two 3-digit numbers. 999,999 is palindromic, but is 999 * 1001, 998,899 is also palindromic, but is 781 * 1279
So, you sacked the cocky khaki Kicky Sack sock plucker?
The second cocky khaki Kicky Sack sock plucker I've sacked since the sixth sitting sheet slitter got sick.

User avatar
Qoppa
Posts: 694
Joined: Sat Nov 24, 2007 9:32 pm UTC
Location: Yes.

Re: Project Euler

Postby Qoppa » Tue Jul 07, 2009 4:36 pm UTC

Arrggh... My efficient algorithm for problem 18/67 is so close. It gives me the correct answer for the 4 row triangle example, and it can get me an answer for both 18 and 67 in a reasonable amount of time (instantly for 18, 30 seconds for 67), but it's not quite working and I can't figure out why. The answer it gives me for 18 is off by 10, and I don't know how off my answer for 67 is... I've been staring at my code for at least an hour now, and I still can't see anything obviously wrong with my algorithm. Baah!

Code: Select all

_=0,w=-1,(*t)(int,int);a()??<char*p="[gd\
~/d~/\\b\x7F\177l*~/~djal{x}h!\005h";(++w
<033)?(putchar((*t)(w??(p:>,w?_:0XD)),a()
):0;%>O(x,l)??<_='['/7;{return!(x%(_-11))
?x??'l:x^(1+ ++l);}??>main(){t=&O;w=a();}

User avatar
xulaus
Posts: 136
Joined: Thu Jul 03, 2008 11:09 am UTC

Re: Project Euler

Postby xulaus » Tue Jul 07, 2009 5:03 pm UTC

Qoppa wrote:Arrggh... My efficient algorithm for problem 18/67 is so close...

Oh man, I remember that one. I had the hardest time just thinking of an efficent algorithm. I was so pleased with myself when I got it. Do you need some help, or was that just a rant?
Meaux_Pas wrote:I don't even know who the fuck this guy is

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Project Euler

Postby jaap » Tue Jul 07, 2009 5:16 pm UTC

Qoppa wrote:Arrggh... My efficient algorithm [...] can get me an answer for both 18 and 67 in a reasonable amount of time (instantly for 18, 30 seconds for 67)


My program answers problem 67 instantly (less than a millisecond). I'm not saying this to brag, but just to point out that you are probably not doing this in the best or easiest way. It is only half a dozen lines of code (excluding the initialisation of the triangular array).
Minor hint:
Spoiler:
Try working through the triangle from the bottom upwards. Although you can do it in either direction, thinking about doing it bottom-up might make things click.

User avatar
Qoppa
Posts: 694
Joined: Sat Nov 24, 2007 9:32 pm UTC
Location: Yes.

Re: Project Euler

Postby Qoppa » Tue Jul 07, 2009 5:16 pm UTC

Mostly just a rant. The problem I have has to be a stupid small thing, because the algorithm I've coded up should work provided I actually typed everything out correctly.
Last edited by Qoppa on Tue Jul 07, 2009 5:26 pm UTC, edited 1 time in total.

Code: Select all

_=0,w=-1,(*t)(int,int);a()??<char*p="[gd\
~/d~/\\b\x7F\177l*~/~djal{x}h!\005h";(++w
<033)?(putchar((*t)(w??(p:>,w?_:0XD)),a()
):0;%>O(x,l)??<_='['/7;{return!(x%(_-11))
?x??'l:x^(1+ ++l);}??>main(){t=&O;w=a();}

fungfat
Posts: 5
Joined: Mon Jul 06, 2009 8:13 pm UTC

Re: Project Euler

Postby fungfat » Tue Jul 07, 2009 5:25 pm UTC

phlip wrote:So, your code tries 999 * everything, and if none of them are palindromic it then tries 998 * everything, and so on... and you end up with 995 * 583.

But that only maximises one of the two multiplicands, not the product... imagine if, say, 991 * 990 was palindromic (it's not, but consider if it was)... it would be much bigger than 995 * 583, since both of the multiplicands are large numbers... but your algorithm wouldn't find it, because 991 < 995.


Thanks Phlip, it works. I found the answer
Spoiler:
906609 = 993 * 913
in 405450 iteration using about 8 seconds running in Javascript. I will play with some optimisation such as concentrate the iteration in the higher number operands.
Last edited by phlip on Wed Jul 08, 2009 12:08 am UTC, edited 1 time in total.
Reason: Put a spoiler around answer

Agent_Irons
Posts: 213
Joined: Wed Sep 10, 2008 3:54 am UTC

Re: Project Euler

Postby Agent_Irons » Tue Jul 07, 2009 5:28 pm UTC

JBJ wrote:
Agent_Irons wrote:I'm going to go with the early termination problem. Just find all palindromes, and if you find one larger than the current largest palindrome replace it. And so on. When you've tested all the combinations all the way down to 100x100 (definitely not the answer) the remaining largest palindrome must be the answer.


The problem there is that not all palindromes are the product of two 3-digit numbers. 999,999 is palindromic, but is 999 * 1001, 998,899 is also palindromic, but is 781 * 1279

I meant all palindromes that are products of two three digit numbers. I don't really see how to optimize this, other than trying for the largest products first, and trimming out the duplicates. 999x998 = 998x999, after all.

Edit: @v I like that solution very much. It goes against my algorithm sense, because I have operations with primes filed under "computationally expensive" in my head. A lot of these project Euler problems boil down to factoring things. No huge surprises there I guess.
Last edited by Agent_Irons on Tue Jul 07, 2009 6:26 pm UTC, edited 1 time in total.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Project Euler

Postby Berengal » Tue Jul 07, 2009 5:47 pm UTC

Agent_Irons wrote:I'm going to go with the early termination problem. Just find all palindromes, and if you find one larger than the current largest palindrome replace it. And so on. When you've tested all the combinations all the way down to 100x100 (definitely not the answer) the remaining largest palindrome must be the answer.
Actually, if you count down, you only need to find the first, since all other palindromes will be smaller.

Code: Select all

def p4():
    for n in range(999,99,-1):
        n = int(str(n)+str(n)[::-1])
        t = [d for d in divisors(n) if len(str(d)) == 3]
        for (x,y) in ((x, y) for x, y in product(t, t) if x*y == n):
            return x*y

'product' found in itertools. Implementation of 'divisors' is left as an excercise for the reader. This code is faster on my machine than going the other way around (looping through possible factors and filtering the non-palindrome-producing ones), probably because of early-termination. My code's outer loop is run at most 899 times, my code's inner loop returns once it's run. There are som hidden loops in 'product' and 'divisor', but they're asymptotically constant.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
JBJ
Posts: 1263
Joined: Fri Dec 12, 2008 6:20 pm UTC
Location: a point or extent in space

Re: Project Euler

Postby JBJ » Tue Jul 07, 2009 6:40 pm UTC

Agent_Irons wrote:
JBJ wrote:
Agent_Irons wrote:I'm going to go with the early termination problem. Just find all palindromes, and if you find one larger than the current largest palindrome replace it. And so on. When you've tested all the combinations all the way down to 100x100 (definitely not the answer) the remaining largest palindrome must be the answer.


The problem there is that not all palindromes are the product of two 3-digit numbers. 999,999 is palindromic, but is 999 * 1001, 998,899 is also palindromic, but is 781 * 1279

I meant all palindromes that are products of two three digit numbers. I don't really see how to optimize this, other than trying for the largest products first, and trimming out the duplicates. 999x998 = 998x999, after all.

I see now. I tried that, but still got better performance the other way.

VB Script - runs in .03 seconds on my laptop, and loops 6,124 times
Spoiler:

Code: Select all

answer = 100*100
for a = 999 to 100 step -1
for b = a to 100 step -1
   prod = a * b
   if prod < answer Then
      Exit For
   End If
   If CStr(prod) = StrReverse(Cstr(prod)) Then
      if prod > answer then
         answer = prod
      End If
   End If
next
next
WScript.echo answer


I tried your approach of going top down finding palindromes along the way, checking if they are the product of two 3-digit numbers, and terminating early on discovery. It took .25 seconds on my laptop and loops 52,869 times.
Spoiler:

Code: Select all

for a = 999999 to 100000 step -1
   If CStr(a) = StrReverse(CStr(a)) Then
   for b = 999 to 100 step - 1
      If a mod b = 0 Then
         If Len(a/b) = 3 Then
            WScript.echo a
            WScript.quit
         End If
         Exit For
      End If
   Next
   End If
Next
Only major optimization is exiting the inner loop on discovery of the first 3 digit integer factor. I can't think of a way to make it faster than that at the moment.

Both are considerably faster than a true brute force, and both could be enhanced a little more by refining the bounds (i.e. we know it will likely be two numbers in the 900's, so we could just check from 900-999) but the performance gained is almost trivial at that point.

*Edit - fixed small bug that Berengal pointed out.
Last edited by JBJ on Tue Jul 07, 2009 7:44 pm UTC, edited 1 time in total.
So, you sacked the cocky khaki Kicky Sack sock plucker?
The second cocky khaki Kicky Sack sock plucker I've sacked since the sixth sitting sheet slitter got sick.

eric.lifka
Posts: 10
Joined: Thu May 21, 2009 1:58 am UTC

Re: Project Euler

Postby eric.lifka » Tue Jul 07, 2009 7:17 pm UTC

inspired by the previous posts on problem 4, I worked on getting it's time down as much as I could. I think I've got it as low as it will go, about .015 seconds per run.

Can anyone see anything I could improve or am I knocking on the lower limits?

Spoiler:
I started with 999, working down, finding the largest palindrome of each number, so for 999 the first time I find a palindrome (again working down from 999) I take that as the max palindrome for 999, moving on to find the max for 998. But the other thing I do, as I'm working down the inner list, trying to find the largest palindrome for say 997, I check to see if I've fallen below the potential for a new max. ie, if the old max was 9009, then if the number I'm testing and the current number in the test list (999...99) cannot surpass that max, then I won't find a new maximum anyway so I take 0 for that number. Maybe I should just let the code talk, I don't feel like I'm explaining myself very well. Anyway, does anyone see any improvements?

Code: Select all

#! python

def findBigestPalindrome():
   largest = 0
   for i in range(999, 99, -1):
      if i * 999 < largest:
         return largest
      tmp = getPalindrome(i, largest)
      if tmp > largest:
         largest = tmp
   return largest

def getPalindrome(num, max):
   for i in range(999, 99, -1):
      test = i * num
      if test < max:
         return 0
      if str(test) == str(test)[::-1]:
         return test
   return 0

if __name__ == "__main__":
   from time import time
   tstart = time()
   result = findBigestPalindrome()
   tstop = time()
   print ("result: " + str(result) + "\nfound in " + str(tstop - tstart) + " seconds.\n")


Thanks!


EDIT: I realized I didn't really take bounds into account, so just to see pushed the lower bound up to 900 instead of 99, but the time didn't change at all, staying right around .015.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Project Euler

Postby Berengal » Tue Jul 07, 2009 7:35 pm UTC

JBJ wrote:Both are considerably faster than a true brute force
The last piece of code is a true brute force. It checks every number if it's palindrome, then checks every possible three-digit factor to see if it's a factor. The only way it could be even more brute force would be if you brute-forced the second factor as well, but I'm not sure how to do that in a plausible way.

A good implementation loops at most 10^n - 10^(n-1) - 1 times for the highest n-digit. That is an upper bound almost seven times as lower than your actual loop count, and in the case of n = 3, it has an actual loop count of 94, almost 65 times lower than your actual.

Also, your first code piece has a bug: it doesn't check the cases where both three-digit factors are equal (which is the case for eight six-digit palindromes).

eric.lifka wrote:Can anyone see anything I could improve or am I knocking on the lower limits?

Code: Select all

def p4(digits = 3):
    for n in range((10**digits)-1, (10**(digits-1))-1, -1):
        n = int(str(n)+str(n)[::-1])
        t = [d for d in divisors(n) if len(str(d)) == digits]
        for (x,y) in ((x, y) for x, y in product(t, t) if x*y == n):
            yield x, y, x*y

def p4alt(digits = 3):
    return ((x, y, x*y) for x in range(10**digits - 1,10**(digits-1) - 1,-1) for y in range(x, 10**(digits-1) - 1, -1) if str(x*y) == str(x*y)[::-1])

def findBigestPalindrome():
   largest = 0
   for i in range(999, 99, -1):
      if i * 999 < largest:
         return largest
      tmp = getPalindrome(i, largest)
      if tmp > largest:
         largest = tmp
   return largest

########

>>> timeit(lambda:findBigestPalindrome(), number=10)
0.083815686
>>> timeit(lambda:next(p4()), number = 10)
0.05191168200000007
>>> timeit(lambda:max(p4alt()), number = 10)
3.8289639840000014


Mine is p4 (needs next called on it), the "for x in [999..100]; for y in [x .. 100];" is p4alt (needs max). I haven't looked at optimizing beyond the foundational algorithm.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

fungfat
Posts: 5
Joined: Mon Jul 06, 2009 8:13 pm UTC

Re: Project Euler

Postby fungfat » Tue Jul 07, 2009 11:03 pm UTC

Agent_Irons wrote:
JBJ wrote:
Agent_Irons wrote:I'm going to go with the early termination problem. Just find all palindromes, and if you find one larger than the current largest palindrome replace it. And so on. When you've tested all the combinations all the way down to 100x100 (definitely not the answer) the remaining largest palindrome must be the answer.


The problem there is that not all palindromes are the product of two 3-digit numbers. 999,999 is palindromic, but is 999 * 1001, 998,899 is also palindromic, but is 781 * 1279

I meant all palindromes that are products of two three digit numbers. I don't really see how to optimize this, other than trying for the largest products first, and trimming out the duplicates. 999x998 = 998x999, after all.

Edit: @v I like that solution very much. It goes against my algorithm sense, because I have operations with primes filed under "computationally expensive" in my head. A lot of these project Euler problems boil down to factoring things. No huge surprises there I guess.


I actually can optimise and get the answer in 8100 iterations in 0.2 seconds (compared to 405450 in 8 seconds). I started with 9xx times 9xx...1xx, and do not do 8xx times 8xx..1xx if a palindomic number is obtained. I also use only the first operand if they are multiple of 11. This idea is obtained from the Project Euler official solution, which is only available if you entered the correct answer for the problem.

Agent_Irons
Posts: 213
Joined: Wed Sep 10, 2008 3:54 am UTC

Re: Project Euler

Postby Agent_Irons » Wed Jul 08, 2009 12:27 am UTC

As far as time attacks go I'm sure we could get the speed down farther. Anyone want to implement this in Assembly?

User avatar
RoadieRich
The Black Hand
Posts: 1037
Joined: Tue Feb 12, 2008 11:40 am UTC
Location: Behind you

Re: Project Euler

Postby RoadieRich » Wed Jul 08, 2009 3:40 am UTC

jaap wrote:My program answers problem 67 instantly (less than a millisecond). I'm not saying this to brag, but just to point out that you are probably not doing this in the best or easiest way. It is only half a dozen lines of code (excluding the initialisation of the triangular array).

Your hint got to a solution for this, in just four lines of code, excluding setup and output, with times as fast as you could care for.
It could probably be twerked for speed, but I usually prefer* pythonic, rather than fast, code.
Spoiler:

Code: Select all

#input is a list of lists containing the triangle data.
output = input[:]

for i, row in reversed(list(enumerate(input[:-1]))):
    for j, val in enumerate(row):
        output[i][j] = input[i][j] + max(output[i+1][j], output[i+1][j+1])

print "Answer is", output[0][0]


What language is your <1ms solution in?


*See my prime iterator in coding: hacks and snippets for an example of the alternative.
73, de KE8BSL loc EN26.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Project Euler

Postby jaap » Wed Jul 08, 2009 6:05 am UTC

RoadieRich wrote:
jaap wrote:My program answers problem 67 instantly
Your hint got to a solution for this, in just four lines of code, excluding setup and output, with times as fast as you could care for.
[...]
What language is your <1ms solution in?
I did it in Java, and you found the exact same algorithm as me.

User avatar
Josephine
Posts: 2142
Joined: Wed Apr 08, 2009 5:53 am UTC

Re: Project Euler

Postby Josephine » Wed Jul 08, 2009 8:32 am UTC

I uh... think I did about the most inefficient way of solving problem 10 ever. I basically took an existing primality tester and modified it with total = total + i. Any suggestions?

Code: Select all

import math
print "2,3,"
state = 1
total = 0
for i in range(4, 2000000):
   upper = math.sqrt(i)
   upper = int(upper)
   for thing in range(2, upper):
      state = 1
      if (i % thing == 0):
         state = 0
         break
   if (state == 1):
      total = total + i
      print total,
exit
Belial wrote:Listen, what I'm saying is that he committed a felony with a zoo animal.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Project Euler

Postby jaap » Wed Jul 08, 2009 8:58 am UTC

nbonaparte1 wrote:I uh... think I did about the most inefficient way of solving problem 10 ever. I basically took an existing primality tester and modified it with total = total + i. Any suggestions?

http://en.wikipedia.org/wiki/Eratosthenes_Sieve

User avatar
Josephine
Posts: 2142
Joined: Wed Apr 08, 2009 5:53 am UTC

Re: Project Euler

Postby Josephine » Wed Jul 08, 2009 9:03 am UTC

ah, right. That. Forgot about that. I'm still going to leave Python running overnight, see if it gets the answer in any reasonable timeframe.
Belial wrote:Listen, what I'm saying is that he committed a felony with a zoo animal.

User avatar
RoadieRich
The Black Hand
Posts: 1037
Joined: Tue Feb 12, 2008 11:40 am UTC
Location: Behind you

Re: Project Euler

Postby RoadieRich » Wed Jul 08, 2009 9:23 am UTC

Remove the print statement from the loop. It'll speed up considerably.
73, de KE8BSL loc EN26.

User avatar
Qoppa
Posts: 694
Joined: Sat Nov 24, 2007 9:32 pm UTC
Location: Yes.

Re: Project Euler

Postby Qoppa » Wed Jul 08, 2009 3:16 pm UTC

Well I got number 67 finally, and interestingly enough, what I ended up doing to fix it brought the execution time down to 16 milliseconds for the 100 line triange. Nice! I also used a different algorithm than the one posted here (mine started off as a variation on Dijkstra's algorithm, but it's now quite different).

Code: Select all

_=0,w=-1,(*t)(int,int);a()??<char*p="[gd\
~/d~/\\b\x7F\177l*~/~djal{x}h!\005h";(++w
<033)?(putchar((*t)(w??(p:>,w?_:0XD)),a()
):0;%>O(x,l)??<_='['/7;{return!(x%(_-11))
?x??'l:x^(1+ ++l);}??>main(){t=&O;w=a();}

User avatar
xulaus
Posts: 136
Joined: Thu Jul 03, 2008 11:09 am UTC

Re: Project Euler

Postby xulaus » Wed Jul 08, 2009 4:15 pm UTC

Qoppa wrote:(mine started off as a variation on Dijkstra's algorithm, but it's now quite different).

That's a novel approach. Kudos. How well did Dijkstra's algorithm perform, or did you modify it before testing?
Meaux_Pas wrote:I don't even know who the fuck this guy is

User avatar
Qoppa
Posts: 694
Joined: Sat Nov 24, 2007 9:32 pm UTC
Location: Yes.

Re: Project Euler

Postby Qoppa » Wed Jul 08, 2009 4:33 pm UTC

Well Dijkstra's didn't work (I was 10 off for whatever reason on the smaller triangle), and it was what took 30 seconds for the larger triangle, though my implementation was admittedly very unoptimized. I'm still unsure why it didn't work though, since I can't see any flaw in what I was doing. I tried both just modifying it to find the longest path rather than the shortest, and also taking 1/v and finding the shortest path, but neither worked for whatever reason.
Spoiler:
I eventually got it to work by just processing the vertices in order from top to bottom rather than taking the vertex with the current longest/shortest path.

Code: Select all

_=0,w=-1,(*t)(int,int);a()??<char*p="[gd\
~/d~/\\b\x7F\177l*~/~djal{x}h!\005h";(++w
<033)?(putchar((*t)(w??(p:>,w?_:0XD)),a()
):0;%>O(x,l)??<_='['/7;{return!(x%(_-11))
?x??'l:x^(1+ ++l);}??>main(){t=&O;w=a();}

User avatar
xulaus
Posts: 136
Joined: Thu Jul 03, 2008 11:09 am UTC

Re: Project Euler

Postby xulaus » Wed Jul 08, 2009 10:08 pm UTC

Qoppa wrote:Well Dijkstra's didn't work (I was 10 off for whatever reason on the smaller triangle), and it was what took 30 seconds for the larger triangle, though my implementation was admittedly very unoptimized. I'm still unsure why it didn't work though, since I can't see any flaw in what I was doing. I tried both just modifying it to find the longest path rather than the shortest, and also taking 1/v and finding the shortest path, but neither worked for whatever reason.
Spoiler:
I eventually got it to work by just processing the vertices in order from top to bottom rather than taking the vertex with the current longest/shortest path.

It's a shame that didn't work, it would have been a neat little program if it had.
Meaux_Pas wrote:I don't even know who the fuck this guy is

Dongorath
Posts: 93
Joined: Tue Oct 16, 2007 1:17 pm UTC

Re: Project Euler

Postby Dongorath » Thu Jul 09, 2009 8:35 am UTC

I didn't want to work, so I decided to try PE#87. Quite easy if you don't do stupid errors in your code, but the worst part ? Checking for duplicate results ! Checking at insertion ? Slow as hell !!! Eventually, I remebered that :
Spoiler:
Sort() is your friend ! Insert every single result in a List<T> and then Sort() ! Then, just count every element which is different from the previous one !

User avatar
JBJ
Posts: 1263
Joined: Fri Dec 12, 2008 6:20 pm UTC
Location: a point or extent in space

Re: Project Euler

Postby JBJ » Thu Jul 09, 2009 4:00 pm UTC

I'm having a bugger of a time with #87
This is the approach I took, tell me if I'm way of base or not.

First I find the largest prime, which when squared, is still less than 50 million.
That's 7069, and 70692 = 49,970,761
I square and put all primes below that into an array.
There are 908 squared primes in that array (22,32,52,72...,70692) -> (4,9,25,49,...,49970761)

I then do the same for cubed primes, and primes to the fourth power, and they are in their respective arrays.
There are 73 primes when cubed remain less than 50 million. Top one being 367, and 3673 = 49,430,863
There are 23 primes when taken to the 4th power are less than 50 million. Top one is 83, 834 = 47,458,321

So I have 73*23 = 1679 possible combinations of p3 and p4 sums. Several of those sums will exceed 50 million, so I eliminate those and I end up with a total of 1,552 p3 + p4 combinations.

So now I have 1,552 * 908 = 1,409,216 possible combinations of p2 and (p3+p4), and of course some of those will exceed 50 million, so I only count the ones that don't. I end up with 1,139,575 which Euler tells me is wrong.

FYI, the largest number I get under 50 million is 49,999,927 which is 49672 + 1733 + 674
As best I can tell, I'm not getting any duplicates. I know for certain that all 1,552 p3 and p4 combinations are unique.

Am I even close?
So, you sacked the cocky khaki Kicky Sack sock plucker?
The second cocky khaki Kicky Sack sock plucker I've sacked since the sixth sitting sheet slitter got sick.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Project Euler

Postby Berengal » Thu Jul 09, 2009 5:34 pm UTC

All the combinations are unique, but are all the results?

My approach was similar to your, but my reasoning was somewhat more simplistic.

Define the sets [imath]S[/imath], [imath]C[/imath] and [imath]F[/imath] to be the all squared, cubed and fourth-powered primes below 50,000,000. Define the set [imath]A[/imath]: [math]\forall a. a \in A \to a \lt 50000000 \wedge a = s + c + f \wedge (s, c, f) \in (S * C * F)[/math]
The answer is the size of the set [imath]A[/imath]
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

Dongorath
Posts: 93
Joined: Tue Oct 16, 2007 1:17 pm UTC

Re: Project Euler

Postby Dongorath » Fri Jul 10, 2009 8:51 am UTC

@JBJ : as Berengal and I said, some numbers can be written as different sums, thus you have to check for duplicate results. I proposed a solution in my spoiler, Berengal proposes to use a set.

@Berengal : this one liner seems so simple... I wish it was this easy to do that in C#...


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 8 guests