I just started using git for version control, and made some free repositories on github. I haven't tried anything beyond the very basics of creating a repository and committing and fetching code from multiple sites. I haven't made any branches or done any rebasing. For the basics, the only new concept I had to learn was the index, which I glossed over when first reading the documentation. After playing around a bit, I got a little confused, then kind of figured out what was going on, then read the documentation again, and it became clear.

More Project Euler problems.

For problem 51, I only had to try replacing the 0s, 1s and 2s, since there had to be 8 values in the family. And I didn't have to try replacing 1s with 0s or 2s with 1s or 0s, since those would be redundant.

I just did a brute force search from 1 on up for problem 52. It would be more complicated and maybe faster to skip numbers where the most significant digit is not 1, but the answer wasn't all that big, so it wouldn't be significantly faster, if at all.

For problem 53, since ⁿC₀ = ⁿC_n = 1, and C increases rapidly from the edges and peaks at the middle, I counted the values under a million for 0 ≤ r ≤ n/2, doubled it and subtracted.

For problem 54, using Haskell's deriving (Ord) with an appropriate data structure and mapping the card values to values that ordered the ace, face cards, and ten correctly made it simple. Also, there were no instances of A 2 3 4 5 in the data, which, if considered a straight, would have had to have a special-case constructor to be ordered correctly.

I just brute-forced problem 55 over the range 1..9999.

For problem 56, the upper bound for the sum of digits is 9b log₁₀a, and log₁₀a < 2, so the upper bound is 18b. So the maximum value for b = 99 establishes a lower bound for b that needs to be searched. Subsequent new maximums for b < 99 can raise that lower bound. I wound up searching 1 ≤ a ≤ 99 for 54 ≤ b ≤ 99.

For problem 57, I found that doing head (show numerator) < head (show denominator) was faster than counting all the digits, as it's known that numerator/denominator is approximately 1.4.

For problem 58, I just did a brute force iteration over each square, with running counts of the total and the number of primes.

For problem 59, I printed out every 3rd character decoded with each of the 26 possible key characters, and then visually chose each of the 3 characters in the key.

For problem 60, I could only come up with a super slow solution, though it did come up with the answer in about 10 minutes, and ruled out other possible answers after 30 more minutes. I made a very wide, shallow tree, spitting out results when reaching a depth of 5. I had to do a bunch of redundant calculations, because although I had a branch starting with 3,7,109,... I still needed branches starting with 3,..., 3,7,..., 3,109,..., 7,..., 7,109,..., 109,.... I'm thinking that a graph-based algorithm, instead of a tree-based algorithm would be faster, should I revisit this problem.

Looking at more Project Euler problems.

I thought problem 41 was going to be tough, but there are only 9! = 362880 nine-digit numbers to consider, and even fewer 8-digit numbers to consider, etc, so it was just a matter of checking for the first prime permutation.

Problem 42 was straightforward. I made a list of triangle numbers up to the maximum word value, then filtered the word values and counted.

For problem 43, I started by taking all multiples of 17 under 1000, filtering out any with repeated digits. Adding the 4th digit made the set 7 times bigger, but removing those that did not have the divisible by 13 property made the set about half the size. Iterate for the remaining digits.

I couldn't find a reasonable way to solve problem 44. It involves finding 4 pentagonal numbers, p_i, p_j, p_k, p_l, where p_i ≤ p_j < p_k < p_l, and p_i = p_k - p_j, and p_j + p_k = p_l, where p_i is minimized. For a given i, there's an upper bound for j, such that p_i ≥ p_j+1 - p_j, and the upper bound for j is O(i²), which means a brute-force search over i gets extremely slow. However, since I didn't have any better ideas, I searched i from 1 to about 350 or so without finding a solution, and gave up.

For problem 45, I made a list of hexagonal numbers, filtered out those that weren't pentagonal or triangle, and took the 3rd number in the resulting list, the first two being 1 and 40755. It would have been slightly slower to make a list of pentagonal or triangle numbers, and filter out those that weren't the other types.

For problem 46, I iterated over non-prime odd numbers, building up a list of primes and doubled squares less than it, stopping when none of the primes could be added to one of the doubled squares to get that number.

In problem 47, I only had to check every 4th number until one had at least 4 factors, then check the previous one, the one before that, and the one before that. If any didn't have at least 4 factors, I could jump forward 4 from that.

For problem 48, using mod 10¹⁰ arithmetic means not having to add gigantic numbers, while still getting the last 10 digits.

For problem 49, I took all the 4 digit primes and grouped the ones that were permutations of each other together, then searched each group for a qualifying triplet.

For problem 50, I found the longest prime sum starting with 2, as well as the list of primes after the last term of the sum. Then, I subtracted 2 and added the next largest prime, looking for the longest sum starting with 3, and iterating until subtracting the next smallest prime and adding enough of the next largest primes to make the sum have more terms than the current longest sum resulted in a sum more than a million.

Looking at the 4th ten Project Euler problems.

Problem 31 is a straightforward recursive count. Once you get to the 1p, the number of combinations is 1.

For problem 32, 99×99 = 9801 and 111×111 = 12321, so all the solutions have to be a two-digit number × a three-digit number resulting in a four-digit number. I did a brute-force search through all the combinations of 5 digits of the multiplicands.

Problem 33 just involved searching with 1 through 9 to see if any pair of digits had the property, so that was a small search. Also, there were only 36 pairs of digits to check.

Problem 34 is just like problem 30 with a larger bound.

For problem 35, I partitioned the primes by number of digits, then filtered out the numbers that were not the minimum of the digit rotations, which conveniently eliminated all numbers with zeros. I then filtered out the numbers for which not all of the rotated numbers were in its partition, which eliminated 11. 111, 1111, 11111, 111111 are all not prime. Then multiple the size of each partition by its number of digits, sum, add 1 for 11 gives the answer.

Problem 36 was a brute-force filter. Since leading zeros weren't allowed, even numbers could be eliminated, cutting the problem in half.

For problem 37, I built lists of n-digit primes that could be truncated from the left to n-1-digit primes, and lists of n-digit primes that could be truncated from the right to n-1-digit primes. The intersection of the left and right lists gives the 11 numbers.

From the example in problem 38, the first digit had to be a 9, so it was just a matter of searching 91..98, 912..987, 9123..9876, and 91234..98765.

For problem 39, p/3 < c < p-3, and c/2 < b < c-1. After that, I just did a brute-force search, which was kind of slow.

Problem 40 is just multiplying 7 single-digit numbers, and at least 2 of them are 1. It's straightforward to figure out those numbers, and, as it turns out, the product of those numbers is simple to mentally compute.

I wanted more immediate feedback about my Rock Band scores, so I modified the code I wrote that takes a picture of the television screen and does OCR (optical character recognition) to figure out what song was just played, and run text-to-speech with the name of the song and my high score. It works about half the time. But when it works, I get to know if I got a new high score without having to go over to the computer and check, which means I can be ready to play the next song.

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.