Daily Dose of Excel

Euler Problem 83 asks:

NOTE: This problem is a significantly more challenging version of Problem 81.

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in red and is equal to 2297.

131 673 234 103 18
201 96  342 965 150
630 803 746 422 111
537 699 497 121 956
805 732 524 37  331

Find the minimal path sum, in matrix.txt (right click and 'Save Link/Target As...'), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by moving left, right, up, and down.

In the Problem 123 thread Doug Jenkins provided a spreadsheet solution for Problem 83, as well as suggesting an alternate method to solve the problem by padding the matrix. He thereby relieved a huge mental block of mine, but it's in the wrong thread. So I started this one.

Padding the matrix has its advantage. It allows you to use a common relationship in the area of interest without having to worry about variable subscripts being out of range because you'd otherwise reference a row or column that you haven't dimensioned (akin to trying to reference Row(0) on a spreadsheet.) There's some overhead to do this, but it saves special cases at the corners and borders. Doug recommended using 1000000, and that's as good a choice as any. With that in mind, the above matrix comes to look like this:

1000000 1000000 1000000 1000000 1000000 1000000 1000000
1000000   131     673     234     103     18    1000000
1000000   201     96      342     965     150   1000000
1000000   630     803     746     422     111   1000000
1000000   537     699     497     121     956   1000000
1000000   805     732     524     37      331   1000000
1000000 1000000 1000000 1000000 1000000 1000000 1000000

Since a picture = 1 kiloword, you can see how we have slop all the way around for subscripts, with the added advantage that if you make the matrix zero-based, the action starts at Row(1), Column(1). My mind likes it better that way. I used this same padding trick for Problem 67, where you can turn a triangle into a square. It really simplifies the code. With all that for background, here is my code that turns Doug's spreadsheet solution into VBA. It runs in about 3/10's of a second.

Doug mentions seeding the Cell array. This makes a huge difference. It goes through the Do-Loop only 5 times. The answer is known after 4 loops, but it takes 5 for the starting TEMP1 to know it. I couldn't figure out how to avoid that without apriori knowledge of the Answer, which is in the bottom right cell before the padding.

Playing with the spreadsheet solution, I made a third matrix of the array by "pasting special" a copy when all is stable. Then with conditional formatting comparing the two, I could see how the data flows and settles as I stepped through it. It starts from the upper left in kind of a maple-leaf pattern: Strong down the middle, with a spike above and below, and then a weak spike down the left side and the top edge. It takes 11 reps for everything to stabilize.

So, all in all, this is my VBA for Doug's concept. Stephen B and Josh G have other approaches, and hopefully, they'll share. This code is the combination of two half-good ideas I had. Maybe Doug will chime in, too. He's the one who gave me the clue about the whole approach.

The usual angle bracket corrections are in the code. It's interesting that it's Cell(R,C) but Matrix (R)(C) for the syntax.

...mrt

Euler Problem 81 asks:

In the 5 by 5 matrix below, the minimal path Min from the top left to the bottom right,
by only moving to the right and down, is indicated in red and is equal to 2427.

131   673   234   103   18
201   96    342   965   150
630   803   746   422   111
537   699   497   121   956
805   732   524   37    331

Find the minimal path Min, in matrix.txt (right click and 'Save Link/Target As...'),
a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right
by only moving right and down.

This is very similar to problems 18 and 67, except that they ask for the maximum path to the bottom, not the minimum path to the lower right corner. #81 can absolutely be done in a spreadsheet, as Tushar shows here for numbers 18 and 67. I like to solve them in VBA. The difference between this problem and #67 is that we have to get to a specific matrix cell, and by the rules, if we end up at the right edge, we can only go down, and if we end up at the bottom, we can only go right. In other words, on the right, progressively sum upwards from the lower right corner, and on the bottom, progressively sum leftwards from that same corner. The goal is to abstract the problem so the choice at matrix cell(0)(0) is the minimum of all paths to cell(0)(0). The answer will be the sum of cell(0)(0) and that minimum. Here is my code that does this. It runs in a blink (less that a tenth of a second.)

