Pascal’s Triangle
I often solve some problems in the intervals between my study. Today, I chose a problem with Pascal’s triangle from Project Euler. Pascal’s triangle is a triangle that is created by the simple rules, such as following:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
And the problem demanded the number of entries which are not divisible by 7 in the first one billion rows of Pascal’s triangle. The number of elements that I have to check is about 500 quadrillion (5 times 10 to the 17th power).
I wrote a simple program code which calculates Pascal’s triangle made of residue of 7 (modularized by 7?). However, this program took about 30 seconds to check 5 billion elements in my computer. This means it will take 95 years to solve this problem. I think there is a smart analytical solution because there are too many elements to solve using dynamic programming. I couldn’t solve this problem today, but I like such a problem that remind me of the splendor of algorithms.
