The Project Euler thread

[Reincarnate]

In Python though yes

[Reincarnate]

Son of a...

Just solved problem 88, but it is tricky to get in decent runtime. Right now my best is only 14s. :(

EDIT: Oh FFS I am an idiot... much faster way to do this.

EDIT: 0.2 seconds -- can't believe I didn't do this in the first place.


EDIT:

Total time for problems 1 through 90: 28.940158 seconds

[Reincarnate]

Up to Problem 96, aaaghghghgh Sudoku. Nope. Bedtime

edit: (jk 97, 99, and 100 are quickfodder -- 96 and 98 can diaf)

edit: actually 98 isn't horrible either

edit: GAURUATUGH FINE I'LL DO SUDOKU. :( going to write the most fucking messiest code in the universe

edit: Yay, first 100 down

[leonid]

really tough

[Reincarnate]

nice one, leonid








EDIT:
Total time for problems 1 through 100: 32.591266 seconds

Problem 1 in 0.000006 s
Problem 2 in 0.000009 s
Problem 3 in 0.000562 s
Problem 4 in 0.295742 s
Problem 5 in 0.000037 s
Problem 6 in 0.000004 s
Problem 7 in 0.018113 s
Problem 8 in 0.010010 s
Problem 9 in 0.000072 s
Problem 10 in 0.427023 s
Problem 11 in 0.002001 s
Problem 12 in 0.353162 s
Problem 13 in 0.000264 s
Problem 14 in 2.009820 s
Problem 15 in 0.000026 s
Problem 16 in 0.000260 s
Problem 17 in 0.001162 s
Problem 18 in 0.000439 s
Problem 19 in 0.003114 s
Problem 20 in 0.000137 s
Problem 21 in 0.121356 s
Problem 22 in 0.014946 s
Problem 23 in 0.638417 s
Problem 24 in 0.124795 s
Problem 25 in 0.035268 s
Problem 26 in 0.013433 s
Problem 27 in 0.000009 s
Problem 28 in 0.000007 s
Problem 29 in 0.017878 s
Problem 30 in 1.653687 s
Problem 31 in 0.002773 s
Problem 32 in 0.481344 s
Problem 33 in 0.000229 s
Problem 34 in 0.227541 s
Problem 35 in 0.462930 s
Problem 36 in 0.519228 s
Problem 37 in 0.251382 s
Problem 38 in 0.001300 s
Problem 39 in 0.000364 s
Problem 40 in 0.000044 s
Problem 41 in 0.001595 s
Problem 42 in 0.004338 s
Problem 43 in 0.049111 s
Problem 44 in 0.271455 s
Problem 45 in 0.018607 s
Problem 46 in 0.012878 s
Problem 47 in 0.072932 s
Problem 48 in 0.003445 s
Problem 49 in 0.485125 s
Problem 50 in 0.197839 s
Problem 51 in 0.238479 s
Problem 52 in 0.641779 s
Problem 53 in 0.002342 s
Problem 54 in 0.067815 s
Problem 55 in 0.077687 s
Problem 56 in 0.414760 s
Problem 57 in 0.000912 s
Problem 58 in 0.293105 s
Problem 59 in 0.002044 s
Problem 60 in 5.083650 s
Problem 61 in 0.002605 s
Problem 62 in 0.045824 s
Problem 63 in 0.000028 s
Problem 64 in 0.242403 s
Problem 65 in 0.000090 s
Problem 66 in 0.032540 s
Problem 67 in 0.005123 s
Problem 68 in 0.040291 s
Problem 69 in 0.000160 s
Problem 70 in 0.790107 s
Problem 71 in 0.000006 s
Problem 72 in 0.062803 s
Problem 73 in 0.019348 s
Problem 74 in 1.181639 s
Problem 75 in 0.745507 s
Problem 76 in 0.070708 s
Problem 77 in 0.021643 s
Problem 78 in 6.514026 s
Problem 79 in 0.000227 s
Problem 80 in 0.007928 s
Problem 81 in 0.007150 s
Problem 82 in 0.010406 s
Problem 83 in 0.131738 s
Problem 84 in 0.001178 s
Problem 85 in 0.002586 s
Problem 86 in 1.702908 s
Problem 87 in 0.464952 s
Problem 88 in 0.270735 s
Problem 89 in 0.002017 s
Problem 90 in 0.075457 s
Problem 91 in 0.008651 s
Problem 92 in 0.207911 s
Problem 93 in 0.270968 s
Problem 94 in 0.000015 s
Problem 95 in 3.656271 s
Problem 96 in 0.216058 s
Problem 97 in 0.000015 s
Problem 98 in 0.147458 s
Problem 99 in 0.002978 s
Problem 100 in 0.000015 s

Total time for problems 1 through 100: 32.591266 seconds

[leonid]

OMG finally.

[leonid]

Wish people read my posts because I take extra time refining my code and explanations

As of now most of the posts I've made recently are still the very last post of each thread

[stargroup100]

I read them

I just don't have much to say lol

[leonid]

I'm talking about my posts in the euler problem threads btw, not this thread

[stargroup100]

OHHH

yeah it kinda sucks, cause nobody reads past the first three posts, let alone the first page

[rushyrulz]

Originally Posted by Problem 23

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Finished problem 23 and it was an efficiency nightmare (i shud lrn 2 code b4tr)

Why do they pick 28,123 when the same is true for all numbers greater than 20,161?

[stargroup100]

Originally Posted by rushyrulz

Finished problem 23 and it was an efficiency nightmare (i shud lrn 2 code b4tr)

Why do they pick 28,123 when the same is true for all numbers greater than 20,161?

I'm assuming this means that through conceptual analysis and proof, the lowest limit we can reduce down to is 28123. Even though the true limit is lower, this is the smallest upper bound we can actually prove in this way. If this is really true, I'm sure it's very well defined what they mean by "reduced any further by analysis". Clearly, brute force testing with a computer doesn't count.

Unless you're asking why the problem writer chose to use that number specifically, in which case I don't know and it's really the writer's free choice. Perhaps he just simply wanted an excuse to use larger numbers, despite the small increase. It does kinda make sense though; once you find the limit of your hand analysis, you have no choice but to use a computer, and only then can you reduce that limit. The problem probably wants to demonstrate an example of this.

I just tried this on my own and the 28123 limit is actually pretty easy to prove, and I really do have no idea how to get this down any lower.

[Reincarnate]

Originally Posted by leonid

Wish people read my posts because I take extra time refining my code and explanations

As of now most of the posts I've made recently are still the very last post of each thread

I read them all (I scroll through the problem listings from time to time and check out new posts).

I just don't have much to add because I don't find those problems as interesting as some of the harder ones.

A comment though, I'm surprised about your approach to 181. That problems seems like it would have been really easy for you to hammer out and execute in quick runtime.


edit: Stargroup: Yes that's right -- in practice it's lower but the limit is analytically provable. Here is the proof: http://mathschallenge.net/full/sum_o...undant_numbers

[stargroup100]

oh shit that's the method I came up with LOL

[rushyrulz]

fair enough

[leonid]

Literally took me 3 minutes to solve
Now I ran out of easy problems

[rushyrulz]

first one that I actually used pencil and paper for.

[leonid]

woot

[leonid]

Easy

A question... Isn't problem 266 a 2-partition problem (NP-complete)?
I don't see any way other than having to run an exponential (or pseudo-polynomial) runtime algorithm that takes ages to finish

[Reincarnate]

There is a way

Every single problem gets tested against the minute-rule before release.

Problem 266 is doable in a lot less time than that, even