Having done #67, this was very straight forward. Problem #83, which uses the same matrix, is similar but harder. It's having its way with me. Here is #83:

NOTE: This problem is a significantly more challenging version of Problem 81.

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in red and is equal to 2297.

131 673 234 103 18
201 96  342 965 150
630 803 746 422 111
537 699 497 121 956
805 732 524 37  331

Find the minimal path sum, in matrix.txt (right click and 'Save Link/Target As...'), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by moving left, right, up, and down.

Note the NOTE, the rules change, and the snaking path. It takes 12 moves, whereas #81 only takes 8. The minimum on the left depends on the minimum on the right. As Doug J has said, 'tis circular, and I've not grasped it yet. The various code I've written does the example, but either takes more than 6400 moves (visiting every cell several times) or ends up in an endless loop in the lower right corner of matrix.txt.

...mrt

Euler Problem 123 asks:

Let p(n) be the nth prime: 2, 3, 5, 7, 11, ..., and let r be the remainder when (p(n)-1)ⁿ + (p(n)+1)ⁿ is divided by p(n)².

For example, when n = 3, p(3) = 5, and 4³ + 6³ = 280. 280 mod 25 = 5.

The least value of n for which the remainder first exceeds 10⁹ is 7037.

Find the least value of n for which the remainder first exceeds 10¹⁰.

This is really the same problem as Euler 120 (posted last week) with p(n) taking the part of a. We are looking for 2*p(n)*n greater than 10¹⁰. I built a collection of the first 7037 primes, and then added primes one-by-one to the collection until the remainder was large enough, with the caveat that even n gives a remainder of 2, so we need an odd n.

All prime numbers beyond 3 lie left or right of an even multiple of six so a prime-checking routine need only check whether or not n mod 6 = 1 or 5 has even divisors, and even then, only up to the square root of n.

Here is the code that does that. The routine runs in about 2.5 seconds.

Dick has more on prime numbers here. The usual angle bracket corrections are in the above.

...mrt

Euler Problem 120 asks:

Let r be the remainder when (a-1)ⁿ + (a+1)ⁿ is divided by a².

For example, if a = 7 and n = 3, then r = 42:

• 6³ + 8³ = 728
• 728 mod 49 = 42

And as n varies, so too will r, but for a = 7 it turns out that r_max = 42.

For 3 <= a <= 1000, find Sum(r_max).

All my brute force attempts to solve this problem overflowed whatever variable type I used, from longs through currency through decimal variants through doubles. Another approach was needed, and Isacc Newton had it figured out in his binomial theorem, which gives the expansion of (x+y)ⁿ.

Four examples:

(a+1)2 = a2+2a+1
(a-1)2 = a2-2a+1
(a+1)3 = a3+3a2+3a+1
(a-1)3 = a3-3a2+3a-1

Adding equations (1) and (2) together, which have n = 2, gives

(a+1)n + (a-1)n= 2an+2

This is true for all even n.

Adding equations (3) and (4) together, which have n = 3, gives

(a+1)3 + (a-1)3 = 2a3 + 6a
2a3 + 6a = 2an + 2an

This is true for all odd n.

Within equations (5) and (7), 2aⁿ is evenly divisible by a². The remainders are thus 2 for even n and 2an for odd n respectively. How big can n grow? Such that 2an stays less than a², or 2n is less than a. Otherwise, a² divides one more time.

Looping through a = 3 to a = 1000 and summing 2an provides the answer. This simple code does that. It runs in a blink.

The usual angle bracket adjustment is in the code. Next week, I'll put up Problem 123, which uses this same approach, but with a as prime numbers.

...mrt

Euler Problem 206 asks:

Find the unique positive integer whose square has the form 1_2_3_4_5_6_7_8_9_0,
where each “_” is a single digit.

