## Project Euler Problem #64

### March 4, 2012

Read the details of the problem here

Summary

How many continued fractions for N ≤ 10000 have an odd period?

Solution

It took a little while for me to understand how this was working so, to make it clearer this is essentially what’s required.

1. Take the square root of the original number then…
2. The integer portion becomes the next number in the sequence,
3. Take the reciprocal of the remaining decimal portion,
4. Take this number as input into Step 2.

Obviously, at step 3, if the decimal portion has been seen before, that sequence would just repeat from then on, so a cycle would have been found. In that respect it’s very similar to the solution for Problem #26.

As an example, here’s the trace for 23, with it’s square root – 4.79583.

n Digit Remainder
4.79583 4 0.79583
1.25655 1 0.25655
3.89792 3 0.89792
1.11369 1 0.11369
8.79583 8 0.79583
1.25655 1 0.25655

Whilst this works as an implemented algorithm for numbers with short sequences it breaks down on the longer ones, some of which are over 200 elements long, due to problems with precision. So I expanded out the algorithm to better reflect the way that Euler describes in the question and coded that up. I made the assumption that the sequence would start from the first position rather than an arbitrary one.

```def cf(n) {
def ( i, j, c, k ) = [ 0, 1, 0, null ]
def sqrt_n = Math.sqrt(n)
while (true) {
j = (n - (i * i)).intdiv(j)
i = -(i - ((int)(sqrt_n + i)).intdiv(j) * j)
if ([i, j] == k) return c - 1
if (c == 1) k = [i, j]
c++
}
}

(((int)Math.sqrt(it)) ** 2 != it) && (cf(it) % 2)
}
```

This executes in Groovy 1.8.6 under Java 7u3 on my Samsung 700G7A i7-2670QM 2.2 GHz machine in around 0.45 seconds, so well within my 5 second cut-off (reduced from the old 15 seconds on my old machine). This runs quite fast as it only ever uses integers – apart from the initial sqrt calculation.

Conclusion

Didn’t use many Groovy features for this solution in the main apart from keeping the function initialization quite terse and the count listop on the number range. Performance was fairly good – though an equivalent Java solution does run in 55 ms – around 8 times faster.

## Project Euler Problem #65

### January 29, 2012

Read the details of the problem here

Summary

Find the sum of digits in the numerator of the 100th convergent of the continued fraction for e.

Solution

This question immediately reminded me of Problem #57 which ended up being quite a simple solution though it sounded involved initially. I took a look at that, and adopted a similar approach to this one.

The trick with this problem was to spot the pattern as to how the numerator changed down the sequence. As it turned out, the values of the denominator are superflous to this and can just be ignored for this purpose.

Taking the first ten terms as given (with a zeroth term for completeness) given this is how it works:

Term Numerator Multiplier Formula
0 1
1 2 2 2 * num0
2 3 1 1 * num1 + num0
3 8 2 2 * num2 + num1
4 11 1 1 * num3 + num2
5 19 1 1 * num4 + num3
6 87 4 4 * num5 + num4
7 106 1 1 * num6 + num5
8 193 1 1 * num7 + num6
9 1264 6 6 * num8 + num7
10 1457 1 1 * num9 + num8

So this can be summarised as:

numn = muln * numn-1 + numn-2

Where n is the term being calculated and muln is the nth element of the continued fraction.  This is simply n / 3 * 2 when n mod 3 == 0, and 1 otherwise.

Given that the multipliers work in triplets, this can be used to advantage and reduce the number of calculations required. I created a function that given the n-1 and n-2 numerators, and a term number could calculate the next three numerators in the sequence. It meant that I didn’t have to do any modulus calculations as long as I kept the boundary aligned correctly i.e. only call it for terms, 2, 5, 8, etc. which were the start of the triplets.

Starting at term 2, I then called this recursively until it was being asked to calculate the 101st term. At this point the 100th term would be the n-1 numerator value and could be returned.

```def f(p1, p2, tc) {
if (tc == 101) return p1
def m = p1 + p2
def n = ((tc + 1).intdiv(3) * 2) * m + p1
f(n + m, n, tc + 3)
}

(f(2G, 1G, 2).toString() as List)*.toInteger().sum()
```

This runs in around 115 ms, with sum of the digits taking about 10 ms. A port of this code to Java runs in around 1.3 ms in total.

Conclusion

