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:

Visual Basic

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

1 2 3 4 5 6 7 8 9 10 11 12

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

Euler Problem 112 asks:

Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 134468.

Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, 66420.

We shall call a positive integer that is neither increasing nor decreasing a “bouncy” number; for example, 155349.

Clearly there cannot be any bouncy numbers below one-hundred, but just over half of the numbers below one-thousand (525) are bouncy. In fact, the least number for which the proportion of bouncy numbers first reaches 50% is 538.

Surprisingly, bouncy numbers become more and more common and by the time we reach 21780 the proportion of bouncy numbers is equal to 90%.

Find the least number for which the proportion of bouncy numbers is exactly 99%.

Looking at the three examples, adjacent digits can be equal and not disqualifying in any of the cases. This means that a number such as 222222 is both increasing and decreasing. Semantically, while this is nonsense, it’s clear that 222222 cannot be bouncy. Using this observation does give us a way of breaking out of a loop without having to check every digit. If the count of the increasing digits (I) equals the counter, or the count of decreasing digits (D) equals the counter, than the number cannot be bouncy. Similarly, if they are ever both less than the counter, the number must be bouncy, and break the loop.

We’ll start with the Answer as 21780, bouncy number B as 0.9*Answer and keep going until B/Answer is 0.99.

Here is the code that does that. It runs in 3.5 seconds on my new hot rod, a 3Ghz dual core tech refresh. My fastest machine is now the office PC.

The usual angle bracket substitutions are in the above. This is me solving a number problem by strings once again. There must be a better insight. Problem 113 wants the number of non-bouncy numbers below a Googol (10¹⁰⁰). Going this way, working with strings, my hot rod might be calculating for a week.

…mrt (thinking Googol looks funny spelled that way)

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.

Visual Basic

<font color="red">131</font> 673 <font color="red">234 103 18</font> <font color="red">201 96 342</font> 965 <font color="red">150</font> 630 803 746 <font color="red">422 111</font> 537 699 497 <font color="red">121</font> 956 805 732 524 <font color="red">37 331</font>

1 2 3 4 5

<font color="red">131</font> 673 <font color="red">234 103 18</font> <font color="red">201 96  342</font> 965 <font color="red">150</font> 630 803 746 <font color="red">422 111</font> 537 699 497 <font color="red">121</font> 956 805 732 524 <font color="red">37  331</font>

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:

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.

Visual Basic

<font color="red">131</font> 673 234 103 18 <font color="red">201 96 342</font> 965 150 630 803 <font color="red">746 422</font> 111 537 699 497 <font color="red">121</font> 956 805 732 524 <font color="red">37 331</font>

1 2 3 4 5

<font color="red">131</font>   673   234   103   18 <font color="red">201   96    342</font>   965   150 630   803   <font color="red">746   422</font>   111 537   699   497   <font color="red">121</font>   956 805   732   524   <font color="red">37    331</font>

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.

Visual Basic

<font color="red">131</font> 673 <font color="red">234 103 18</font> <font color="red">201 96 342</font> 965 <font color="red">150</font> 630 803 746 <font color="red">422 111</font> 537 699 497 <font color="red">121</font> 956 805 732 524 <font color="red">37 331</font>

1 2 3 4 5

<font color="red">131</font> 673 <font color="red">234 103 18</font> <font color="red">201 96  342</font> 965 <font color="red">150</font> 630 803 746 <font color="red">422 111</font> 537 699 497 <font color="red">121</font> 956 805 732 524 <font color="red">37  331</font>

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