Ooh, been reading about Sudoku algorithms and there are many many many different ways of removing "possibilities" from each square.

Mine doesn't really do that at the moment. I just compile the potential numbers each time I get to the square rather than storing them with the square.

Will be making it a bit more advanced tonight

Read Problem 39 a few days ago and came up with a really elegant solution whilst I was away.

Did most of the work with pen and paper and then transferred that into code at work.

My first solution (using Progress (i.e. very slow) and a P4 3GHz) takes less than 1 second to solve it

I love it when that happens

Will have a look at that one... going to see if it's possible to solve it with a Linq query as it's incredibly fast, there was one for calculating a sum and it did it in milliseconds when for loops took about 10 seconds unoptomised

OK, my old computer died.

It was a 3.4GHz P4 with 4GB ram on WIndows XP.

Ran that code in just over 1 second.

The same code on my new computer (3.1Ghz i5 with 4GB ram on Windows 7) runs in 0.4 seconds.

LOL!

However, the same code in C++ runs in 0.01 seconds.

LOL!

I think my brain has melted.

I just can't work out how to do Problem 29. http://projecteuler.net/problem=29

I've seen that I can work it out without having to actually calulate any of the values by looking at factors but my brain is hurting too much to get any further.

Also I only need to look at the values of "a" which are squares, cubes, etc...

I also know that if a is a square number and b <= 50 then a^b is a duplicate. SImilarly is a is a cube and b <= 33 then a^b is duplicate...

It isn't that simple though.

e.g. for 2 <= a, b <= 10

4 ^ 9 = 8 ^ 6

But that doesn't follow the usual rule and I'not entirely sure how to get those also.

4 = 2^2 so
4^9 = 2^18

8 = 2^3
18/3 = 6
so 8^6 = 2^18 = 4^9
so 8^6 is a duplicate.

Easy enough on paper but I can't think how to write it in a program

LOL!

some rather un linq pseudocode...

from p in (2.To(100).SelectMany(p=>p.Factored()))
select p.Distinct.OrderBy(p=>p);

with Factored() being a method to return an IEnumerable of the values from 2.To(100)

I love being on a techi forum where other people make me feel totally ignorant. When I ring tech support at work, it's always the other way around

I can feel the germ of a solution at the back of my head. It involves an array and elimination using factorisation of indices.

I need to ponder a bit...

yeah, I had a 2d array of bools and was going through to eliminate them.

In a 10x10 it gets all bar 8^4. I just didn't have enough time to get that bit to work.

Will have a think tomorrow.


---
I am here: http://maps.google.com/maps?ll=53.790160,-1.848516

Well annoyingly on that I dont have my extension set on this pc (on my work one for messing about on POCs mostly)

Brute forced that with a nested for loop in under 1.5s (1347ms) on my laptop but reckon getting it under 1 second will be very easy

I found the Linq extensions I have been adding as I go and the BigInteger class in System.Numerics a huge help, especially on this sort of task

Ok, I've done it without requiring factors at all.

For 2 <= a <= 100

Increment a <= 100

Increment n for a^n <= 100

Increment m for m <= 100 * (n - 1)

then (a^n)^(m/n) is a duplicate where m mod n is 0

I'm on my iPhone at the moment so it's hard to type. Will try it at home.


---
I am here: http://maps.google.com/maps?ll=53.790162,-1.848520

Another thing I just thought. You only need to increment a up to 10 (ie sqrt 100)


---
I am here: http://maps.google.com/maps?ll=54.255346,-1.354888

Gah!

Close but not quite! I just need to sort out the maths properly.

VERY ANNOYING!

I've got a program that works upto 5 (i.e. the example on the problem).

It runs in about 0.003 seconds. Answer = 15.

It also works for 2 <= a,b <= 10.

That runs in about 0.003 seconds. Answer = 69.

When I run it for 2 <= a,b <= 100 it also runs in about the same time (0.004 seconds) but the thing says it's giving me the wrong answer!

Given up for now.

I need to sit down with this and go through it properly.

I know what it needs to do I just can't code it easily.



e.g.

I know that these powers of 2 are all duplicates up to N = 16...

2^ (4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 24, 28, 30, 32, 36, 48) are all powers of either 4, 8 or 16...

4^n/2 = 2^ 4, 6, 8, 10, 12, 14, 16
8^n/3 = 2^ 6, 9, 12, 15, 18, 24, 30
16^n/4 = 2^ 8, 12, 16, 20, 24, 28, 32, 36, 48

I know that not all of them appear as powers of 2 (i.e. 2^48 doesn't appear in the grid N = 16) but they do appear as powers of other numbers... (i.e. 2^48 is in the grid as 8^16 etc...).

I just can't work out how to go through them easily in a single algorithm.