JordiB saidI solved this problem a year or so ago and don't have the code handy. I could of course look in the answers thread over on ProjectEuler.net (which is only available to people who solved the problem), but I think I remember how I did it and if you optimize it, it might indeed be O(n) for both time and space complexity. I used a vector/array of length one million where each element signifies the chain length if you would start the sequence with its index (+1 if indices start at 0).
This is exactly what I had in mind as well.
If the numbers would all stay below one million, then you would only have to do a million calculations to fill the vector's values. You can then easily select the largest. The only problem is that the numbers don't stay below one million and I didn't really do anything about that. I haven't checked how many numbers over one million there are that will be 'visited' more than once, but the program ran pretty fast, so it's probably not that big a deal. It would still be nice to have a more elegant solution for this part of the problem though. I guess that for these high numbers you could use a dictionary, but I doubt lookup time for that would be O(1). Also, if the relation between n and the number of numbers over n is greater than O(n), I don't think the solution can ever be in O(n), but I don't think that that is the case.
I think I have a solution to that which will allow (amortised) O(1) lookups and allow the array to grow as needed. I've been meaning to implement the data type for a rope class (like strings, but bigger) and this might be a good opportunity to try an implementation. The one that this will need will be a bit simpler.
