Project Euler 148 - Exploring Pascal's Triangle

Official link: https://projecteuler.net/problem=148

Thought Process

I used Lucas's Theorem, specifically a corollary of Lucas's Theorem (102) in the following article: https://arxiv.org/pdf/1409.3820.pdf

The theorem states that given a prime, p, and an integer n = np That is n is represented in base p

For example in row 7 = 10 in base 7 therefore there are (1+1)(1+0) = 2 entries in row 7 that are not divisible by 7I actually originally solved this using this alone but my code took over 30 mins to output the correct anwser, then I thought smarter by looking at the pattern produced by the number of entries that are not divisible by 7

The pattern is as follows:

The sum of the first 7 rows is 28, sum of rows 8-14 = 2*28, sum of rows 15-21 = 3*28, therefore the sum of the first 7^2 rows is (1+2+3+4+5+6+7)*28 = 28^2, so we can begin to quickly calculate

As an example I will show you the answer for 5050:

100 = 202 in base 7, therefore

anwser = (1+2) * 28^2 + 3*(0)*28^1 + 3*1*(1+2)*28^0 = 2361

From there we can use the fact that 10^9 = 33531600616 in base 7

Interactive Code

Enter a number (yourinput)

Code will output the number of entries that are not divisible by 7 up till row yourinput