Groovy was a nice language to do this in. Not having to mess about with BigInteger objects explicitly is always a boon in the Java world. Performance was quite disappointing though – given that f() is only ever called with BigInteger arguments the compiler should be able to work out exactly what types the variables are and the generated bytecode should be pretty similar to that which javac outputs…but it’s not. In this case Groovy is nearly two orders of magnitude slower and I really don’t see a good reason for it at this stage in the language maturity.

## Project Euler Problem #69

### May 21, 2010

Read the details of the problem here

Summary

Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.

Solution

I started by creating a program that calculated totient values and displayed when it found maxima. It became evident that it simply was not going to scale to the scope of the problem. It did, however, given an obvious (in retrospect) insight into the problem.

The results that I got back from my program, before it essentially ground to a halt, were as follows:

n φ(n) n/φ(n)
2 1 2
6 2 3
30 8 3.75
210 48 4.375
2310 480 4.8125
30030 5760 5.213542

I recognised the values in n as the products of consecutive primes.

So, for instance, 30 = 2 * 3 * 5, 210 = 2 * 3 * 5 * 7. This meant that is was just a case of finding the maximum product of primes without exceeding the one million limit, which was the work of moments!

So the insight was, in order for the totient to be maximized, the number of primes making it up has to be maximized, so reducing considerably the number of relatively prime smaller numbers, hence the maxima was always to be found at these multiples.

Conclusion

Engage brain before typing code.

## Project Euler Problem #68

### May 21, 2010

Read the details of the problem here

Summary

What is the maximum 16-digit string for a “magic” 5-gon ring?

Solution

I really didn’t think I’d be able to do this in Groovy and get it to run within my 15 second limit, at least not without some fiddly recursive solution. However, I used Groovy 1.7.2 which has been out for a while now and offers somewhat improved performance and a few extra collection operators. Notable in this solution is the eachPermutation() method which will iterate over a collection and call the closure for each permutation of elements.

The solution itself is quite straightforward and obvious. I don’t want to have duplicated (i.e. rotational symmetric) results so I enforce an ordering of numeral around the outer ring, this means that the first element can’t be greater than 6 otherwise there would be insufficient numbers available. I then enforce the ordering. The next step is to make sure that the number ten doesn’t appear in the inner ring otherwise it would appear twice in the concatenation and make it 17-digits. After getting through those basic guard conditions it’s then a case of making sure the various legs all add to the same total before assembling the string & checking to see if a new maximum has been found.

```def SEQ = [ 0, 6, 7, 1, 7, 8, 2, 8, 9, 3, 9, 5, 4, 5, 6 ]

(1..10).eachPermutation { nums ->

if (nums[0] > 6) return

for (i in 1..<5) {
if (nums[0] > nums[i]) return
}

for (i in 5..<10) {
if (nums[i] == 10) return
}

def sum = nums[0] + nums[6] + nums[7]

def p = 3
while (p < 15) {
if (sum != nums[SEQ[p]] + nums[SEQ[p+1]] + nums[SEQ[p+2]]) return
p += 3
}

def sb = new StringBuilder()
for (i in 0..<15) {
sb.append(nums[SEQ[i]])
}

}
```

It runs in 8.3 seconds. Not fast, but within the 15s target so I’ll leave it there! Improvement is left, as they say, as an exercise for the reader…

Update: Having gained access to the forum, it seems that there is an additional logical tweak, actually a slight refinement to the commencing number that can be used. If I make that minor change the run time drops to 4.3 seconds. Even better!

Conclusion

I thought that Groovy allowed for quite a quick time-to-solution for this problem. Although not the top in performance it wasn’t bad considering this is a brute-force approach. The code is quite clear in intent without a lot of supporting noise.

## Project Euler Problem #63

### May 21, 2010

Read the details of the problem here

Summary

How many n-digit positive integers exist which are also an nth power?

Solution

The first thing was to determine the potential scope of the problem. The base number had to be 9 or less, as 10 (or above) to any power is going to have more digits than the power. Obviously 9 is going to have the highest possible power which is 1/(1-log(9)), which rounded down is 21, before having insufficient digits in the number.

921 = 109418989131512359209,
922 = 984770902183611232881.

So 922 only has 21 digits, therefore a power of 21 forms the upper search bound.

I was about to write a brute-force solution based on this when it struck me that all I actually needed to do was to sum up these maxima for the eligible bases i.e. 1-9, and not have to calculate the actual numbers themselves.

```def answer =
(1..9).sum { (int)(1 / ( 1 - Math.log10(it))) }
```

So it ended up just being a one-liner that runs in 28 ms.

Conclusion

Groovy listops made the solution very terse!

## Project Euler Problem #70

### May 5, 2010

Read the details of the problem here

