Problem 78:
Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can separated into piles in exactly seven different ways, so p(5)=7.
| OOOOO |
| OOOO O |
| OOO OO |
| OOO O O |
| OO OO O |
| OO O O O |
| O O O O O |
Find the least value of n for which p(n) is divisible by one million.
This problem is one that utilizes an algorithm called "Integer Partitions" (http://en.wikipedia.org/wiki/Partition_(number_theory)). Reading the wikipedia article previously mentioned will give some insight to the logic and algorithmic details that allow you so find the number of ways you can represent the number 5, or in this case, rearrange five coins of equal value in any number of sets.
After getting some idea of the algorithm, you may end up like me in realizing that being able to derive the algorithm itself may lead to a root of insight and understanding but is not necessary to solve problem 78, nor is it the best use of time considering we're interested in the computer programming side of things. The algorithm is denoted as p(n) where n is the "number of coins" so to speak, and the function yields the number of different ways in which n coins can be separated into piles.
Algorithm:
p(n) = p(n – 1) + p(n – 2) – p(n – 5) – p(n – 7) + p(n – 12) + p(n – 15) – p(n – 22)…
where p(0) = 1 and p(n) = 0 for n < 0.
Interestingly enough, we have a mishmash of technicalities within this equation. First off, each term contains the variable n, and has a certain number being subtracted from it (1,2,5,7,12,15,22 ... etc). These numbers are created from an algorithm based on their placement in the initial equation of p(n). These numbers in particular are called "Pentagonal Numbers" . You can wikipedia an explanation of the algorithm for these certain types of numbers but I will list them here:
Pentagonal Number Algorithm:
f(k)= (3k^2 - k)/2
So f(0) will yield 1, f(1) will yield 2, etc. But if you actually plug in 0 and 1, you will not get these yielded numbers. This is because there is yet another algorithm that yields the value of k for iteration variable i.
K Algorithm:
f(m)=
if m is even:
m//2 + 1
if m is odd:
-m//2 - 1
Notice that in this algorithm, m is not just being divided by 2, but also being "floored". Assuming those reading this solution are familiar with computer science, floor simply means to round down a decimal number thus changing the decimal portion to 0 at all times.
Okay so now we have three algorithms, all that's left is to use them in the appropriate order!
1) Find your k value using your iterative variable i
2) Find your pentagonal value using the previously solved for, k
3) Plug your pentagonal value into the first equation, p(n)
4) Solve for p(n)
**Quick note, in the equation p(n), the terms are in sequence of ++--++--++--... etc. This is a rather straightfoward pattern but cannot be overlooked.
After reading the quick note, it should be understood that due to the inconsistency of addition or subtraction, the use of recursion to solve this problem is an almost immediate response but proven challenging and what I found to be impossible. This would mean we have to create some sort of looping structure, that solves an equation that continuously calls itself unless it encounters a value of 1 or below.
I've developed a solution for this algorithm in Python, I will list the code below as well as provide an explanation for how it works. There are other algorithms on the internet, but I found that when I researched this problem, I did not understand any of them, so I hope my explanation is an easier rendition of others you may have read.
My Algorithm:
The first two functions pentagonal() and gp() are directly copied from the Python pseuodocode listed at the bottom of the page of article: http://en.wikipedia.org/wiki/Pentagonal_number_theorem.
The main procedure p() is created by me in order to suit the needs of the problem. Lets start from the top shall we.
Logic:
We are going to create a list (f[]) that will hold all p(n) solutions from when n=0. At first this may seem inefficient because all we care about is the value of p(n) which yields 0 when modulo'd by 1000000. But after trying recursion and failing, I've realized that a bottom up approach is much better suited. What this means is that if you start from the bottom (p(0)) this yields an immediate answer of 1. Then you solve for p(1) which calls for p(0) which yields 1, meaning p(1)=1. Then you solve for p(2) which calls p(1) and p(0). This essentially ends up looking like the following diagram:
As we can see, if we keep a list of all the previously found p(n) values, we can call them up as we need them as opposed to
a) resolving for them
b) thinking in terms of recursion from starting at the top, gong to the bottom, and then collecting values from the bottom going back up.
This way we simply start at the bottom, keep adding values to the array which act not only as potential answers, but building blocks for other answers.
p(3) = p(2) + p(1). Both p(2) and p(1) would've already been found, making the answer for p(3) to simply be the previous two answers added together, and appended to the list!
Assuming that you now understand the logic of my program, you can do one of three options.
1) Continue reading to hear the explanation of my code.
2) Go and do it yourself with some background knowledge of my logic and not come back.
3) Go and try it yourself, if you get stuck, feel free to come back to this post and continue reading my code explanation and then give another crack at it!
Code Explanation:
First we initialized a variable n=1. This acts as p(1). The reason we start from p(1) instead of p(0) is because we initialize our p(n) array (f) to be equal to 1 (which is the result of p(0)). We have a varialbe called count which is equal to 0, this is going to act as our "iterative variable" i mentioned previously. t is going to be our "k" value, but we name it t because i used the variable id "k" for an array that holds all the "k" values for the given "n" value. The previous sentence may sound very confusing, it simply means the array k will hold all k values respective to the variable n until k is a negative number in which we will stop building the array.
Second we enter the main while look that runs "forever" until we find our answer of n%1000000==0. The second while loop is to build up our array of k. The way this works is that while the value "t" is positive, we will append the k-list of all the k values respective to n.
Thirdly we initialize more variables! r will be our current p(n) value (aka. the p(n) we append to our list of f). c is a counter variable because I used a list iterator as opposed to a variable iteration. c simply keeps count of what index I am currently in with respect to k[] value i.
Fourthly we enter the for loop which increments c as it should, then enters an if-statement.
if (c//2%2==0):
This is checking for whether or not we should be adding or subtracting. Remember previously in this post I mentioned a pattern of ++--++--..etc, well this is how we check where we are in that sequence. c//2 returns a number that will be the same for two consecutive numbers. Example: 0//2 = 0, 1//2 = 0, 2//2 = 1, 3//2=1. See how 0 and 1 are consecutive, but both yield 0, and 2 and 3 are consecutive and both yield 1? I then take this number that should be the same and modulus it by 2 in order to check if it's even or odd. Basically if it's even i will add, and if it's odd then i will subtract. This more or less means do this every second time, so if you want a pattern of +-+-+-...etc you would just do c%2, but since I need it to repeat each operator twice I need the same value twice which is why I use the c//2 to give me the same result for two consecutive values of c.
After I determine whether or not to add or subtract (such a trivial question, yet a long explanation), I perform the algorithm of adding f[n-i]. What does this mean exactly? Remember that i represents a value of "k" and n represents n. This essentially looks like p(n-k) from the formula!!! Therefore;
f[n-i]=f(n-k)
Fifthly, we append the solution of r or in other words p(n) to our array of f[].
Sixthly we check if the value we just entered as p(n)%1000000==0 because that is the purpose of the problem. When that if statement returns true, we return the value of n respective to p(n)%1000000==0.
This concludes my explanation of Project Euler's Problem 78. I hope that you understand the problem, and if you have any further questions or perhaps optimizations to my algorithm please feel free to comment below or PM me.
Thank you!
No comments:
Post a Comment