## Project Euler

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

Moderators: phlip, Moderators General, Prelates

Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Project Euler

You absolutely, positively have to implement some prime/factoring functions. You won't get very far without that. If your language doesn't have decent matrix support, then yeah, go ahead and write some of that as well.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

Functions (and type signature) in my personal hacker library I've had the most use for in PE problems:

primes :: [Integer] (Infinite list of all primes)
isPrime :: Integer -> Bool
factorize :: Integer -> [Integer]
factors :: Integer -> [Integer] (same as factorize, but each appears only once)
fibs :: [Integer] (fibonacci sequence)
permute :: [a] -> [[a]]
isPalindrome :: (Eq a) => [a] -> Bool
powerSet :: [a] -> [[a]]
divisors :: Integer -> [Integer]
contains' :: (Ord a) => a -> [a] -> Bool (True if an element is in a list, assuming the list is sorted. Works on infinite lists)

I haven't had any use for matrixes myself so far, but I don't really know any matrix math so I wouldn't know how to use it properly.
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.

mabufo
Posts: 105
Joined: Sun Sep 09, 2007 11:17 pm UTC

### Re: Project Euler

Berengal wrote:Functions (and type signature) in my personal hacker library I've had the most use for in PE problems:

primes :: [Integer] (Infinite list of all primes)
isPrime :: Integer -> Bool
factorize :: Integer -> [Integer]
factors :: Integer -> [Integer] (same as factorize, but each appears only once)
fibs :: [Integer] (fibonacci sequence)
permute :: [a] -> [[a]]
isPalindrome :: (Eq a) => [a] -> Bool
powerSet :: [a] -> [[a]]
divisors :: Integer -> [Integer]
contains' :: (Ord a) => a -> [a] -> Bool (True if an element is in a list, assuming the list is sorted. Works on infinite lists)

I haven't had any use for matrixes myself so far, but I don't really know any matrix math so I wouldn't know how to use it properly.

Thank you for the list. Forgive me for asking though, what is powerset and permute?

Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Project Euler

