【No. 0044】Pascal's Triangle
Jan 31, 2015 23:32
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
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.
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.
Corrections (2)
No. 1 Timmy
- I often solve some problems in the intervals between my study.
- I often solve some problems (or: mathematical puzzles) in the intervals between my study (or: studies).
- I couldn't solve this problem today, but I like such a problem that remind me of the splendor of algorithms.
- I couldn't solve this problem today, but I like such problems that remind me of the splendor of algorithms.
Interesting!
Toru
Thank you so much always for your correction! :D
Thank you so much always for your correction! :D
Timmy
You are welcome!
You are welcome!
No. 2 thethinker83
- Today, I chose a problem with Pascal's triangle from Project Euler.
- This sentence is perfect! No correction needed!
- Pascal's triangle is a triangle that is created by the simple rules, such as following:
- Pascal's triangle is a triangle that is created by the simple rules, such as the following:
- And the problem demanded the number of entries which are not divisible by 7 in the first one billion rows of Pascal's triangle.
-
And the problem demanded the number of entries which are not divisible by 7 in the first one billion rows of Pascal's triangle.
You can also use "asked for" instead of "demanded" here
- The number of elements that I have to check is about 500 quadrillion (5 times 10 to the 17th power).
- This sentence is perfect! No correction needed!
- I wrote a simple program code which calculates Pascal's triangle made of residue of 7 (modularized by 7?).
-
I wrote a simple program code which calculates Pascal's triangle made of residue of 7 (modularized by 7?).
I would use "modularized by 7" or just "modulo 7".
- However, this program took about 30 seconds to check 5 billion elements in my computer.
- This sentence is perfect! No correction needed!
- This means it will take 95 years to solve this problem.
- This sentence is perfect! No correction needed!
- I think there is a smart analytical solution because there are too many elements to solve using dynamic programming.
- This sentence is perfect! No correction needed!
This was very interesting and very well written. I wish I had a better idea how to solve this problem.
Toru
Thank you very much for correcting me! :)
Your comments were very encouraging for me. I will try to solve this problem during my free time. :D
Thank you very much for correcting me! :)
Your comments were very encouraging for me. I will try to solve this problem during my free time. :D