Daily Dose of Excel

Euler Problem 188 asks:

The hyperexponentiation or tetration of a number a by a positive integer b, denoted by a^^b or ^ba, is recursively defined by:

a^^1 = a,
a^^(k+1) = a(a^^k).

Thus we have e.g. 3^^2 = 3³ = 27, hence 3^^3 = 3²⁷ = 7625597484987 and 3^^4 is roughly 10^{3.6383346400240996*10^12}.

Find the last 8 digits of 1777^^1855.

Euler uses double up-arrows for hyperexponentiation. I substituted double carets as a “reasonable facsimile.” Tetration is covered by this Wikipedia article. A key point is to note that tetration is not associative, and we must evaluate the expression from right to left (top to bottom).

This is the recursive version:

This works fine, but it won’t handle 1777^^1885. Python has a Pow(b,e,m) function that returns base b raised to exponent e modulo m.

This is what we want to duplicate, particularly since returning the last 8 digits in to the same as modulo 10⁸. Here is the VBA translation of Pow(b,e,m):

I used decimal variants, so this will work for m-1 up to the square root of ~7.92e29, or about ~8.9e14. Big enough. BitShift in this case is integer division by 32. Here are those functions:

The usual angle brackets substitutions are above. Altogether then, this is the code for Problem 188:

Simple enough, but a lot of homework for this one. It put some more tools in the toolbox, and runs in less than 1/10 of a second.

..mrt

Summing the digits of a number is a chore I’ve been doing alot lately. Originally I’d parse the number out over the columns. And since SUM() ignores text, I’d turn the characters into digits by applying an arithmatic identity operation, like this:

• =- -MID($A10,COLUMN(),1)

That’s double minus signs before the MID() function. The reasons for picking that identity operation are here at XLDYNAMIC’s website, about half-way down.

And filling right. But if the numbers were of uneven length, filling down would throw a #VALUE! error for all but the longest number. Contrary to what the Help advises, I find that SUM() does not ignore error values. So I was ending up with this formula so I could fill down:

• =IF(ISERR(–MID($A10,COLUMN(),1)),0,–MID($A10,COLUMN(),1))

That’s double ugly, and a cell-eater to boot. I did a Google search and found Microsoft Knowledge Base article 214053 on this topic. Here’s what it says:

Formula 1: Sum the Digits of a Positive Number
To return the sum of the digits of a positive number contained in cell A10, follow these steps:

1. Start Excel 2000.
2. Type 123456 in cell A10.
3. Type the following formula in cell B10:
   =SUM(VALUE(MID(A10,ROW(A1:OFFSET(A1,LEN(A10)-1,0)),1)))
4. Press CTRL+SHIFT+ENTER to enter the formula as an array formula.
5. The formula returns the value 21.

Ignoring Step 1, I looked at Step 4 and thought, from hanging around here, that we can do better. But to do better, let’s first look at the formula from the inside out. OFFSET() returns a reference one row less then A10 is long (more on OFFSET() later). ROW() then returns an array of row numbers starting from 1 (the row of A1–It’s the 1 that’s important, not the A) to the bottom of the offset. The array has as many elements as the length of the number in A10. MID() then creates an array of each digit as text. VALUE() turns the text into numbers, and then SUM(), array entered, sums the array of values.

While my formula was double-ugly, this one is just ugly. To impove it, from the outside in:

1. Replace SUM() with SUMPRODUCT(). The formula no longer has to be array-entered, and it works just as well.
2. Replace VALUE() with the double minus
3. Instead of using LEN(A10)-1 as a row offset, use LEN(A10) as a height parameter.
4. Make the reference to A1 absolute with respect to row, allowing fill-down.

The new formula is:

• =SUMPRODUCT(- -MID(A10,ROW(OFFSET(A$1,,,LEN(A10))),1))

Much prettier, and even not counting curly-braces, two characters shorter. The Knowledge Base goes on to give this as the formula for summing the digits of a negative number:

• =SUM(VALUE(MID(A11,ROW(A2:OFFSET(A2,LEN(A11)-2,0)),1))) also array-entered.

