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.