Summary

Investigate values of n for which φ(n) is a permutation of n.

Solution

I’d done Problem 69 sometime ago but that was a fairly obvious non-programming solution. I’d taken a look at this problem and it looked a lot more complicated and without anything concrete to leverage from the previous problem, so I skipped over it. However I was hunting around for a problem that I might have a good stab at to make my century and gave this one some more consideration.

I knew from the previous problem that the ratio of n/φ(n) was maximised when n was the product of many small prime factors (there’s the giveaway for that one!) hence with few relatively prime numbers. It seemed reasonable that it would be a minimum when n was a product of a small number of large, prime factors – so best case would be only two. A little bit of experimentation (using a GCD calculation) showed this to be the case with a good degree of confidence (though it was far from a formal proof). I also found that if n = p1 * p2 then φ(n) = (p1-1) * (p2-1). This would obviously be a big help as long as the assumptions held true as it was very evident that a GCD approach was hopeless.

For a few first multiples of primes and the exemplar:

p1 p2 p1*p2 (n) (p1-1)*(p2-1) Relatively Prime φ(n) n/φ(n)
2 3 6 2 1,5 2 3
3 5 15 8 1,2,4,7,8,11,13,14 8 1.875
5 7 35 24 1,2,3,4,6,8,9,11,12,
13,16,17,18,19,22,23,
24,26,27,29,31,32,33,
34
24 1.45833…
7 11 77 60 1,2,3,…,74,75,76 60 1.28333…
11 7919 87109 79180 loads of them… 79180 1.10013…

Given that the exemplar was of this two-prime form, I suspected that might be on the right track as Euler is quite good on giving clues like this.

So the next step was to determine which primes might be eligible for calculation. As mentioned earlier, I wanted them both to be as large as possible and so it makes sense to concentrate around the square root of the limit given (107). I decided to give it 30% either way from the square root and expand outwards if necessary. The square root of 107 is 3162.28 so that meant creating primes running from 2213-4111 (in which there happens to be only 236 primes). I did this using the normal sieve method before constructing the list from it.

It was then just a case of running through the 27,730 combinations of primes, some of which would exceed the limit and could be quickly discarded, and doing the necessary calculations.

```def LIMIT = 10000000
def UPRIME=(int)Math.ceil((Math.sqrt(LIMIT) * 1.3))
def LPRIME=(int)Math.floor((Math.sqrt(LIMIT) * 0.7))

def isPrime = new boolean[UPRIME]
Arrays.fill(isPrime, true)
(0..1).each { isPrime[it] = false }

for (i in 2..<Math.sqrt(UPRIME)) {
if (!isPrime[i]) continue
def j = i + i
while (j < UPRIME) {
isPrime[j] = false
j += i
}
}

def primes = []
for (i in LPRIME..<UPRIME) { if (isPrime[i]) primes << i }

def ( answer, min ) = [ 0, Double.MAX_VALUE ]

for (i in 0..<primes.size()-1) {
for (j in i+1..<primes.size()) {
def n = primes[i] * primes[j]
if (n > LIMIT) break
def phi = (primes[i]-1) * (primes[j]-1)
if (n.toString().toList().sort().join()
== phi.toString().toList().sort().join()) {
def ratio = n / phi
if ( ratio < min ) ( answer, min ) = [ n, ratio ]
}
}
}
```

This runs in a quite satisfactory, and quite surprising quick, 0.26 seconds. Though I must admit that I was somewhat lucky with the bounds of the primes. A Java version, using an int array rather than list for the primes, but otherwise the same logic runs in 13 ms – so around 20x faster.

Special Note: This was my 100th correctly answered question, so I’m now in the Hall of Fame albeit as a n00b Novice, being ranked at 115/2292 in England.

Conclusion

Groovy was useful in creating the check for a permutation but I steered mostly clear of listops & syntactic sugar as I was concerned, perhaps needlessly as it turned out, about performance.

## Project Euler Problem #67

### February 8, 2010

Read the details of the problem here

Summary

Using an efficient algorithm find the maximal sum in the triangle?

Solution

This is just a larger version of the problem first introduced in Problem 18 and the algorithm and code I used for that was suitable for this problem too. For details on that see my previous post for a solution.

```def tiers = []
new File("triangle.txt").eachLine { line ->
tiers << line.trim().split(" ")*.toInteger()
}

(tiers.size()-2).downto(0) { row ->
for (i in 0..<tiers[row].size()) {
tiers[row][i] += [tiers[row+1][i], tiers[row+1][i+1]].max()
}
}