This is the better version, simply entered:

• =SUMPRODUCT(–MID(A11,ROW(OFFSET(A$2,,,LEN(A11)-1)),1))

You have to start the array at 2 (via A$2) to skip the negative sign, and then also shorten the length by one for the same reason. This one is the same length as Microsoft’s. If you want one formula for all numbers, this one has no counterpart in the Knowledge base:

• =SUMPRODUCT(- -MID(ABS(A11),ROW(OFFSET($A$1,,,LEN(ABS(A11)))),1))

It uses the absolute value ABS() function for the obvious reason. It only works for true numbers. It will not handle long text strings as numbers, such as you may have for credit cards or international phone numbers. For those, either use the earlier one, or use SUBSTITUTE(A11,”-”,”") in place of ABS(A11). Now we’re the ones getting getting ugly.

…mrt

Euler Problem 203 asks:

The binomial coefficients ⁿC_k can be arranged in triangular form, Pascal’s triangle, like this:

                        1
                     1     1
                  1     2     1
               1     3     3     1
            1     4     6     4     1
         1     5     10    10    5     1
      1     6     15    20    15    6     1
   1     7     21    35    35    21    7     1
.........

It can be seen that the first eight rows of Pascal’s triangle contain twelve distinct numbers: 1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21 and 35.

A positive integer n is called squarefree if no square of a prime divides n. Of the twelve distinct numbers in the first eight rows of Pascal’s triangle, all except 4 and 20 are squarefree. The sum of the distinct squarefree numbers in the first eight rows is 105.

Find the sum of the distinct squarefree numbers in the first 51 rows of Pascal’s triangle.

Each number inside Pascal’s Triangle is the sum of the two numbers above it. Pascal’s Triangle, traditionally zero-based, can be portrayed in an array, like this:

In this form, each number below row(0) and right of column(0) is the sum of the number diagonally left and above with the number directly above. There is another way to determine each number, which is what Euler’s ⁿC_k notification signifies. Where n is the row, and k is the column, each number is n!/((n-k)!*k!). In the problem statement, the largest n is 50. Therefore the largest prime-squared we have to deal with is 49, and the largest prime is 7. We have no need to investigate higher.

Once we build the 0×50, 0×50 Pascal array, a collection is the perfect tool to collect(duh!) unique entries because you can’t have duplicates; and because of symmetry, we only need look in the left half of the array. Finally, loop through the distinct numbers checking the remainders from the divisions by 2², 3², 5², and 7². If all of them are non-zero, the distinct number is square-free, and add it to the running total to form the answer. Equivalently, as implemented, if any of them are zero, then square-free is false, and don’t add the distinct number.

This is the code that does this. It runs in about 2/100^ths of a second, and builds the “triangle” by addition rather than factorization.

It’s probably overkill to use a sieve for only 4 prime numbers, but it’s a tool the tool box now. I wanted to use “distinctnum(n) mod p*p” but that throws errors for large values of distinctnum(n), so I went with definition of mod instead.

…mrt

Euler Problem 119 asks:

The number 512 is interesting because it is equal to the Base of its digits raised to some power: 5 + 1 + 2 = 8, and 8³ = 512. Another example of a number with this property is 614656 = 28⁴.

We shall define a(n) to be the nth term of this sequence and insist that a number must contain at least two digits to have a Base.

You are given that a(2) = 512 and a(10) = 614656.

Find a(30).

8³ = 512 is the same as log₈(512) = 3, and 28⁴ = 614656 is the same as log₂₈(614656) = 4. If we find numbers that have integral logs in a base equal to the sum of their digits then we have found elements of a(). We only need the first 30.

The VBA Log() function uses natural logs. For those with an engineering bent, it’s like the worksheet LN() function. To get Logs in a different base, the VBA help file reminds us that Log_n(x) = Log(x) / Log(n). With the caution that if the n = 1, then log(n) = 0, and we have a division by zero to guard against.

Here is the code that does this:

Note that I stopped at a(12). That determination takes 20 seconds, and a(n) and a(n+1) are getting farther and farther apart. The method is sound, but the approach isn’t timely.

An alternative is to find lots of numbers to powers, and check to see if they have the requisite base. Doing it that way, the a(n) elements do not arrive in n order, and a sort will be required to pull out a(30). Since I don’t know how many there are in the span of numbers, we’ll add the proper results to a collection, and then sort the collection. (Dick has an article on sorting a collection here. I shamelessly ripped him off.) This is the new code. It runs in a 1/100^th of a second..

The usual angle bracket substitutions are in the above. When you see the answer, you’ll see how bad that first approach really was. At least the answer fits in a variant without loss of precision.

Happy Labor Day!

…mrt

Euler Problem 109 asks:

In the game of darts a player throws three darts at a target board which is split into twenty equal sized sections numbered one to twenty.

The score of a dart is determined by the number of the region that the dart lands in. A dart landing outside the red/green outer ring scores zero. The black and cream regions inside this ring represent single Darts. However, the red/green outer ring and middle ring score double and treble scores respectively.

At the centre of the board are two concentric circles called the bull region, or bulls-eye. The outer bull is worth 25 points and the inner bull is a double, worth 50 points.

There are many variations of rules but in the most popular game the players will begin with a score 301 or 501 and the first player to reduce their running total to zero is a winner. However, it is normal to play a “doubles out” system, which means that the player must land a double (including the double bulls-eye at the centre of the board) on their final dart to win; any other dart that would reduce their running total to one or lower means the score for that set of three darts is “bust”.

When a player is able to finish on their current score it is called a “checkout” and the highest checkout is 170: T20 T20 D25 (two treble 20s and double bull).

There are exactly eleven distinct ways to checkout on a score of 6:

D3
D1 D2
S2 D2
D2 D1
S4 D1
S1 S1 D2
S1 T1 D1
S1 S3 D1
D1 D1 D1
D1 S2 D1
S2 S2 D1

Note that D1 D2 is considered different to D2 D1 as they finish on different doubles. However, the combination S1 T1 D1 is considered the same as T1 S1 D1.

In addition we shall not include misses in considering combinations; for example, D3 is the same as 0 D3 and 0 0 D3.

Incredibly there are 42336 distinct ways of checking out in total.

How many distinct ways can a player checkout with a score less than 100?

If you’ve never “done darts,” this is the hard way to learn the rules. I did darts often in a Scot pub (I was “pretty good for a Yank”–damning with faint praise) so I had a good understanding of the game. A dart board has 20 spokes, worth from 1 to 20 points, an inner hub worth 50 points (the bull’s eye), an outer hub worth 25 points, a midway ring worth triple the spoke score, and an outer rim worth double the spoke score. Very good players countdown from 501, but the pub matches started down from 301. To win, your last dart had to land in the double ring and take you exactly to zero. Too high a value, or a reduction to one, and your turn was wasted.

A good picture of a dart board and the 3-dart “double-outs” is here.

The one tricky thing about this problem was the requirement that “S1 T1 D1 is considered the same as T1 S1 D1.” I couldn’t figure out how to handle that until I decided to not let it happen at all. This is why the middle loop of the 3-dart solutions starts at the same counter as the outer loop.

Here is the code that does the counting. It runs in a blink:

The reason you “go bust” on one is because you can’t double out from there. The usual angle bracket substitutions are in the above.

…mrt

Euler Problem 205 asks:

Peter has nine four-sided (pyramidal) dice, each with faces numbered 1, 2, 3, 4. Colin has six six-sided (cubic) dice, each with faces numbered 1, 2, 3, 4, 5, 6.

Peter and Colin roll their dice and compare totals: the highest total wins. The result is a draw if the totals are equal.

What is the probability that Pyramidal Pete beats Cubic Colin? Give your answer rounded to seven decimal places in the form 0.abcdefg

As a quick review, if we roll 2 of Colin’s dice, we expect 6² different outcomes. Rolling 6 dice will have 6⁶ outcomes, or 46,656 different rolls.

Peter has 4⁹ different outcomes, or 262,144 different rolls. Peter’s least roll (nine 1’s) will best the one way Colin can roll a 6 (six 1’s), the six ways he can roll a 7 (five 1’s and a 2 six times) and the twenty-one ways he can roll an 8 (a 3 and five 1’s six times, or two 2’s and four 1’s fifteen times). Peter’s meager 9 wins over 28 of Colin’s possible rolls. Peter’s 10, which he can roll 9 ways, bests 84 of Colin’s rolls.

VBA does not have a CEILING function, and I needed one for this problem. We could use Application.Worksheetfunction.Ceiling, but there is a quicker way execution-wise by a factor of 5. The INT function always rounds down. When the argument to INT is negative, INT rounds down or away from zero. INT(-3.14159) is -4, and -INT(-3.14159) is 4, rounding pi() up! Very useful when you need more area in your circles. It works this way in both the VBA and the spreadsheet implementations.

Easier than developing the usage for Problem 205, I’ll show it and explain how it works. The code we want to use for Colin is "-INT(-N/6^C) Mod 6" for C from zero to five, where N is the number of the roll (1 to 6⁶), and when Mod 6 = zero, substitute 6. In a spreadsheet, this would be =IF(MOD(-INT(-N/6^C),6), MOD(-INT(-N/6^C),6), 6)

Remembering that 6⁰ is 1, and 6¹ is 6, this is how the first four of Colin’s dice (C=0,1,2,3) look on Roll 66, N = 66, -N = -66.

1. C = 0, Die 1:
• INT(-66/6^0) = INT(-66/1) = -66
• –66 = 66
• 66 Mod 6 = 0, Return 6
2. C = 1, Die 2:
• INT(-66/6^1) = INT(-66/6) = -11
• –11 = 11
• 11 Mod 6 = 5, Return 5
3. C = 2, Die 3:
• INT(-66/6^2) = INT(-66/36) = INT(-1.83333) = -2
• –2 = 2
• 2 Mod 6 = 2, Return 2
4. C = 3, Die 4:
• INT(-66/6^3) = INT(-66/216) = INT(-0.30555) = -1
• –1 = 1
• 1 Mod 6 = 1, Return 1

Dice 5 and 6 (with C of 4 and 5) also return 1. Colin’s 66^th roll is {6,5,2,1,1,1}. We do the same thing for Peter, where the code is "-INT(-N/4^P) Mod 4" for P from zero to eight, returning 4 when Mod 4 is zero. Peter’s 66^th roll is {2,1,1,2,1,1,1,1,1}, summing 11. Peter gets 11 forty-five ways, on which he beats the 210 of Colin’s rolls (but not Colin’s #66) that sum 10 or below.

If we aggregate the number of times Colin sums from 6 to 36 in his 46,656 possible rolls, and the number of times Peter gets a particular sum from 9 to 36 in his 262,144 different rolls, we can then loop through Peter’s aggregation and see how many of Colin’s rolls lose to that number. If we then multiply that discovery by the number of ways Peter achives that aggregation, keep a grand sum of winners, and then divide by the product of (6⁶)*(4⁹),we will have our percentage of Peter’s winning. Format the answer to 7 decimals to the right. Format() will take care of the necessary rounding.

This is the code that does this. It runs in about 6^ths of a second.

If, instead of -INT, I use Application.Worksheetfunction.Ceiling as:

• TEMP = Application.WorksheetFunction.Ceiling(N / 6 ^ C, 1) Mod 6 and
• TEMP = Application.WorksheetFunction.Ceiling(N / 4 ^ P, 1) Mod 4

the runtime is 3.5 seconds! Using ROUNDUP() is even slower. The really wrong way to do this problem is to match each of Peter’s rolls with each of Colin’s, or something like this, where larger PP() and CC() now hold each roll and not the occurrances of each sum.

That’s 12,230,590,464 loops. Been there, did that. Takes 6 and a half minutes. No tee shirt.

…mrt

Euler Problem 76 asks:

It is possible to write five as a sum in exactly six different ways:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

How many different ways can one hundred be written as a sum of at least two positive integers?

This is a Euler Partition problem, one of at least 4 in the problem set (Nos. 31, 77, and 78 are also.) I didn’t now that when I solved #31. I came across Euler partitions as a hint to solving problem #76.

Two things I’ve learned about Project Euler:

1. If Leonhard Euler was involved with it, Project Euler is involved with it, and
2. There’s probably a PhD in a mathematics department somewhere that has a monograph on the topic

Problem 76 is right out of that playbook. The paper Playing with Partitions on the Computer from the mathematics server of Temple University is exactly on point. In fact, if you catch the hint in the document, the answer is right there in the back. No computer required. The authors provide a Section 4, A Basic Program to Generate Partitions.

This is my VBA translation of the authors’ algorithms. The number of partitions for zero, P(0), is defined as 1, there being only one way to take zero, and the number of partitions for any negative number is zero, so when the indexing reaches for a negative partition, we can stop the loop. The partitions for later numbers grow from the partitions of earlier numbers by pentagonal numbers (as F below). That’s what Euler discovered. It’s covered in the reference.

The code names that tune in “zero” notes, err seconds, per the timer.

The usual angle brackets substitutions are in the above. This code, slightly modified, will directly solve #78. You’ll need to make the partition reachback (K) bigger, and look for a different kind of endpoint. The number of partitions corresponding to the answer of #78 is a 257 digit number.

Euler partitions occasionally make the news. They’ll explain them better than I can, for sure.

Now, what I can’t figure out is what to change when the increments are prime numbers (as in #77), rather than unitary. I’d think it should be N, or the Loop step, but I haven’t got it yet.

…mrt

Euler Problem 124 asks:

The radical of n, rad(n), is the product of distinct prime factors of n. For example, 504 = 2³× 3² × 7, so rad(504) = 2 × 3 × 7 = 42.

If we calculate rad(n) for 1 <= n <= 10, then sort them on rad(n), and sorting on n if the radical values are equal, we get:

Unsorted      Sorted
n  rad(n)     n  rad(n)     k
1    1        1    1        1
2    2        2    2        2
3    3        4    2        3
4    2        8    2        4
5    5        3    3        5
6    6        9    3        6
7    7        5    5        7
8    2        6    6        8
9    3        7    7        9
10   10       10   10       10

Let E(k) be the kth element in the sorted n column; for example, E(4) = 8 and E(6) = 9.

If rad(n) is sorted for 1 <= n <= 100000, find E(10000).

This is my 100th solution. Harumpf. All that, and I am yet but a Euler novice!

If you play with the rad() function a bit, a few things become clear: for prime p, rad(p) = p, and for all p, rad(pⁿ) = rad(p). With those rules, you can compute a lot of rad() functions quickly. However, I couldn’t compute the remainder of the 100,000 radicals via the method shown above in Euler time (one minute–If some one can, I’m ready to copy). So I cheated. Here is information about the radical function from “The Online Encyclopedia of Integer Sequences” or OEIS. On that page is a link to the first 100,000 computed radicals in textual format. Perfect! I downloaded that file and saved it as radn.txt. From there, bring it into E(1 to 100000, 1 to 2), sort E on column 2, and then bubble sort around E(10000,2) to get things in proper order at the point of interest. To sort E() I used blogmeister and fellow Eulerian Doug Jenkins’ SortV function. Get that here. It worked fine (Doug has since improved it). The whole routine, including the sort of 100,000 items, took a second and a half.

Here is the code that does it.

E(10000,2) turns out to be a pretty good year…one year after I was born. The usual angle bracket adjustments are used above.

I didn’t want to “cheat” quite that way. What I wanted to do was write code that went out on the web and pulled in the results. I’m row-challenged at 65536, and a Web-query seems to demand a range, not an array. I also couldn’t noodle out how to get past the row limit. I thought Excel might do the query via the clipboard (it does!) but even the clipboard object was truncated at 65,536 lines. I couldn’t come up with a way to populate 100,000×2 elements of an array via the internet, even though VBA doesn’t care. Is there one?

…mrt