First thing to note is that Euler wants the integer, not the square that conforms to the pattern. That failure to RTFQ costs me a couple of hours as I kept trying to check in a 19-digit number when the answer is a 10-digit number. I saw immediately how to build the numbers that fit the pattern, and wrote this code:

It runs in a very uncool 21+ seconds on my home machine. It builds the number squared by successively concatenating a counter with the digit that lies at that counter within a string variable that counts down from 999,999,999; and then it looks for integer square roots. I counted down instead of up from Euler experience--Euler's answers tend to be at the high end of anticipated values. Neat idea, not so neat for performance, and I was surprised that doubles were accurate enough to solve a problem requiring 19 significant figures. Euler often asks for computations beyond their accuracy. The answer is the sole integer square root. End when that number is found.

So I rewrote the code from the square root point of view. The largest possible number is when the underscores are all nines, and the smallest when the underscores are all zeros. Compute those square roots, again as doubles, and check from the top down for the sole square between those numbers squared that conforms to the pattern. Doing it as a decimal variant provides all the precision required.

One thing I learned from that is that CDec() is not commutative. There is a difference between Cdec(A*A) and CDec(A)*CDec(A)

This code ran in .04 seconds. Now that was cool. I should have thought harder back at the beginning. The first was way checks about 2.77 billion numbers for every one the second way checks.

...mrt

Euler Problem 100 asks:

If a box contains twenty-one coloured discs, composed of fifteen blue discs and six red discs, and two discs were taken at random, it can be seen that the probability of taking two blue discs, P(BB) = (15/21)×(14/20) = 1/2.

The next such arrangement, for which there is exactly 50% chance of taking two blue discs at random, is a box containing eighty-five blue discs and thirty-five red discs.

By finding the first arrangement to contain over 10^12 = 1,000,000,000,000 discs in total, determine the number of blue discs that the box would contain.

Using R for #Red, B for #Blue and T for total (R+B), the basic equation here is:

          B * B-1 = 0.5
          T   T-1

Since they can neither equal each other nor both be the square root of 0.5 (or 0.707106781...) we want B/T to be a skosh over the square root of 0.5, and (B-1/T-1) a skosh under. In other words, the answer will be the first integer B greater than Sqr(0.5)*10^12.

If we rearrange the equation, we get

• 2B^2 - 2B = T^2 - T

A single double quadratic equation with two unknowns can be morphed into a Pell equation with either no solutions, or an infinite number of them. Again, Euler wants the first solution with total discs T greater than 10^12. The first hit on a Google search for probability and Pell (here) returns an article exactly on point, with the examples for P=0.5 worked out in the first 11 cases. Dr. Sasser must have written it in a hurry, because it can be confusing. He uses two variables y, and they mean different things. I'm going to try to sort that out. There are also a few typos, but you can figure them out from context. The above equation does morph, as Dr. Sasser shows how, into Pell-form x^2 - Dy^2 = C as

• x^2 - 2y^2 = -1

with y = 2B-1. B, the number of Blue discs, is then (y+1)/2. Once we have the y solutions, we have the B solutions. The solutions for this Pell equation are x + y*Sqr(2) = (1 + sqr(2))^n, for integer n.

Flashing back to algebra, the product of (aw + bz)(cw + dz) is:

• acw^2 + (ad + cb)wz + dbz^2

If c = 1, w = 1, d = 1, z = Sqr(2), and z^2 = 2 corresponding to solution 1*1 + 1*Sqr(2) then rearranging the above gives:

• a + 2b + (a+b)*Sqr(2)

This is of the form x + y*Sqr(2) with x = a + 2b and y = a + b. This gives us a method to take (1 + Sqr(2)) to any integer power n. Recall that we're looking for the y = a + b that gives B = (y+1)/2 greater than Sqr(0.5)*10^12.

This is the code that does that. It runs in a blink.

The first time I attempted this problem I incremented B or T as necessary to get just above Sqr(0.5)*10^12. Don't go that way. Floating arithmetic errors give "false positives" for that approach.

There usual angle bracket corrections are in the code.

