Euler Problem 31 states:

‘In England the currency is made up of pound, £, and pence, p, and there are

‘eight coins in general circulation:

‘

‘ 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

‘

‘It is possible to make £2 in the following way:

‘

‘ 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

‘

‘How many different ways can £2 be made using any number of coins?

‘eight coins in general circulation:

‘

‘ 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

‘

‘It is possible to make £2 in the following way:

‘

‘ 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

‘

‘How many different ways can £2 be made using any number of coins?

Over in the Euler Problem 16 thread, dbb provided his answer. This is dbb’s code, copied from there, with 8 loops for eight coins:

Sub P31()

Dim P1 As Long, P2 As Long, P5 As Long, P10 As Long, P20 As Long

Dim P50 As Long, P100 As Long, P200 As Long

Dim n1 As Long, n2 As Long, n5 As Long, n10 As Long, n20 As Long

Dim n50 As Long, n100 As Long, n200 As Long

Dim n As Long

For P1 = 0 To 200 Step 1

n1 = P1

For P2 = 0 To 200 – n1 Step 2

n2 = n1 + P2

For P5 = 0 To 200 – n2 Step 5

n5 = n2 + P5

For P10 = 0 To 200 – n5 Step 10

n10 = n5 + P10

For P20 = 0 To 200 – n10 Step 20

n20 = n10 + P20

For P50 = 0 To 200 – n20 Step 50

n50 = n20 + P50

For P100 = 0 To 200 – n50 Step 100

n100 = n50 + P100

For P200 = 0 To 200 – n100 Step 200

If n100 + P200 = 200 Then

n = n + 1

End If

Next P200

Next P100

Next P50

Next P20

Next P10

Next P5

Next P2

Next P1

Debug.Print n

End Sub

Dim P1 As Long, P2 As Long, P5 As Long, P10 As Long, P20 As Long

Dim P50 As Long, P100 As Long, P200 As Long

Dim n1 As Long, n2 As Long, n5 As Long, n10 As Long, n20 As Long

Dim n50 As Long, n100 As Long, n200 As Long

Dim n As Long

For P1 = 0 To 200 Step 1

n1 = P1

For P2 = 0 To 200 – n1 Step 2

n2 = n1 + P2

For P5 = 0 To 200 – n2 Step 5

n5 = n2 + P5

For P10 = 0 To 200 – n5 Step 10

n10 = n5 + P10

For P20 = 0 To 200 – n10 Step 20

n20 = n10 + P20

For P50 = 0 To 200 – n20 Step 50

n50 = n20 + P50

For P100 = 0 To 200 – n50 Step 100

n100 = n50 + P100

For P200 = 0 To 200 – n100 Step 200

If n100 + P200 = 200 Then

n = n + 1

End If

Next P200

Next P100

Next P50

Next P20

Next P10

Next P5

Next P2

Next P1

Debug.Print n

End Sub

It runs in a second and a half on my machine. Problem 76 looks very similar.

‘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?

‘

‘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?

Does that mean 100 loops are required?

…mrt

Hi Dick – is there a limit to the extent of a potential post that can be previewed. I have Problem 55 in draft that continually gets truncated at the same spot, and I’ve lost all track of what might be below ;-) if anything?

Happy New Year to All.

…Michael

Iteration will solve problem 76, taking nearly 9 minutes, but VBA is not the quickest. Essentially the code below starts with a number (running backwards from 100 to 1 for no particular reason) and finds all the sequences of that number or smaller numbers that make up 100.

`Sub P76()`

Dim m As Long

fP76 100, 0, m

Debug.Print m - 1

End Sub

'n = number currently being added

'S = total sum so far

'm = number of solutions

Sub fP76(ByVal n As Long, ByVal S As Long, ByRef m As Long)

Dim i As Long

Dim t As Long

For i = n To 1 Step -1

t = S + i

'tell you when it has a new starting number

If S = 0 Then Debug.Print i; m

Select Case t

Case Is

Sorry, my first response got truncated, here is the rest of my code

If S = 0 Then Debug.Print i; m

Select Case t

Case Is