(powerset '(1 2 3)) => (nil (1) (2) (3) (1 2) (1 3) (2 3) (1 2 3))

(permute '(1 2 3)) => ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Posts: 3072
Joined: Mon Oct 22, 2007 5:28 pm UTC
Location: Beaming you up

### Re: Project Euler

Xanthir wrote:(powerset '(1 2 3)) => (nil (1) (2) (3) (1 2) (1 3) (2 3) (1 2 3))

(permute '(1 2 3)) => ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))

Those would be useful even outside PE problems.
<quintopia> You're not crazy. you're the goddamn headprogrammingspock!
<Cheese> I love you

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

### Re: Project Euler

Xanthir wrote:You absolutely, positively have to implement some prime/factoring functions. You won't get very far without that. If your language doesn't have decent matrix support, then waffle, go ahead and write some of that as well.

I heartily agree with getting/creating some standard functions for PE.
I only learned of PE about a week ago (Thanks XKCD!) and so far have finished 15 of the easy ones.

I'm doing them in VBScript, which admittedly doesn't have the greatest math ability. All the more challenging, eh?
But the loose data types allowed me to create some functions for adding and multiplying very large numbers ( > 1.7 E308) by converting them to strings and running them through basic multiplying and adding algorithms. This came in pretty useful for some of the questions for adding the sum of digit questions, or like Q25, the first Fibonacci to have 1000 digits. Got the answer in less than 15 seconds.

I've also got a basic prime generator and prime test which worked fine for the first few problems, although I should probably look into finding a more streamlined one. Q10 for finding the sum of all primes below 2 million slightly exceeded the 1-minute guideline. Okay, it took two minutes. I didn't revamp that one since I still got the answer in what I considered a reasonable amount of time, but I know I'll have to going forward.
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.

Gumbitha
Posts: 10
Joined: Tue Feb 24, 2009 6:49 am UTC

### Re: Project Euler

I'm stuck on number 10. Both methods of prime number generation I have seem to give the same exact answer,
Spoiler:
1179908154

Which is regarded as wrong.

My "solution":
Spoiler:

Code: Select all

/*The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.Find the sum of all the primes below two million.*/ #include <iostream>#include <cmath>using namespace std;int main(void) {   int root = 1;   int n = 3;   int p = 1;   int prime = 1;   int c = 0;   int sum = 2;   static int PRIMELIST[1000000] = {2};      for (int i = 3; i < 2000000; i+=2) {      root = sqrt((double)i) + 1;       for(c = 0; PRIMELIST[c] < root && PRIMELIST[c] != '\0'; c++) {      if (i % PRIMELIST[c] == 0) {         prime = 0;               //cout << i << " is not prime " << PRIMELIST[c] << " is a factor \n";         break;         }      }      if (prime == 1) {            cout << i << " is prime " << p + 1 << "\n" ;         PRIMELIST[p] = i;         p++;         sum += i;      }               prime = 1;         }   cout << "Sum is " << sum << "\n";return 0;   }/*int main(void) {   int root = 1;   int n = 3;   int p = 1;   int prime = 1;   int sum = 2;   for (int i = 3; i < 2000000; i+=2) {      root = sqrt((double)i) + 1;      for (n = 3; n <= root; n += 2){         if (i % n == 0) {            prime = 0;                  //cout << i << " is not prime " << n << " is a factor \n";            break;         }      }      if (prime == 1) {         p++;         cout << i << " is prime " << p + 1 << "\n" ;         sum += i;      }               prime = 1;   }   cout << "Sum is " << sum << "\n";return 0;   }*/

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

Spoiler:
unsigned long
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.

Gumbitha
Posts: 10
Joined: Tue Feb 24, 2009 6:49 am UTC

### Re: Project Euler

Oh, stupid me. I was going to change that and forgot. Many thanks

Guff
Posts: 165
Joined: Thu Jan 03, 2008 11:56 pm UTC

### Re: Project Euler

I just made it to Level 2.

I also just looked at 234, and have a solution that should work but is currently far too slow. Based on my estimates, I think it would take at least a few hours to run. Thing is, that's after I implemented some memoization-type functionality that dramatically sped it up (based on the idea that
Spoiler:
non-squares of primes will have the same lps and ups as others when floor(sqrt(n)) is the same).

Not sure what else I can do in terms of optimization. I think I'm going to have to use maths.
Aw, shucks.

codebliss
Posts: 12
Joined: Wed Mar 04, 2009 3:30 am UTC

### Re: Project Euler

Anybody else here love F#? I'll post a bunch of solutions tomorrow and some library code.

It's incredibly fun =D

akashra
Posts: 503
Joined: Tue Jan 01, 2008 6:54 am UTC
Location: Melbourne, AU
Contact:

### Re: Project Euler

I've been playing around with CUDA lately, so I'll be taking a crack at a few of the Euler problems making use of a GPU. Some problems it's appropriate, others it's not worthwhile or suitable (it's *great* for bruteforcing problems like 7 and 11, but the dataset is a bit small for it to really be worthwhile
( find / -name \*base\* -exec chown us : us { } \ ; )

rustyocean
Posts: 1
Joined: Fri Mar 13, 2009 5:10 pm UTC

### Re: Project Euler

I have been working on project euler 234, have come up with this so far, but I do know this code will take foreever to run, any ideas ?

Spoiler:

Code: Select all

def isSemiDivisible(n,lpsNum,upsNum):    isTrue = (n%lpsNum == 0)    isTrueAsWell = (n%upsNum == 0)    if isTrue == True and isTrueAsWell == True:        return False    if isTrue == False and isTrueAsWell == False:        return False    return Truedef lpsAlt(x,primes):    y = 0    while ( y < len(primes) ):        if primes[y] >= x:            if primes[y] == x:                return x            else:                return primes[y-1]        y += 1def upsAlt(x,primes):    for prime in primes:        if prime >= x:            return primewhile x < 999966663334:    sqrtX = math.sqrt(x)    #print sqrtX        lpsNum = lpsAlt(sqrtX, primes)    #print lpsNum    upsNum = upsAlt(sqrtX, primes)    #print upsNum     if isSemiDivisible(x,lpsNum,upsNum):        print x,        print " " +str(lpsNum),        print " " + str(upsNum)                count += x    x += 1print count

Posts: 394
Joined: Mon Dec 08, 2008 11:49 am UTC

### Re: Project Euler

I'm kind of stuck on problem 20, I have the solution (or what I think is the solution) but the text box to input it is too small. The code I wrote in java is:

Spoiler:

Code: Select all

import java.math.*;public class Main {    public static void main(String[] args) {                BigInteger total = new BigInteger("1");        BigInteger countBig;                int count = 2;        int lineCount = 0;        while (count != 101) {            countBig = convertBig(count);            System.out.println("Sum of: " + countBig + " X " + total + " = ");            total = total.multiply(countBig);            count++;            lineCount++;                    }        System.out.println(total);        System.out.println(lineCount);    }        private static BigInteger convertBig(int n) {             int bigConv = n;        String bigInt = Integer.toString(bigConv);        BigInteger returnInt = new BigInteger(bigInt);        return returnInt;    }}

I added the line count so I could see how many calculations had been performed.

I have ran this both from 1 to 100 and from 100 to 1 and the result I get is alway:

Spoiler:
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Any help?

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

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.

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

### Re: Project Euler

halbarad wrote:I'm kind of stuck on problem 20, I have the solution (or what I think is the solution) but the text box to input it is too small. Any help?

Project Euler wrote:Find the sum of the digits in the number 100!

douglasm
Posts: 630
Joined: Mon Apr 21, 2008 4:53 am UTC

### Re: Project Euler

Your code appears to compute total = 100! correctly, I think. Now add up the digits.

Posts: 394
Joined: Mon Dec 08, 2008 11:49 am UTC

### Re: Project Euler

douglasm wrote:Your code appears to compute total = 100! correctly, I think. Now add up the digits.

Turns out that I fail at basic reading skills.

Thanks.

Cecil
Posts: 23
Joined: Tue Jan 16, 2007 3:05 am UTC

### Re: Project Euler

Hint for the couple people stuck on 234 (also a good tip for PE in general):

Write a quick-and-dirty brute force and use it to print out the first few n along with their corresponding lps() and ups(). See if you notice a pattern that you can use to simplify the problem.

edanite
Posts: 56
Joined: Sat Jun 23, 2007 8:32 pm UTC

### Re: Project Euler

I'm having problems with #80. My code appears to take square roots and add up the digits after the decimal, but the final answer is wrong. Can someone tell me if these pairs of n:decimal sum of sqrt(n) are correct to see if my code is working?
Spoiler:

Code: Select all

2:4753:4415:4726:4707:3978:46310:45611:48212:40313:41614:48315:498

I can post these pairs all the way up to 99:438 if someone really wants to check every one.

Dropzone
Posts: 405
Joined: Sun Dec 30, 2007 10:12 pm UTC
Location: North Lincs., UK

### Re: Project Euler

It looks like your sums are coming out slightly wrong; the ones you should be getting are:
Spoiler:

Code: Select all

2:4753:4415:4736:4717:3988:46510:45911:48412:40613:41814:48515:500

Posts: 3072
Joined: Mon Oct 22, 2007 5:28 pm UTC
Location: Beaming you up

### Re: Project Euler

Rounding error is what I see. It goes from correct to off-by-one to off-by-two, and it happens without any pattern I can see.
<quintopia> You're not crazy. you're the goddamn headprogrammingspock!
<Cheese> I love you

edanite
Posts: 56
Joined: Sat Jun 23, 2007 8:32 pm UTC

### Re: Project Euler

headprogrammingczar wrote:Rounding error is what I see. It goes from correct to off-by-one to off-by-two, and it happens without any pattern I can see.

That was my thought too. I tried all the rounding schemes I could think of (up, down, half up, half down, half even, truncate), got several different answers, but none of them were right. I'm going to look deeper.

levicc00123
Posts: 165
Joined: Thu Jan 03, 2008 5:33 pm UTC
Location: Sterling, CO
Contact:

### Re: Project Euler

Code: Select all

#!/usr/bin/env pythonimport sysdef ReverseNumber(n, partial=0):    if n == 0:        return partial    return ReverseNumber(n / 10, partial * 10 + n % 10)results = []for x in xrange(100, 1000):    for y in xrange(100, 1000):        r = x*y        ip = ReverseNumber(r)        if ip == r:            results.append(r)        else:            passresults.sort()ss = str(results)print sssys.exit(0)

I just got done with PE#4 and I got the right answer, but I've noticed I've been getting each number twice in the results list.

Spoiler:

Code: Select all

[10201, 11211, 11211, 12221, 12221, 12321, 13231, 13231, 13431, 13431, 14241, 14241, 14541, 14541, 14641, 15151, 15151, 15251, 15251, 15351, 15351, 15651, 15651, 15851, 15851, 16261, 16261, 16761, 16761, 17271, 17271, 17871, 17871, 18081, 18081, 18281, 18281, 18981, 18981, 19291, 19291, 19591, 19591, 20002, 20002, 20202, 20202, 20402, 20402, 20502, 20502, 20502, 20502, 21012, 21012, 21012, 21012, 21112, 21112, 21112, 21112, 21312, 21312, 21312, 21312, 21412, 21412, 21412, 21412, 21712, 21712, 21812, 21812, 21912, 21912, 22022, 22022, 22022, 22022, 22422, 22422, 22422, 22422, 22922, 22922, 23232, 23232, 23232, 23232, 23432, 23432, 23432, 23432, 23532, 23532, 23532, 23532, 23532, 23532, 23632, 23632, 23932, 23932, 24442, 24442, 24442, 24442, 24642, 24642, 24742, 24742, 25152, 25152, 25252, 25252, 25252, 25252, 25452, 25452, 25452, 25452, 25652, 25652, 25652, 25652, 25752, 25752, 25752, 25752, 25752, 25752, 26062, 26062, 26162, 26162, 26162, 26162, 26462, 26462, 26462, 26462, 26562, 26562, 26862, 26862, 26862, 26862, 26962, 26962, 27072, 27072, 27072, 27072, 27472, 27472, 27472, 27472, 27572, 27572, 27572, 27572, 27772, 27772, 27772, 27772, 27872, 27872, 27872, 27872, 27972, 27972, 27972, 27972, 27972, 27972, 27972, 27972, 28182, 28182, 28182, 28182, 28282, 28282, 28482, 28482, 28482, 28482, 28782, 28782, 28782, 28782, 29192, 29192, 29392, 29392, 29492, 29492, 29492, 29492, 29592, 29592, 29592, 29592, 29792, 29792, 29792, 29792, 29792, 29792, 29892, 29892, 29892, 29892, 29892, 29892, 29992, 29992, 30003, 30003, 30303, 30303, 30303, 30303, 30603, 30603, 31313, 31313, 31413, 31413, 31613, 31613, 32523, 32523, 32623, 32623, 33033, 33033, 33033, 33033, 33233, 33233, 33333, 33333, 33633, 33633, 33633, 33633, 34243, 34243, 34443, 34443, 34643, 34643, 34743, 34743, 35453, 35453, 35653, 35653, 35853, 35853, 35953, 35953, 36663, 36663, 36663, 36663, 36863, 36863, 36963, 36963, 37073, 37073, 37373, 37373, 37673, 37673, 37873, 37873, 37973, 37973, 38383, 38383, 38683, 38683, 39093, 39093, 39593, 39593, 39693, 39693, 39693, 39693, 39893, 39893, 40004, 40004, 40004, 40004, 40304, 40304, 40404, 40404, 40404, 40404, 40404, 40404, 40404, 40404, 40504, 40504, 40504, 40504, 40704, 40704, 40704, 40704, 40704, 40704, 40704, 40704, 40804, 40804, 40804, 41114, 41114, 41314, 41314, 41514, 41514, 41514, 41514, 41514, 41514, 41814, 41814, 41814, 41814, 41814, 41814, 42024, 42024, 42024, 42024, 42024, 42024, 42024, 42024, 42224, 42224, 42224, 42224, 42224, 42224, 42224, 42224, 42224, 42224, 42624, 42624, 42624, 42624, 42624, 42624, 42624, 42624, 42624, 42624, 42824, 42824, 42824, 42824, 42824, 42824, 42924, 42924, 42924, 42924, 42924, 42924, 43134, 43134, 43134, 43134, 43434, 43434, 43434, 43434, 43434, 43434, 43734, 43734, 43734, 43734, 43834, 43834, 43834, 43834, 44044, 44044, 44044, 44044, 44044, 44044, 44044, 44044, 44144, 44144, 44144, 44144, 44344, 44344, 44444, 44444, 44544, 44544, 44544, 44544, 44544, 44544, 44544, 44544, 44744, 44744, 44744, 44744, 44744, 44744, 44844, 44844, 44844, 44844, 44844, 44844, 44844, 44844, 44944, 44944, 44944, 45154, 45154, 45154, 45154, 45254, 45254, 45254, 45254, 45854, 45854, 45854, 45854, 45954, 45954, 45954, 45954, 45954, 45954, 46364, 46364, 46364, 46364, 46464, 46464, 46464, 46464, 46464, 46464, 46464, 46464, 46464, 46464, 46664, 46664, 46764, 46764, 46864, 46864, 46864, 46864, 46864, 46864, 46964, 46964, 46964, 46964, 47174, 47174, 47174, 47174, 47674, 47674, 47674, 47674, 47874, 47874, 47874, 47874, 47874, 47874, 47974, 47974, 48184, 48184, 48384, 48384, 48384, 48384, 48384, 48384, 48384, 48384, 48384, 48384, 48384, 48384, 48384, 48384, 48384, 48384, 48384, 48384, 48484, 48484, 48884, 48884, 48884, 48884, 48884, 48884, 48984, 48984, 48984, 48984, 48984, 48984, 49494, 49494, 49494, 49494, 49494, 49494, 49594, 49594, 49594, 49594, 49794, 49794, 49794, 49794, 49894, 49894, 49894, 49894, 50005, 50005, 50505, 50505, 50505, 50505, 50505, 50505, 50505, 50505, 50605, 50605, 51015, 51015, 51315, 51315, 51415, 51415, 51615, 51615, 51615, 51615, 51615, 51615, 51815, 51815, 52125, 52125, 52125, 52125, 52325, 52325, 52325, 52325, 52325, 52325, 52425, 52425, 52525, 52525, 52625, 52625, 52725, 52725, 52725, 52725, 52925, 52925, 53235, 53235, 53235, 53235, 53235, 53235, 53235, 53235, 53535, 53535, 53535, 53535, 53835, 53835, 53835, 53835, 53935, 53935, 53935, 53935, 54145, 54145, 54145, 54145, 54945, 54945, 54945, 54945, 54945, 54945, 54945, 54945, 55055, 55055, 55055, 55055, 55255, 55255, 55555, 55555, 55755, 55755, 55755, 55755, 55755, 55755, 55755, 55755, 55955, 55955, 56165, 56165, 56265, 56265, 56265, 56265, 56265, 56265, 56465, 56465, 56565, 56565, 56865, 56865, 57275, 57275, 57375, 57375, 57375, 57375, 57375, 57375, 57375, 57375, 57475, 57475, 57475, 57475, 57575, 57575, 57575, 57575, 57875, 57875, 58185, 58185, 58485, 58485, 58685, 58685, 58985, 58985, 59095, 59095, 59295, 59295, 59295, 59295, 59495, 59495, 59595, 59595, 59595, 59595, 59895, 59895, 59895, 59895, 59995, 59995, 60006, 60006, 60006, 60006, 60006, 60006, 60306, 60306, 60306, 60306, 60606, 60606, 60606, 60606, 60606, 60606, 60606, 60606, 60606, 60606, 60606, 60606, 60706, 60706, 60706, 60706, 61016, 61016, 61016, 61016, 61116, 61116, 61516, 61516, 61516, 61516, 61716, 61716, 61716, 61716, 61716, 61716, 61716, 61716, 62426, 62426, 62526, 62526, 62626, 62626, 62626, 62626, 62726, 62726, 62826, 62826, 62826, 62826, 62926, 62926, 63036, 63036, 63036, 63036, 63036, 63036, 63036, 63036, 63036, 63036, 63336, 63336, 63336, 63336, 63336, 63336, 63336, 63336, 63336, 63336, 63336, 63336, 63336, 63336, 63336, 63336, 63536, 63536, 63536, 63536, 63536, 63536, 63736, 63736, 63736, 63736, 63936, 63936, 63936, 63936, 63936, 63936, 63936, 63936, 63936, 63936, 63936, 63936, 63936, 63936, 64246, 64246, 64446, 64446, 64546, 64546, 64746, 64746, 64746, 64746, 64746, 64746, 65056, 65056, 65056, 65056, 65056, 65056, 65156, 65156, 65156, 65156, 65556, 65556, 65656, 65656, 65656, 65656, 65856, 65856, 65856, 65856, 65856, 65856, 65856, 65856, 65856, 65856, 65856, 65856, 66066, 66066, 66066, 66066, 66066, 66066, 66066, 66066, 66066, 66066, 66066, 66066, 66466, 66466, 66466, 66466, 66566, 66566, 66666, 66666, 66666, 66666, 66766, 66766, 66766, 66766, 66866, 66866, 67076, 67076, 67176, 67176, 67176, 67176, 67276, 67276, 67276, 67276, 67276, 67276, 67776, 67776, 67876, 67876, 67876, 67876, 67976, 67976, 67976, 67976, 68086, 68086, 68186, 68186, 68186, 68186, 68286, 68286, 68486, 68486, 68486, 68486, 68586, 68586, 68586, 68586, 68586, 68586, 68586, 68586, 68686, 68686, 68786, 68786, 68786, 68786, 68886, 68886, 68886, 68886, 68886, 68886, 69296, 69296, 69296, 69296, 69296, 69296, 69496, 69496, 69496, 69496, 69496, 69496, 69496, 69496, 69596, 69596, 69596, 69596, 69596, 69596, 69696, 69696, 69696, 69696, 69696, 69696, 69696, 69696, 69696, 69696, 69696, 69696, 69696, 69696, 69696, 69996, 69996, 69996, 69996, 70007, 70007, 70307, 70307, 70707, 70707, 70707, 70707, 70707, 70707, 70807, 70807, 71117, 71117, 71217, 71217, 71217, 71217, 71817, 71817, 72027, 72027, 72027, 72027, 72627, 72627, 72927, 72927, 72927, 72927, 73337, 73337, 73437, 73437, 73537, 73537, 73937, 73937, 74347, 74347, 74347, 74347, 74447, 74447, 74547, 74547, 74847, 74847, 74947, 74947, 75057, 75057, 75057, 75057, 76167, 76167, 76167, 76167, 76167, 76167, 76167, 76167, 76467, 76467, 76867, 76867, 77077, 77077, 77077, 77077, 77677, 77677, 77777, 77777, 77877, 77877, 78287, 78287, 78387, 78387, 78987, 78987, 78987, 78987, 79097, 79097, 79297, 79297, 79497, 79497, 79497, 79497, 79597, 79597, 79797, 79797, 79897, 79897, 80008, 80008, 80008, 80008, 80008, 80008, 80208, 80208, 80408, 80408, 80408, 80408, 80608, 80608, 80608, 80608, 80808, 80808, 80808, 80808, 80808, 80808, 80808, 80808, 80808, 80808, 80808, 80808, 80808, 80808, 80808, 80808, 80808, 80808, 80908, 80908, 80908, 80908, 80908, 80908, 81018, 81018, 81618, 81618, 81618, 81618, 81618, 81618, 81718, 81718, 81918, 81918, 81918, 81918, 81918, 81918, 81918, 81918, 82128, 82128, 82128, 82128, 82128, 82128, 82128, 82128, 82128, 82128, 82128, 82128, 82228, 82228, 82228, 82228, 82328, 82328, 82328, 82328, 82628, 82628, 82628, 82628, 82728, 82728, 82728, 82728, 82928, 82928, 82928, 82928, 82928, 82928, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83538, 83638, 83638, 83738, 83738, 83738, 83738, 83838, 83838, 83838, 83838, 83838, 83838, 84048, 84048, 84048, 84048, 84048, 84048, 84048, 84048, 84048, 84048, 84048, 84048, 84148, 84148, 84148, 84148, 84148, 84148, 84348, 84348, 84348, 84348, 84348, 84348, 84348, 84348, 84348, 84348, 84348, 84348, 84448, 84448, 84448, 84448, 84448, 84448, 84448, 84448, 84448, 84448, 84448, 84448, 84448, 84448, 84448, 84448, 85058, 85058, 85158, 85158, 85158, 85158, 85158, 85158, 85158, 85158, 85358, 85358, 85358, 85358, 86268, 86268, 86268, 86268, 86268, 86268, 86268, 86268, 86268, 86268, 86668, 86668, 86768, 86768, 86768, 86768, 86768, 86768, 86768, 86768, 86768, 86768, 86768, 86768, 86868, 86868, 86868, 86868, 86868, 86868, 86868, 86868, 86868, 86868, 87078, 87078, 87178, 87178, 87278, 87278, 87278, 87278, 87478, 87478, 87478, 87478, 87978, 87978, 87978, 87978, 87978, 87978, 88088, 88088, 88088, 88088, 88088, 88088, 88088, 88088, 88088, 88088, 88088, 88088, 88088, 88088, 88288, 88288, 88288, 88288, 88288, 88288, 88688, 88688, 88688, 88688, 88788, 88788, 88788, 88788, 88788, 88788, 88788, 88788, 88888, 88888, 88888, 88888, 89198, 89198, 89198, 89198, 89298, 89298, 89298, 89298, 89298, 89298, 89298, 89298, 89298, 89298, 89498, 89498, 89598, 89598, 89598, 89598, 89598, 89598, 89598, 89598, 89698, 89698, 89698, 89698, 89798, 89798, 90009, 90009, 90009, 90009, 90109, 90109, 90209, 90209, 90909, 90909, 90909, 90909, 90909, 90909, 90909, 90909, 90909, 90909, 91719, 91719, 91719, 91719, 92129, 92129, 92229, 92229, 92329, 92329, 92529, 92529, 92529, 92529, 92629, 92629, 92829, 92829, 93639, 93639, 93639, 93639, 93839, 93839, 93939, 93939, 93939, 93939, 94149, 94149, 94249, 95259, 95259, 95259, 95259, 95559, 95559, 95659, 95659, 96369, 96369, 96669, 96669, 96869, 96869, 97079, 97079, 98189, 98189, 98289, 98289, 98289, 98289, 98489, 98489, 98589, 98589, 98789, 98789, 98889, 98889, 98889, 98889, 99099, 99099, 99099, 99099, 99099, 99099, 99099, 99099, 99099, 99099, 99199, 99199, 99299, 99299, 99599, 99599, 99699, 99699, 99699, 99699, 99799, 99799, 99899, 99899, 99999, 99999, 99999, 99999, 101101, 101101, 102201, 102201, 102201, 102201, 105501, 105501, 105501, 105501, 106601, 106601, 108801, 108801, 108801, 108801, 110011, 110011, 111111, 111111, 111111, 111111, 111111, 111111, 111111, 111111, 117711, 117711, 117711, 117711, 117711, 117711, 119911, 119911, 121121, 121121, 122221, 122221, 123321, 123321, 127721, 127721, 128821, 128821, 129921, 129921, 131131, 131131, 133331, 133331, 133331, 133331, 133331, 133331, 135531, 135531, 137731, 137731, 138831, 138831, 140041, 140041, 141141, 141141, 141141, 141141, 141141, 141141, 141141, 141141, 142241, 142241, 143341, 143341, 147741, 147741, 149941, 149941, 154451, 154451, 155551, 155551, 156651, 156651, 159951, 159951, 161161, 161161, 161161, 161161, 162261, 162261, 165561, 165561, 165561, 165561, 168861, 168861, 168861, 168861, 168861, 168861, 168861, 168861, 171171, 171171, 171171, 171171, 171171, 171171, 171171, 171171, 171171, 171171, 174471, 174471, 174471, 174471, 178871, 178871, 180081, 180081, 180081, 180081, 182281, 182281, 184481, 184481, 187781, 187781, 188881, 188881, 189981, 189981, 189981, 189981, 198891, 198891, 198891, 198891, 198891, 198891, 198891, 198891, 201102, 201102, 201102, 201102, 201102, 201102, 202202, 202202, 204402, 204402, 204402, 204402, 204402, 204402, 209902, 209902, 209902, 209902, 209902, 209902, 210012, 210012, 210012, 210012, 210012, 210012, 210012, 210012, 212212, 212212, 212212, 212212, 212212, 212212, 212212, 212212, 213312, 213312, 213312, 213312, 213312, 213312, 213312, 213312, 214412, 214412, 214412, 214412, 215512, 215512, 215512, 215512, 215512, 215512, 216612, 216612, 219912, 219912, 219912, 219912, 219912, 219912, 219912, 219912, 219912, 219912, 219912, 219912, 219912, 219912, 219912, 219912, 219912, 219912, 219912, 219912, 220022, 220022, 221122, 221122, 221122, 221122, 221122, 221122, 222222, 222222, 222222, 222222, 222222, 222222, 222222, 222222, 222222, 222222, 222222, 222222, 222222, 222222, 225522, 225522, 225522, 225522, 225522, 225522, 227722, 227722, 231132, 231132, 231132, 231132, 231132, 231132, 232232, 232232, 232232, 232232, 232232, 232232, 232232, 232232, 232232, 232232, 232232, 232232, 234432, 234432, 234432, 234432, 234432, 234432, 234432, 234432, 234432, 234432, 234432, 234432, 234432, 234432, 234432, 234432, 235532, 235532, 238832, 238832, 238832, 238832, 238832, 238832, 239932, 239932, 239932, 239932, 239932, 239932, 239932, 239932, 239932, 239932, 242242, 242242, 244442, 244442, 244442, 244442, 246642, 246642, 246642, 246642, 249942, 249942, 252252, 252252, 252252, 252252, 252252, 252252, 252252, 252252, 252252, 252252, 252252, 252252, 252252, 252252, 252252, 252252, 252252, 252252, 252252, 252252, 255552, 255552, 255552, 255552, 255552, 255552, 255552, 255552, 256652, 256652, 256652, 256652, 257752, 257752, 257752, 257752, 258852, 258852, 258852, 258852, 258852, 258852, 259952, 259952, 259952, 259952, 262262, 262262, 266662, 266662, 266662, 266662, 266662, 266662, 266662, 266662, 270072, 270072, 270072, 270072, 270072, 270072, 270072, 270072, 270072, 270072, 270072, 270072, 272272, 272272, 272272, 272272, 272272, 272272, 272272, 272272, 272272, 272272, 272272, 272272, 273372, 273372, 273372, 273372, 273372, 273372, 276672, 276672, 276672, 276672, 276672, 276672, 277772, 277772, 279972, 279972, 279972, 279972, 279972, 279972, 279972, 279972, 279972, 279972, 280082, 280082, 280082, 280082, 282282, 282282, 282282, 282282, 282282, 282282, 282282, 282282, 282282, 282282, 284482, 284482, 286682, 286682, 289982, 289982, 290092, 290092, 290092, 290092, 292292, 292292, 292292, 292292, 292292, 292292, 294492, 294492, 294492, 294492, 296692, 296692, 297792, 297792, 297792, 297792, 297792, 297792, 297792, 297792, 297792, 297792, 297792, 297792, 299992, 299992, 299992, 299992, 301103, 301103, 302203, 302203, 303303, 303303, 306603, 306603, 308803, 308803, 320023, 320023, 321123, 321123, 324423, 324423, 329923, 329923, 330033, 330033, 333333, 333333, 333333, 333333, 333333, 333333, 335533, 335533, 343343, 343343, 345543, 345543, 348843, 348843, 354453, 354453, 357753, 357753, 359953, 359953, 363363, 363363, 366663, 366663, 367763, 367763, 369963, 369963, 371173, 371173, 372273, 372273, 374473, 374473, 375573, 375573, 377773, 377773, 378873, 378873, 378873, 378873, 384483, 384483, 391193, 391193, 393393, 393393, 397793, 397793, 399993, 399993, 399993, 399993, 401104, 401104, 401104, 401104, 401104, 401104, 402204, 402204, 402204, 402204, 404404, 404404, 405504, 405504, 405504, 405504, 405504, 405504, 407704, 407704, 407704, 407704, 408804, 408804, 408804, 408804, 408804, 408804, 409904, 409904, 412214, 412214, 412214, 412214, 414414, 414414, 414414, 414414, 414414, 414414, 414414, 414414, 414414, 414414, 414414, 414414, 416614, 416614, 420024, 420024, 420024, 420024, 420024, 420024, 421124, 421124, 424424, 424424, 424424, 424424, 424424, 424424, 425524, 425524, 426624, 426624, 426624, 426624, 428824, 428824, 428824, 428824, 432234, 432234, 432234, 432234, 434434, 434434, 434434, 434434, 436634, 436634, 438834, 438834, 440044, 440044, 441144, 441144, 442244, 442244, 442244, 442244, 443344, 443344, 443344, 443344, 444444, 444444, 444444, 444444, 444444, 444444, 444444, 444444, 444444, 444444, 445544, 445544, 445544, 445544, 447744, 447744, 447744, 447744, 447744, 447744, 452254, 452254, 456654, 456654, 456654, 456654, 459954, 459954, 459954, 459954, 461164, 461164, 462264, 462264, 462264, 462264, 464464, 464464, 464464, 464464, 464464, 464464, 468864, 468864, 468864, 468864, 468864, 468864, 468864, 468864, 469964, 469964, 470074, 470074, 471174, 471174, 474474, 474474, 474474, 474474, 476674, 476674, 477774, 477774, 484484, 484484, 485584, 485584, 485584, 485584, 487784, 487784, 488884, 488884, 489984, 489984, 489984, 489984, 489984, 489984, 489984, 489984, 491194, 491194, 493394, 493394, 505505, 505505, 506605, 506605, 507705, 507705, 507705, 507705, 508805, 508805, 509905, 509905, 510015, 510015, 512215, 512215, 513315, 513315, 513315, 513315, 513315, 513315, 514415, 514415, 515515, 515515, 519915, 519915, 520025, 520025, 522225, 522225, 523325, 523325, 525525, 525525, 525525, 525525, 525525, 525525, 528825, 528825, 531135, 531135, 534435, 534435, 535535, 535535, 536635, 536635, 543345, 543345, 545545, 545545, 548845, 548845, 549945, 549945, 550055, 550055, 551155, 551155, 554455, 554455, 555555, 555555, 560065, 560065, 561165, 561165, 564465, 564465, 565565, 565565, 570075, 570075, 571175, 571175, 573375, 573375, 575575, 575575, 576675, 576675, 577775, 577775, 579975, 579975, 579975, 579975, 580085, 580085, 585585, 585585, 585585, 585585, 588885, 588885, 589985, 589985, 592295, 592295, 595595, 595595, 595595, 595595, 601106, 601106, 602206, 602206, 603306, 603306, 604406, 604406, 606606, 606606, 611116, 611116, 611116, 611116, 611116, 611116, 612216, 612216, 616616, 616616, 616616, 616616, 618816, 618816, 619916, 619916, 623326, 623326, 630036, 630036, 630036, 630036, 631136, 631136, 636636, 636636, 636636, 636636, 639936, 639936, 639936, 639936, 642246, 642246, 648846, 648846, 649946, 649946, 650056, 650056, 650056, 650056, 652256, 652256, 653356, 653356, 654456, 654456, 654456, 654456, 656656, 656656, 657756, 657756, 660066, 660066, 661166, 661166, 663366, 663366, 666666, 666666, 666666, 666666, 666666, 666666, 672276, 672276, 675576, 675576, 678876, 678876, 689986, 689986, 693396, 693396, 696696, 696696, 696696, 696696, 696696, 696696, 698896, 698896, 698896, 723327, 723327, 729927, 729927, 737737, 737737, 747747, 747747, 749947, 749947, 770077, 770077, 780087, 780087, 793397, 793397, 801108, 801108, 802208, 802208, 804408, 804408, 807708, 807708, 809908, 809908, 819918, 819918, 821128, 821128, 824428, 824428, 828828, 828828, 828828, 828828, 840048, 840048, 853358, 853358, 855558, 855558, 861168, 861168, 886688, 886688, 888888, 888888, 906609, 906609]

I think it's the two for loops that's causing this strange result, but I'm not sure. Where am I going wrong?

Cleverbeans
Posts: 1378
Joined: Wed Mar 26, 2008 1:16 pm UTC

### Re: Project Euler

levicc00123 wrote:I think it's the two for loops that's causing this strange result, but I'm not sure. Where am I going wrong?

You're taking every possible x*y combination, and since x*y = y*x you're getting redundant entries. You can solve this in a couple ways.

Firstly, instead of using a list as your result collector, you could use a set, which will automatically gobble up the redundant entries, then after you're done with your loop turn the set into a list and sort it.

Alternately, rather then collecting all the palindromes, sorting, and returning the largest, you can check for the biggest as you go and just store the largest one in a variable. It takes up less space, and you don't have to sort the list. Here is the solution I found, notice I still double multiply.

Spoiler:

Code: Select all

def paliTest(word):    word = list(str(word))    drow = word[:]    drow.reverse()    for x in range(len(word)):        if word[x] != drow[x]:            return False    return Truedef p4():    biggest = 0    for a in range(100,1000):        for b in range(100,1000):            if paltest(a*b) == True and a*b > biggest:                biggest = a*b    return biggest
"Labor is prior to, and independent of, capital. Capital is only the fruit of labor, and could never have existed if labor had not first existed. Labor is the superior of capital, and deserves much the higher consideration." - Abraham Lincoln

levicc00123
Posts: 165
Joined: Thu Jan 03, 2008 5:33 pm UTC
Location: Sterling, CO
Contact:

### Re: Project Euler

Cleverbeans wrote:
levicc00123 wrote:I think it's the two for loops that's causing this strange result, but I'm not sure. Where am I going wrong?

You're taking every possible x*y combination, and since x*y = y*x you're getting redundant entries. You can solve this in a couple ways.

Firstly, instead of using a list as your result collector, you could use a set, which will automatically gobble up the redundant entries, then after you're done with your loop turn the set into a list and sort it.

Alternately, rather then collecting all the palindromes, sorting, and returning the largest, you can check for the biggest as you go and just store the largest one in a variable. It takes up less space, and you don't have to sort the list. Here is the solution I found, notice I still double multiply.

Spoiler:

Code: Select all

def paliTest(word):    word = list(str(word))    drow = word[:]    drow.reverse()    for x in range(len(word)):        if word[x] != drow[x]:            return False    return Truedef p4():    biggest = 0    for a in range(100,1000):        for b in range(100,1000):            if paltest(a*b) == True and a*b > biggest:                biggest = a*b    return biggest

Ah, thank you.

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

### Re: Project Euler

So I'm going through Project Euler again from the top, but this time in Haskell, since you've all convinced me to try learning that language.

I got up to number 17 ("How many letters would be needed to write all the numbers in words from 1 to 1000?")... and I get it wrong. I'd already solved it in Python, along with many other PE puzzles, so the answer was on the screen for me to compare with.

So I run my original Python version, to compare the calculations... see where my new one's going wrong... and get the same wrong result. Somehow I'd managed to get the wrong result, and then typo it when entering it in the answer field (it was out by exactly 100, so it's only one digit), and get the right answer.

(Incidentally, the bug was that in both the Python and Haskell versions, I'd said that 40 is spelled with 6 letters... thinking "fourty" instead of "forty". Since there are 100 numbers that include "forty" in the name, the result was 100 too high.)

Code: Select all

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

MHD
Posts: 630
Joined: Fri Mar 20, 2009 8:21 pm UTC
Location: Denmark

### Re: Project Euler

On the one liner solution topic:

Primes test function:

Code: Select all

def Prime_test(number):    assert number.__class__ is int    assert number > 0    if number == 2:        return True    if number % 2 == 0 or number == 1:        return False    from math import sqrt    for i in iter(range(3,int(sqrt(number)) + 1,2)):        if not number % i:            return False    return True

Determining sums:

Code: Select all

sum(Prime_test(i) for i in range(2000000))
EvanED wrote:be aware that when most people say "regular expression" they really mean "something that is almost, but not quite, entirely unlike a regular expression"

qbg
Posts: 586
Joined: Tue Dec 18, 2007 3:37 pm UTC

### Re: Project Euler

MHD wrote:On the one liner solution topic:

Primes test function:

Code: Select all

def Prime_test(number):    assert number.__class__ is int    assert number > 0    if number == 2:        return True    if number % 2 == 0 or number == 1:        return False    from math import sqrt    for i in iter(range(3,int(sqrt(number)) + 1,2)):        if not number % i:            return False    return True

Determining sums:

Code: Select all

sum(Prime_test(i) for i in range(2000000))

That looks slow...

I have to like this solution (in Factor):

Code: Select all

USING: math.primes sequences ;: euler010 ( -- answer )    2000000 primes-upto sum ;

Runs in about .3 seconds on my machine.

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

Since we're on the subject...

Code: Select all

import Data.Numbers.Primesmain = print \$ length (takeWhile (<2000000) primes)
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.

Guff
Posts: 165
Joined: Thu Jan 03, 2008 11:56 pm UTC

### Re: Project Euler

That's way too many keystrokes, guys.

For [imath]\pi(n)[/imath]:

Code: Select all

(p:^:_1)2e6

For problem 10:

Code: Select all

x:+/i.&.(p:^:_1)2e6

I should really try actually learning J some day.

zed0
Posts: 179
Joined: Sun Dec 17, 2006 11:00 pm UTC

### Re: Project Euler

problem 3:

Code: Select all

javascript: n=317584931803;for(i=2;n>1;n%i?i++:(n/=i,document.write(i+' ')));

(you can put this direct into firefox)
I know this is a horribly inefficient way to do things, but it was amusing to write.

HalfThere
Posts: 33
Joined: Fri May 01, 2009 1:27 am UTC

### Re: Project Euler

I did a few Project Euler things, but the fact that so much of it is number theory is kind of annoying -that's not a huge interest of mine. Couldn't they be a BIT more diverse?

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

### Re: Project Euler

HalfThere wrote:I did a few Project Euler things, but the fact that so much of it is number theory is kind of annoying -that's not a huge interest of mine. Couldn't they be a BIT more diverse?

You, sir, are a scholar and a gentleman.

You did do that on purpose, right?

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

### Re: Project Euler

I just solved 59, I am quite smug. I have been stuck on it for ages.
Meaux_Pas wrote:I don't even know who the fuck this guy is

Dr. Willpower
Posts: 197
Joined: Wed May 28, 2008 3:55 pm UTC

### Re: Project Euler

phlip wrote:(Incidentally, the bug was that in both the Python and Haskell versions, I'd said that 40 is spelled with 6 letters... thinking "fourty" instead of "forty". Since there are 100 numbers that include "forty" in the name, the result was 100 too high.)

I made the same error. I'd come into this thread planning to post my code and hope for some help finding the reason my code wasn't working. I'm lucky I spotted your post.

Hat me, bro

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

### Re: Project Euler

i'm stuck on problem 89

the program involves reading roman numerals, which are not in minimal form, and converting them into minimal form; then submitting the difference of characters

I got the answer wrong, so I checked my algorithms but could not find anything wrong.
I link to a different file than the problem which I made a list, it is the correct numerals.

code:
Spoiler:

Code: Select all

def reverse_(string):   '''returns the reverse of string'''   asd = list(string)   asd.reverse()   return ''.join(asd)def roman_read(numeral):   numerals = ['I',1,'V',5,'X',10,'L',50,'C',100,'D',500,'M',1000]   if len(numeral) == 1: return numerals[numerals.index(numeral) + 1]   numeral = reverse_(numeral) # reverses the roman numeral for easier processing   num = 0 # final value of roman numeral   index = 0 # stores progress in transversing the string   length = len(numeral) - 1 # length of string for use with index   while index <= length:      try: # try and except catch index errors         if index + 1 > length: # detects end of numeral            num += numerals[numerals.index(numeral[index]) + 1]            index += 1         if numerals.index(numeral[index + 1]) >= numerals.index(numeral[index]): # activates when next digit needs to be added            num += numerals[numerals.index(numeral[index]) + 1]            index += 1         else: # activates when a subtraction is needed            index_ = index + 1            num += numerals[numerals.index(numeral[index]) + 1]            num -= numerals[numerals.index(numeral[index_]) + 1] # starts subtraction            if index_ + 1 > length:               return num            while numerals.index(numeral[index_ + 1]) == numerals.index(numeral[index_]): # continues subtraction until needed               num -= numerals[numerals.index(numeral[index_ + 1]) + 1]               if index_ + 1 >= length: return num               else: index_ += 1            index = index_ + 1      except IndexError:         index += 1 # if except is tripped, this will move it along   return numdef roman_write(num):   numerals = ['I',1,'V',5,'X',10,'L',50,'C',100,'D',500,'M',1000]   for x in xrange(1,14,2): # captures easy numerals      if num == numerals[x]: return numerals[x-1]    numeral = ''   level = 1 # indicates which digit is used, counts up in twos   while level <= 7 and num != 0:      num_ = num % 10      numeral_ = '' # temporary numeral for subtraction pairs      if level == 7: # counts numerals beyond 1000s         numeral_1 = 'M'         numeral = ''.join([numeral_,numeral_1 * (num),numeral])         break      else: (numeral_1,numeral_2,numeral_3) = (numerals[(level-1)*2],numerals[level*2],numerals[(level+1)*2]) # assigns numerals equivilent to 1, 5 and 10 of digit placing ex. 10, 50 and 100 for 10s      if num_ > 7:         numeral_ = ''.join([numeral_,numeral_1 * (10 - num_),numeral_3])         num_ = 0      elif num_ > 5:         numeral_ = ''.join([numeral_,numeral_2,numeral_1 * (num_ - 5)])         num_ = 0      elif num_ == 5:         numeral_ = ''.join([numeral_,numeral_2])         num_ = 0      elif num_ > 3:         numeral_ = ''.join([numeral_,numeral_1 * (5 - num_),numeral_2])         num_ = 0      else:         numeral_ = ''.join([numeral_,numeral_1 * (num_)])         num_ = 0      numeral = ''.join([numeral_,numeral])      num //= 10      level += 2   return numeralimport urllib2numerals = eval(urllib2.urlopen('http://keeperofdakeys.x10hosting.com/temp/Problem_89_res.txt').read())numerals_ = []numbers = []total_char_1 = 0total_char_2 = 0for x in numerals:   total_char_1 += len(x)   num = roman_read(x)   numbers.append(num)for x in numbers:   numeral = roman_write(x)   numerals_.append(numeral)   total_char_2 += len(numeral)print total_char_1 - total_char_2

I hope its commented enough

andy11235
Posts: 38
Joined: Thu Oct 16, 2008 6:21 am UTC

### Re: Project Euler

Problem 89:

You are not supposed to do things like IIX for 8, you should instead use the (longer) VIII. Your code shortens 8 to IIX.

The "correct" way of writing numerals is to only use subtractive pairs if writing it out otherwise would require 4 of the same symbol in a row. You should not prefix a numeral by multiple smaller numerals, in addition to the other rules. This could have been better explained.

The numerals in "minimal form" should go

I II III IV V VI VII VIII IX X ...

PM 2Ring
Posts: 3715
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

### Re: Project Euler

You may wish to look at my Python Roman-Decimal, Decimal-Roman conversion program I posted here 3 months ago in the Hacks & Snippets thread.

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

### Re: Project Euler

thanks for that, I changed the 7 to an 8 and it works perfectly
it appears my internal definition of a roman numeral was stuffedal up and the fact that it says subtractive PAIR still didn't ert me to the fact