Continuing to look at the Project Euler problems. The third 10 are a little more difficult than the previous 20.

My Haskell solution for problem 21 was too slow. So, in Java, I made a table of the sum of the divisors for the numbers from 1 to 9999, then added up the numbers that pointed at each other, as well as the numbers in the table that paired with numbers greater than 9999, and it was reasonably fast.

Problem 22 was straightforward.

I could not write a fast algorithm for problem 23 in Haskell. So, in Java, I made a table of whether the number is abundant for 1 to 28123. Then, each number from 1 to 28123 could be tested by testing for pairs of trues in the table where the indices added up to the number, which should be less than around 200 million tests, and short-circuiting after the first pair is found means the actual number of tests should be much lower than that.

Problem 24 doesn't require much computation. The first element of the nth permutation is the (n-1)/m!+1th element, where m+1 is the number of elements, and the rest of the nth permutation is the remainder of (n-1)/m!+1th permutation of the remaining elements.

Problem 25 was straightforward.

My solution to problem 26 was kind of slow, but not excessively slow. I calculated the cycle length by making a list of the remainders and searched the list of remainders for repeats with each new digit in the quotient. After that, it was a brute-force maximum search: snd $ maximum $ map (\ n -> (cycleLength n,n)) [1..1000].

My solution for problem 27 was kind of slow. b must be a prime under 1000 due to n=0, so there 168 possibilities for b. Given b and n, p = n² + an + b, where p is prime, so a = (p - b)/n - n, so p - b has to be a multiple of n, so I made a list of primes satisfying that condition, which can be mapped to a list of values for a, which can be filtered for |a| < 1000. Then, I brute-force searched the 168 values of b for the maximum n and the corresponding a.

Problem 28 doesn't require much computation. The numbers on the corner of the nxn square, where n is odd, is a simple function of n, so the numbers on the diagonals can be added by recursively adding the diagonals of the (n-2)x(n-2) square.

For problem 29, any pair that has aⁱ ≤ 100, where i > 1 and i divides b is not distinct and can be filtered out.

My solution for problem 30 was quite slow. Since 6×9⁵ = 354294, 299999 is an upper bound. 2⁵ + 5×9⁵ = 295277, 1⁵ + 5×9⁵ = 295246, so I used 295246 as an upper bound for the brute force search. After working on problem 34, which is almost the same problem with a much bigger upper bound, I made the search faster by searching by 10s and only going through the 1s digits if the sum of the other digits is between the number + 9 - 9⁵ and the number. This could be generalized to further prune the search by only considering the most significant digits, and only iterating through less significant digits if sum of the digits is within range of the number.

Continuing to look at the Project Euler problems. The second 10 are a little more difficult than the first 10.

Problem 11 is yet another search. I used transpose . zipWith drop [0..] to get a quarter of the diagonals, and combined it with various uses of reverse to get the rest of the diagonals. The result was on a diagonal.

My solution to problem 12 was horribly slow with hugs, so I solved it in Java. The algorithm I used should be O(N^3/2), and the answer I got was between 50 million and 100 million. Perhaps my calculation of triangle numbers was O(N²) in hugs, instead of O(N), causing the calculation to be O(N^5/2).

Problem 13 might have been more of a challenge when restricted to fixed size integer arithmetic. As it was, take 10 . show . sum.

My Haskell solution to problem 14 was horribly slow, so I solved it in Java by tabulating the results under a million and using the recursive formula whenever it went over a million.

My Haskell solution to problem 15 was horribly slow, so I solved it in Java by tabulating the results by building on the previously tabulated results for smaller grids, which should be O(N²).

Problem 16, like problem 13, was a simple one-liner that would have been much more difficult when restricted to fixed size integers.

Problem 17 is just a matter of counting correctly, without any nontrivial mathematical reasoning or computation.

Problem 18 (and problem 67) can be solved with pretty much a one-liner: foldr1 (\ row sums -> zipWith3 (\ i l r -> i + max l r) row sums (tail sums)).

Problem 19 is an easy brute-force iteration, with only 1200 months to consider. The 100 and 400 year rules can be ignored, given the range.

Problem 20 is a simple one-liner just like problem 16, where the challenge is mainly for those restricted to fixed-size integers.

When there was only busy-work at work, I started working through the Project Euler problems. For the most part, I used the hugs implementation of Haskell, since the problems ought to be solvable without a huge amount of computation. However, some of my solutions were way too slow, so I used Java to solve some of the problems. I haven't submitted any of my answers, so I don't have that verification that my answers are correct.

Problem 1 was a simple one-liner in Haskell

 p1 = sum [3,6..999] + sum [5,10..999] - sum [15,30..999]

Problem 2 was a simple 2-liner in Haskell.

For problem 3, I started by computing a list of primes. After getting the answer, I realized that calculating the primes was superfluous. I could just divide out all factors, starting from 2, regardless if they were prime or not, and the remainder would be the largest prime factor.

I just brute forced problem 4, though I can halve the search space since multiplication is commutative.

Problem 5 was a simple one-liner. Haskell's Prelude provides gcd.

Problem 6 was another simple one-liner.

My solution for problem 7 was pretty slow. Adding a type declaration: primes :: [Int], made it over 3 times faster, though still slow, with hugs. The inferred type would have been primes :: [Integer], but since all of the relevant numbers fit into signed 32-bit integers, [Int] would still give the correct result. I sped up a number of slow solutions by adding Int declarations.

I brute forced problem 8. Since the last digit was a 0, I could just do product . take 5 and not worry about a spurious result, which I would have had to worry about if the number had ended with 09999.

Problem 9 was another brute-force search. Since 1000 > c > b > a > 0, I could limit the search to 1000 > c > 333 and c > b > c/2.

My solution to problem 10 in Haskell was just too slow using hugs, so I wrote basically the same algorithm in about 20 lines of Java, which was fast. The result had to be a long, since it was too big to for 32-bit integers. I manually stored the computed primes in an array in the Java solution. Perhaps hugs wasn't memoizing the list of primes that was being computed, causing the algorithm that was supposed to be O(N^3/2) to be O(N²).

The service that I work on interfaces with things that other people work on. One problem that came up multiple times is that these other systems have hard-coded invalid assumptions that have worked so far, for various reasons. One of the reasons is that one of the early features that didn't fit those assumptions simply got reclassified as unsupported and has been removed from every release. Due to these problems, I'll have to account for these hard-coded assumptions in these other systems when adding new features in the future.