aha, I think I figured out the problem both Michael and I are having. The comment editor truncates everything after a “less than” symbol because it thinks it’s an HTML tag

Here is my full code with a text substitute for the “less than” sign

Sub P76()

Dim m As Long

Dim t As Single

t = Timer

fP76 100, 0, m

Debug.Print m – 1, (Timer – t) / 60

End Sub

Sub fP76(ByVal n As Long, ByVal S As Long, ByRef m As Long)

Dim i As Long

Dim t As Long

For i = n To 1 Step -1

t = S + i

If S = 0 Then Debug.Print i; m

Select Case t

Case Is LESSTHAN 100

fP76 i, t, m

Case 100

m = m + 1

End Select

Next i

End Sub

No limit, as far as I know. I can’t imagine what’s cutting it off. Can you send me the text of the post in an email?

Use a recursive approach for both Euler 31 and Euler 76 — they are nearly the same problem!

A recursive approach can be easily generalized to search for a target T with N possible ‘buckets’ whereas a nested loops approach requires a code change whenever N changes. For example, how many ways can you come up with $250 using bills / coins of denomination 100, 50, 20, 10, 5, 2, 1, 50c, 25, 10, 5, and 1? With a recursive approach, only the input data set would change.

The recursive code for 31 should be easily adaptable to 76! Just use 99 buckets, 1, 2, …, 99. The big difference is that we must use at least 2 buckets in 76 whereas in 31 a single bucket is acceptable.

It should not be very difficult to generalize the VBA code at

Find a set of amounts that match a target value

http://www.tushar-mehta.com/excel/templates/match_values/index.html

The only difference between the code on that page and the requirement for 31 is that the code imposes an implicit restriction that each bucket (value) be used only once. For 31 each value can be used as often as required. But, that should be a trivial change to the code. I’ll try it tomorrow and share the results. Adapting the code for 31 to 76 will require some additional work. But that too should not be too difficult. Hopefully, I will not have to eat my claim that the recursive approach requires a trivial change. {grin}

Hi Dick –

Email on it’s way from my work address. dbb may be right.

…mrt (Happy New Year to all!)

OK. The recursive solution to Euler 31 based on the template I’d mentioned in my last comment is now on my website. Visit http://www.tushar-mehta.com/misc_tutorials/project_euler/euler031.html

I’ve tried a recursive routine which is more elegant & versatile. But for Project Euler we want speed… and recursive routines take too much ticks on the stack.

Thus nesting: start with the largest coin, then try to fill the (declining) remaining balance.

Dim t!: t = Timer

Dim p002&, p005&, p010&, p020&, p050&, p100&, p200&

Dim n002&, n005&, n010&, n020&, n050&, n100&, n200&

Dim amnt&, rslt&

amnt = 200

For p200 = 0 To amnt Step 200: n200 = amnt – p200

For p100 = 0 To n200 Step 100: n100 = n200 – p100

For p050 = 0 To n100 Step 50: n050 = n100 – p050

For p020 = 0 To n050 Step 20: n020 = n050 – p020

For p010 = 0 To n020 Step 10: n010 = n020 – p010

For p005 = 0 To n010 Step 5: n005 = n010 – p005

For p002 = 0 To n005 Step 2: rslt = rslt + 1

Next: Next: Next: Next: Next: Next: Next

Debug.Print amnt; rslt; Timer – t

End Sub

One way is big-endian (so to speak) and the other little-endian. Does is matter?

…mrt

Recursion: see Recursion

(don’t remember where I saw this)

keepITcool: You might want to try the recursive approach rather than simply concluding that the performance is unacceptable because it is recursive.

“But for Project Euler we want speed…”

I think different people want different things. Looking at the comments it seems that a lot of people are keen to write the most elegant or the shortest code they can. For me the point is to come up with the code that gives the correct answer (within the program run time constraint) in the shortest possible time spent working on it. In other words if I can reduce the solution time from 59 seconds to 1 microsecond with less than 58 seconds worth of coding, that’s worth doing, otherwise it isn’t and I’ll move onto something else. The only proviso is that if the code is re-useable (either in Project Euler or elsewhere) then it’s worth spending some time optimising it.