Euler Problem 66 asks:

Consider quadratic Diophantine equations of the form:

x^2 – Dy^2 = 1

For example, when D=13, the minimal solution in x is 649^2 – 13*180^2 = 1.

It can be assumed that there are no solutions in positive integers when D is square.

By finding minimal solutions in x for D = {2, 3, 5, 6, 7}, we obtain the following:

3^2 – 2*2^2 = 1
2^2 – 3*1^2 = 1
9^2 – 5*4^2 = 1
5^2 – 6*2^2 = 1
8^2 – 7*3^2 = 1

Hence, by considering minimal solutions in x for D<=7, the largest x is obtained when D=5.

Find the value of D<=1000 in minimal solutions of x for which the largest value of x is obtained.

If you rearrange x^2 – D*y^2 = 1 to D = (x^2 – 1)/y^2, the square root of D is nearly proportional to x/y. This square root ratio can be determined by continued fractions, and as long as D is not a perfect square, has an infinte number of ratios that are solutions. Fortunately, Euler only asks for the first one. The algorithm to do this is described at http://mathworld.wolfram.com/PellEquation.html. Unfortunately, the author wasn’t wasn’t wearing a programmer’s cap when writing, and the equations had to be rearranged. Here is my code that implements Pell’s equation. There’s not much to see in the main routine–just looking for the maximum x and picking off its index. The heavy lifting is in the PellSoln() function. PellSoln() returns an {x,y} pair (Euler only asked for the D associated with the maximum x.) and optionally will return the n-th higher order solution. It’s annotated to the appropriate MathWorld equation. You can see there was some re-ordering. The code runs in a blink.

Every Diophantine equation has the the “trivial solution” of {1,0}, and so PellSoln() turns trivial if D is a perfect square. The usual accommodations are made for angle brackets. Pell’s equation is big in number theory. I don’t expect to have a use for it again. ;-)

Is there a better way to return a 1×2 array?

…mrt

Euler Problem 75 asks:

It turns out that 12 cm is the smallest length of wire that can be bent to form an integer sided right angle triangle in exactly one way, but there are many more examples.

12 cm: (3,4,5)
24 cm: (6,8,10)
30 cm: (5,12,13)
36 cm: (9,12,15)
40 cm: (8,15,17)
48 cm: (12,16,20)

In contrast, some lengths of wire, like 20 cm, cannot be bent to form an integer sided right angle triangle, and other lengths allow more than one solution to be found; for example, using 120 cm it is possible to form exactly three different integer sided right angle triangles.

120 cm: (30,40,50), (20,48,52), (24,45,51)

Given that L is the length of the wire, for how many values of L <= 2,000,000 can exactly one integer sided right angle triangle be formed?

Everything discussed here can be found at http://en.wikipedia.org/wiki/Pythagorean_triple

Integer Pythagorean Triples (keep [3,4,5] in mind–it’s the first example of one) are values that form right triangles. Triples that are not multiples of other triples are called primitive. [3,4,5] is the first integer triple, and it’s obviously primitive. [6,8,10] is a triple, but as a 2x multiple of [3,4,5], it is not primitive. Similarly for [9,12,15].

Using Euclid’s formula (upcoming), integer primitive triples can be computed from a pair of numbers m and n with the following properties:

• m greater than or equal to 2
• n less than m
• n and m of opposite parity
• m and n are relatively prime (GCD = 1)

With this understanding then, Euclid found Side a is m^2 – n^2. Side b is 2*m*n and Side c is m^2 + n^2. For [3,4,5], m = 2 and n = 1.

• 3 = 2^2 – 1^2
• 4 = 2*2*1
• 5 = 2^2 + 1^2

If you add (m^2 + n^2) + (2*m*n) + (m^2 – n^2) to get the perimeter, it simplifies to 2*m*(m + n).

The [3,4,5] triangle’s perimeter is

• 3 + 4 + 5 = 12 = 2*2*(2 +1)

and 12 is the minimum value for any integer triple.

Some things fall out from the above properties.