...mrt

Euler Problem 80 asks:

It is well known that if the square root of a natural number is not an integer, then it is irrational. The decimal expansion of such square roots is infinite without any repeating pattern at all.

The square root of two is 1.41421356237309504880..., and the digital sum of the first one hundred decimal digits is 475.

For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots.

The first thing I wanted to know to solve this problem was what the square root of 2 was to 100 places. I wasn't getting the right sum. I found it here.

1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727
which is
979291172255376750081652821559640563801792871084643
divided by
692463428657900307544320387485120303323686251920582

When I summed the decimal digits, I got 481, not 475. But if I drop the right-hand 7 and add the left-of-the-decimal 1, that's a down-spot of 6. Euler wants the sum of the first 100 digits, not the first 100 after the decimal.

To make the calulation I wanted an algorithm that computed square roots as strings. I found that here. The author says of his Japanese method

It is an amusing exercise to program a computer to do this algorithm, at least if n is an integer, and because only integer additions and subtractions are used, there are no errors due to floating-point arithmetic. On the other hand, it is necessary to use more complicated storage techniques (strings or arrays) to store the values of a and b as they get larger and larger, and the algorithm will get slower and slower at producing successive digits.

Amusing? I'm not so sure. To implement the Japanese method in strings, it took me a while to find the equivalent of "a greater than or equal to b" where a and b are string representations of numbers. I ended up with:

• If the length of a is greater than the length of b, then a is greater than b
• If the length of a is less than the length of b, then a is less than b
• If the length of a equals the length of b then do a string-comparison

Don't know why that took as long as it did.

I also needed an algorithm for subtracting strings. Rather than write a "borrowing" routine, I used the "method of nines'-complement" found here on Wikipedia.

When it was all done, the code runs in 11 seconds.

The usual angle bracket adjustments have been made above. The AddAsStrings function has been put up before. Dr Jervis' Japanese method requires you to independently place the decimal point in the square root. I made that optional, and set it to false to accomodate Euler's way of counting.

...mrt

Euler Problem 104 asks:

The Fibonacci sequence is defined by the recurrence relation:

F(n) = F(n-1) + F(n-2), where F(1) = 1 and F(2) = 1.

It turns out that F(541), which contains 113 digits, is the first Fibonacci number for which the last nine digits are 1-9 pandigital (contain all the digits 1 to 9, but not necessarily in order). And F(2749), which contains 575 digits, is the first Fibonacci number for which the first nine digits are 1-9 pandigital.

Given that F(k) is the first Fibonacci number for which the first nine digits AND the last nine digits are 1-9 pandigital, find k.

The title really deserves an exclamation point. As discussed in Large Number Arithmetic I've been trying to solve this problem since before January. This problem breaks my little AddAsStrings function, and for reasons you'll see, overflows Tushar's LargeAdd function. We're looking for a big number, longer in length then Excel can handle as a string. And I was stuck. Doug, in Large Number Arithmetic, showed how to keep track of the back end of a variable. How to keep track of the front end had me stumped until it came to me last Sunday morning when I woke up (any one else code in their sleep?): Separate variables. Use a long to track the backend and a double to track the front end. An immediate trouble with that is that doubles only work to E+308, and one of the test cases, Fib(2749) is E+575. Solution there was to knock the Fibonacci values down by 10^2 when ever they get over 10^9, and keep track of the exponent in a separate variable. Here is my code, with a helper function Ends() that tests the ends for "pan-digitality." It's a little faster than most I've seen, since it breaks as soon as there is a failure, rather that testing on, and I only test the left side when the right side is pandigital. The code runs in six-tenths of a second:

Compared to the multi-precision answer given by the Foxes Team addin mentioned in Large Number Arithemtic, this answer drifts off in the 13 decimal place. The xnumbers add-in has been helpful. It did the Euler totient problems, for instance. It's been a useful addition to the toolbox, and since any improvement has stopped, I'd recommend grabbing before it disappears.

...mrt