project-euler / project-euler / 148 / 148-analysis.txt

We can easily verify that none of the entries in the first seven rows of
Pascal's triangle are divisible by 7:

  	  	  	  	  	  	 1
  	  	  	  	  	 1 	  	 1
  	  	  	  	 1 	  	 2 	  	 1
  	  	  	 1 	  	 3 	  	 3 	  	 1
  	  	 1 	  	 4 	  	 6 	  	 4 	  	 1
  	 1 	  	 5 	  	10 	  	10 	  	 5 	  	 1
1 	  	 6 	  	15 	  	20 	  	15 	  	 6 	  	 1

However, if we check the first one hundred rows, we will find that only 2361 of
the 5050 entries are not divisible by 7.

Find the number of entries which are not divisible by 7 in the first one
billion (109) rows of Pascal's triangle.

-------------------------------

For row n and position k the entry in the pascal triangle is C(n,k) =
n! / (k! * (n-k)!) ==> [(n-k+1) * (n-k+2) * (n-k+3) ... n] / [1 * 2 * 3 ... k]

To count the number of factors of 7 in the C(n,k) we can use the following
formula:

(PI == multiplication)

* T[PI[1..k]] = Int[k/7] + Int[k/49] + Int[k/7**3] + Int[k/7**4]...

* T[PI[n-k+1..n]] = [How many times multiples of 7 appear in (n-k+1 .. n)]
    + [How many times multiples of 49 appear in (n-k+1 .. n)]
    + [How many times multiples of 7**3 appear in (n-k+1 .. n)]



TPI_7[7-1+1..7] = TPI_7[7..7] = 1
TPI_7[7-2+1..7] = TPI_7[6..7] = 1
TPI_7[7-3+1..7] = TPI_7[5..7] = 1

TPI_7[8-1+1..8] = TPI_7[8..8] = 0
TPI_7[8-2+1..8] = TPI_7[7..8] = 1
TPI_7[8-3+1..8] = TPI_7[6..8] = 1

* T[PI[n-k+1..n]] = [How many times multiples of 7 appear in (n-k+1 .. n)]
    = Int[ (k + (7-1) - n%7) / 7]
    + Int[ (k + (7**2-1) - n%(7**2)) / 7**2]
    + Int[ (k + (7**3-1) - n%(7**3)) / 7**3]

For

==============================================

\|[6[1..6] .. 13[1]] = 6*(6+1)/2 Ys ==> 21 Ys.

Triangle[1 .. 49] = (1+2+3+4+5+6) * \|[6*6] = 21*21 Ys = 21**2 Ys = 441 Ys

\|Triangle[50[1 .. 48] .. 98[48]] = (1+48)*48/2 Ys ==> 1176 Ys

Triangle[1 .. 49*7] = Triangle[1 .. 343] = (1+7)*7/2*Triangle[1..49] + (1+6)*6/2 * \|Triangle[50 .. 98] = 
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.