• With a value of 2*m*(m + n) , all right triangle perimeters are even.
• For a primitive triangle, one side is even, and the other two are odd (to add to an even)
• For a primitive triangle, Side c is always odd
• For multiples, either one side is even, with the other two are odd, or they are all even.
• And since area = 1/2 * a * b, and b is even, the area of an integer right triangle is always a whole number.

Euler asks us for perimeters less or equal to 2,000,000. We can use that to find some bounds on c and m. For all triangles, one way is: a + b > c. Then a + b + c > c + c. 2000000>= a + b +c means 2000000 > 2*c, and 1000000 > c. Take c = m^2 +n^2 = 1000000, then for n = 1, m^2 + 1 = 1000000 and m is approximately the square root of 10^6, or 10^3.

Alternatively, if 2*m*(m + n) = 2000000, then m*(m + n) = 1000000. For n = 1, m^2 + 1 = 1000000, and we are at the same place.

We can build loops with m = 2 to Sqr(1000000) and n = 1 + (m mod 2) to m – 1 step 2 (for opposite parity) to build all primitives. If we multiply the primitive perimeter P by an incrementing K until K*P is greater than 2,000,000, and increment the appropriate counter L(K*P) by 1 for each case, we have accounted for and binned all the perimeters. Loop through L() from 12 to 2000000 Step 2, and tally the L(k) equal to 1.

Here is the code that does all that, with the GCD2 function. It runs in about eight-tenths of a second, and also reports out the number of primitives (PPT).

When I first wrote the code I included a test (commented out above) for “right-triangle-ness” using precomputed squares up to 1000000^2. This test used currency variables to hold 10^12. The final loop used a currency-type counter to total cases of L(P) = 1. That loop never went above 1717986, and the wrong answer from a right method resulted. That was fixed by using k, a long. See the Code Snipit thread. That right-angled test was never failed, or Euclid’s formula would have failed, and yours truly would be in wikipedia with a dissertation topic ;-). It’d only take one example for fame and glory, but it’s just not needed. But then I wouldn’t have found the bug. Some irony, I suppose.

All the currency types can be changed to longs, and if you use the alternative calculation for P, a and b need not be computed. Though this isn’t how I did them, this also applies to Problems 9 and 39. There are the usual angle bracket adjustments.

…mrt

Euler Problem 73 asks:

Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d <= 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that there are 3 fractions between 1/3 and 1/2.

How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d <= 10,000?

Here is my code. It uses the same GCD2() function as Problem 75. Takes about 7 seconds.

Mike W…hope this helps. It has the usual angle bracket substitutions.

…mrt

All –

Could some exceedingly kind wizard please run this very simple code snipit, and then explain it (the results) to me? Repeatable on my home machine and work machine running XL2002. On my Mac XL2004, I don’t have this problem.

For P, I get 1717988 (???????)
For K, I get 2000002

And, well, I don’t get what I get ;-)

…mrt

Euler Problem 36 asks:

A palindrome reads the same left-to-right as right-to-left. Examples are “Able was I ere I saw Elba” and “A man, a plan, a canal. Panama”, and for Euler-purposes, 585. Project Euler, when discussing hints, says to read the details of the problem carefully. In this problem, there is a big hint.

Not including leading zeros means no ending zeros. In base 10, then there are no palindromic even multiples of ten. In base 2, there are no palindromic evens at all.

Here is my code. It runs in a few tenths of a second.

It takes the decimal number as a string and reverses it. If they are equal, then they are palindromic. For these cases, it turns the decimal via LongToBit04() into a 32-bit binary, strips the leading zeros, and reverses that. Again if equal, it adds to the running sum.

The LongToBit04() function comes from the people over at VBSPEED, “The Visual Basic Performance Site” at http://www.xbeat.net/vbspeed/. Over there they rack and stack algorithms for dozens of purposes. They score 10 different longs-to-bits schemes, for instance, and #4 isn’t even the fastest. The site doesn’t seem to be as active as it once was, but it’s a great resource still.

…mrt

Euler Problem 79 asks:

