I have had the impression that numerous posts in the past few months may have been related to trying to solve some of the problems posted on another site under the name of "Project Euler".

For all those who may be interested in testing their skills (math, logic and programming), the site's address is:

http://www.mathschallenge.net/

Have fun

Raymond
Posted on 2004-06-05 22:47:32 by Raymond
Thanks Raymond, I spend an hour creating x86 solutions. Three of them didn't even require any programming. I've solved eight of them so far...10...15...20...25...
Posted on 2004-06-06 14:06:36 by bitRAKE
I've just been working on the one where you have to find the smallest number that is divisible by the numbers 1-20.

I'm normally more comfortable in VB so I used this to get the answer first. The task took about 5 minutes to solve.

Then I re-wrote exactly the same algorithm in masm32. It takes just 7 seconds! It's amazing the speed improvements you can get by working everything out in the CPU's registers. Man I love asm :).
Posted on 2004-06-06 15:42:58 by DeX
We should be able to find this on paper, without use a computer...

Let's begin with working out the factorizations of every positive integer up to 20:
2: 2
3: 3
4: 2^2
5: 5
6: 2*3
7: 7
8: 2^3
9: 3^2
10: 2*5
11: 11
12: 2^2*3
13: 13
14: 2*7
15: 3*5
16: 2^4
17: 17
18: 2*3^2
19: 19
20: 2^2*5
The smallest number that is divisible with all of these must have a factorization that contains at least as many occurences of a factor as each of the above ones.
So we find the highest powers of every prime factor and multiply them.
2^4*3^2*5*7*11*13*17*19. And there we have our answer, 232792560. (Okay, so I cheated. I used the windows calculator to compute the above answer :P)

Well at least it didn't take 5 minutes :alright:
Posted on 2004-06-06 17:28:51 by Sephiroth3
Sephiroth3, there are many more puzzles to go... :)
Posted on 2004-06-06 18:29:01 by bitRAKE
Aye, thanks.. I have solved 14 questions for now...

Sephiroth3,
That's exactly the method I used to solve it. :alright:
Posted on 2004-06-06 18:55:37 by roticv
roticv, doing well on the problems. :) We seem to be solving different ones, but I'm keeping up right behind you scorewise.

Many of the problems have digit summations, or sum of factors; and lots of polynomial number work. I've done all but 5 of the 25 completely in x86 -- used Excel for one, found three on the web, and used VB here at work for one.

I brute forced one of the ones I found on the web, but it took three hours. Also, I brute forced one they recommended not to, but it only took 16 seconds. :)
Posted on 2004-06-07 17:31:45 by bitRAKE
I'd really like to see how you implemented some of these problems in assembly bitRake. I've only done about 5 (out of 22 - not far behind you and rotvic) in assembly and the others have been in VB.

Also I brute forced most of them. I'm never sure if brute force is the correct method to use or not. One of the one's I didn't brute force however was the one that you did bitRake (they said it would take 2 days not 16 seconds!). Actually finding a logical method to solve it was not too hard but implementing the tree structure from a file into code took some doing.

Other difficult ones I find are the prime number and factor ones, and also the ones that insist you work with huge values such as 2^1000 or 100! Luckily I wrote an arbitary precision maths module a while ago which has been pretty handy.

All but the simplest problems though I would find much too difficult in assembly. My maths module uses strings to store the values of really long numbers. Is this the method you used bitRake or BCD or something similar?

Also you are required to convert between numeric values and strings pretty often as you said. This isn't too hard in VB but it must be a whole lot harder in assembly I imagine. How do you do that?
Posted on 2004-06-07 18:27:34 by DeX
DeX, bitRAKE uses binary - no BCD. :) You would be surprised to see how few lines of code the solutions are (I'm talking a couple dozen lines of code max!). Just email and I'll send you the code for the ones you have solved already. :D

http://www.asmcommunity.net/board/cryptmail.php?tauntspiders=in.your.face@nomail.for.you&id=5d9b7214c9505b863305963f80804e68

String conversion is either divide by ten in a loop for integers; or multiple by ten for fractions. We don't have to do the whole conversion in most cases as they just want the sum of digits.

Knowing how to generate polygonal numbers without multiplication is important though for brute force. And a prime sieve is handy for the prime puzzles (mine only requires two registers, and two instructions to test for prime ;)).

p.s. I used Excel for another one - now I'm in the top 50...whoohoo!
Posted on 2004-06-07 18:41:08 by bitRAKE
two instructions to test for prime

Ok, now you've done it!!!

what is that solution in 2 instructions, Im really puzzled ...and I...well... :stupid:

Cheers :)
Posted on 2004-06-07 22:01:32 by Milos
Of course, it requires a table:

bt , eax
jc Prime

http://www.asmcommunity.net/board/index.php?topic=13322&highlight=prime+sieve

There is no magic - just proper planning. When you are testing for primeness in a loop it is very effective. The only limit is how much memory you have to set aside for the buffer. Most competitions don't require monster size primes anyway.
Posted on 2004-06-07 22:21:23 by bitRAKE
bitRAKE wrote
Also, I brute forced one they recommended not to, but it only took 16 seconds.
You must still be using a pre-Pentium computer to solve that #18 problem.:grin: :grin: :grin: I'm currently using a P4-1500 and the answer gets displayed so fast that I don't even have time to blink after I start the "brute force" program.