The only reason you need a computer for this problem is to download keylog.txt. I opened keylog.txt to get a grasp of what kind of code to write, and in about a dozen lines of sliding numbers around, had solved it. There is positional consistency from character to character, and from one login attempt to the next. The next 38 lines were just looking for a surprise that didn’t come.

Having solved it, I did want to write code that implemented the algorithm my eye had so readily seen. That was harder. I wanted to use a collection again, because its Add and Remove methods readily accommodate re-arranging data. What collections don’t seem to have is a property that indicates where an item is in the collection (or if it’s there I couldn’t find it. My surmise is that collections are linked lists.) To address this, my first thought was to make a collection of a user-defined type that would have an index field. Though the XL help implies that you can make a collection of almost anything, user-defined types seem to be one of those things that’s on the wrong side of “almost.”

I ended up using an INDEX() array in parallel to the collection and doing my own bookkeeping. This is the code. It runs in what the timer reports out as zero seconds. There are probably better ways to do this bookkeeping, but Remove is done by index, and this is the way that occurred to me. The approach is that if an item is earlier in the PassCode collection that it is in the login attmept, to remove it from the PassCode and then add it back after the item in the attempt.

The usual substitutions are made for angle brackets. Is there a better way to index a collection? This way will get messy for collections of any appreciable size.
…mrt

Euler Problem 45 asks:

If we rearrange the Pentagonal formula, we can get P(n)=n(3n-1)/2 as

• 1.5*n^2 – 0.5n – P(n) = 0 with -P(n) = -T(n).

Similarly for the Hexagonal formula, we can get H(n)=n(2n-1) as

• 2*n^2 – 1*n – H(n) = 0 with -H(n) = -T(n).

Flashing back to high school algebra, all we need to do is determine the roots of those quadratic equations (Remember minus b plus or minus the square root of b squared minus 4ac, all over 2a?) If the two equations have integer roots, then we have found a number that is Triangular, Pentagonal, and Hexagonal. Here is my code. It tests for for pentagonal roots first, and only those that pass are tested for hexagonal roots. I didn’t know how far to test, so I picked to 100,000.

It runs in a few hundredths of a second.

…mrt

Euler Problem 23 asks:

The approach seems simple:

1. Determine the list of abundant numbers and add to a collection
2. Determine the list of all abundant number sums and add it to a different collection
3. Run the list of numbers past the second collection to identify those not in the collection, and sum

Usually, I’ll count the number of something, re-dim a variable to that count, and then stuff the variable. But since I have to calculate “abundantness” to determine membership, we’ll just add it to the collection in the same step, and have the collection report the count.

Unfortunately, collections only provide for add, remove, retrieve, and count. There is not a “belongs” or “ismember” function. A smart guy (Mark Nold) over in StackOverflow provided a way, using errors. Here is his code:

I use his method twice to, first, see if an abundant number sum is already in the collection of AbundantSums, and then secondly to see which of the numbers in the range to 28123 is not in the AbundantSums collection.

That’s how I did it. My problem is that, to coin a new unit of measurement, the calculations take a kilo-second, or almost 18 minutes, to arrive at the answer. The first and last steps are very fast. It’s the middle one that takes 1000 seconds. Euler won’t mind, I think, if I say there are 6965 abundant numbers in the range. To compute all possible abundant number sums is 6965*6965 cycles, or very close to 49 million loops. I don’t see the trick to get this down to one-minute Euler time, and I couldn’t pick out the shortcut in the commentary of those who already solved this problem. Here’s my code, with timing comments for each of the steps.

The IsAbundant function only has to check to the square root of a number. If num mod i = 0 you have also determined that num/i is a factor at the same time, and both can be added to the sum of factors. The only rub is when num is a perfect square (when i = sqr(num) = num/i) and you have added that factor twice. Rather than put some logic inside the loop, I checked if that was the case, and subtracted one square root when required.

Only partial credit for this one. It takes too dang long. Please comment on what I’ve missed. The Prime Glossary (http://primes.utm.edu/glossary/page.php?sort=AbundantNumber) reports that the real limit is 20161. While several solvers knew that, I don’t think that’s the problem–gets me down to about 400 seconds. To make the change, just change the constant at the top.

…mrt