I'm also using brute force for most of the problems and strictly in assembler (except for one where I used "pen and pencil"). I've also been "cheating" a little bit for some of them using a debugger before completing the program (such as for the encrypted text of #59).

DeX
Also you are required to convert between numeric values and strings pretty often
The only time I would use such a procedure is to convert the final answer for display. For large numbers, I prefer to use unpacked BCD which is VERY easy to implement in assembler.

And then there are some problem (such as #28) which can be "brute force" coded with less than a dozen assembler instructions for the computation if you analyze the problem properly. The answer to that #28 could probably be computed with 2 lines of code in VB.

Raymond
Posted on 2004-06-07 22:59:11 by Raymond
Raymond, you caught me - I didn't time it. I ran it from the debugger, but it is a lot slower than it could be due to the way I abstracted the triangle array away from path selection without changing the data. Maybe it will be useful for something else? My math skills are lacking and I'm feeling my coding skills not being enough to cover for it. Needless to say I am learning quite a bit doing these problems. :)
Posted on 2004-06-08 00:09:37 by bitRAKE
I see they added a harder version of problem #18. :)

I'm doing really well at reducing the problems down to a managable level, but there are about ten I've coded solutions for and not found a correct solution. I'm sure there are errors in my code, or I'm missing some element of the problem. And a couple naive brute force attempts are too slow to reach a solution in my lifetime.

40 problems done...
Posted on 2004-06-10 01:37:24 by bitRAKE
Ah you are good, bitRAKE. Alot of solutions requires brute forcing. Like for instance I am brute forcing question 66.
Posted on 2004-06-10 05:34:53 by roticv
Thanks roticv. Currently, I don't have algorithms to generate permutations, and there are a number of problems that will be resolved when this work is complete. I also tried to brute force 66, and found an error in the code just now.

Yeah, they are all brute force at some level -- the problem becomes how to reduce the number to tests needed (hopefully, exponentially :)). For example, we can add a test that reduces the number of guesses by half (say with a single instruction); or we could restructure the problem to rule out 9/10th's of all guesses. The quicker a guess can be rejected or confirmed - the better.

Another example is the pandigital problems: there are so few numbers that meet the requirement of an N-digit number being composed of the digits 1 to N, that it wouldn't make any sense to itterate through all the numbers (1000,1002,...,9999). It is better to itterate through N and generate the possible permutations (1234,1243,...,4312,4321).

``````Digits	Numbers		Pandigital
1	9		1	11.11%
2	99		2	2.02%
3	999		6	0.60%
4	9999		24	0.24%
5	99999		120	0.12%
6	999999		720	0.07%
7	9999999		5040	0.05%
8	99999999	40320	0.04%
9	999999999	362880	0.04%
Total	1111111101	409113	0.04%``````
...this has a significant impact on the number of guesses needed. And furthermore no verification of the pandigit-ness of the number needs to be explicitly verified - being inherant in the process. Might be obvious to everyone, but it is just an example of the kind of thinking I'm doing.
Posted on 2004-06-10 10:13:35 by bitRAKE
Yes you are right, bitRAKE. The more we eliminate with such tests the brute forcing component would be faster. Another problem I have encountered is dealing with big numbers. Since I never had my own big number library, I ended up coding in C with miracl.

Oh yes, when you solved problem 57 do tell me. I made some interesting discovery about the continued fractions of root 2 that remind me of Fibonacci and golden ratio.
Posted on 2004-06-11 09:08:33 by roticv
roticv, wow - that is a pretty big hint. :D Yeah, I see it, too. IIRC, that relationship is stating in a book I have on spirals and the continued fraction can be derived from the golden ratio. Bravo on your discovery!

I have posted some big number routines on this board and might release a GMP/mpn/K7 type library in the future. I've only used a single limb multiply/divide, but the above problem will require a multi-limb addition as well.

Funny thing is I just solved this problem with Excel. The number system doesn't support large enough numbers, but I was able to extrapolate where the digits are greater -- it appears to be periodic maybe?
Posted on 2004-06-11 10:17:12 by bitRAKE
If the above refers to question 41, the number of pandigital to test is only 5912 (since 1 is not a prime), because 8digit pandigital and 9digit pandigital are all divisible by 3. (For 9 digit pandigital it is always divisible by 9). Of course I have yet to code it :p Just food for a thought
Posted on 2004-06-15 13:05:24 by roticv
There are several problems that make use of pandigital numbers or permutated numbers...62, 49, 43, 32, 38, 41, ...in my coding it has been better to prune guesses as early as possible rather than to code a complex verification algorithm on the end. We can really get a lot of speed this way - generating as largely correct possiblities from the start. Problem 68 was done with pencil and paper this way - two high level guesses and I was done! :)

On 41, that is certainly true and creates a lower upper bound for the search space. He does say to limit it to 9 digits, but I'm assuming that is true. I have missunderstood many of the problems and continue to email the author of the pages. The gentleman appears very open to suggestion, and is commited to maintaining the problems.
Posted on 2004-06-15 21:41:39 by bitRAKE