Pascal's triangle expression not resulting in correct output

Question

I am looking for help with some code I have written for Project Euler Problem 148.

The problem is as follows:

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

I am aware that this specific method will not work as it will - when ran with 1000000000 - result in an overflow error.

Regardless, I am curious why this code does not work:

I use the expression ((math.factorial(r))/((math.factorial(t))*(math.factorial((r-t))))) to find the value of the term at the given row and term, as shown by the formula:

When numrows == 7, the script should print 0, which it does.

When numrows == 100, the script should print 2361, but my code prints 3139.

The code is as follows:

import math

numrows = 100
count = 0

for r in range(numrows):
  for t in range(r):
    if not (((math.factorial(r))/((math.factorial(t))*(math.factorial((r-t))))) % 7 == 0):
      count += 1
print(count)

Are you sure the formula is correct? This might be a better question for Mathematics. — Barmar
– Barmar, Commented Nov 21, 2019 at 18:44
Also, the values of t go from 0 to r, and you only go up to (r-1). This way, you miss one value on each row (and as they all are 1, they should be counted.) — Thierry Lathuille
– Thierry Lathuille, Commented Nov 21, 2019 at 18:48

Prune · Accepted Answer · 2019-11-21 19:00:25Z

2

You incorrectly implemented the formula, using float division / instead of integer division '//'. With the change to

    if not math.factorial(r)//(math.factorial(t)*math.factorial(r-t)) % 7 == 0:

You get the output 2261. (Yes, I removed the superfluous parentheses.)

With small numbers, you get exact results in floating-point arithmetic, so your modulus operation yields the desired result. However, when you get up to the lower rows, you run into the limits of floating-point precision -- the result of the division won't be exactly blahblah.0, and your == 0 comparison fails. Thus, you count quite a few cells that aren't supposed to match your criterion.

Finally, add Thierry's repair:

for t in range(r+1):

... and you get 2361, as desired.

Note that this nested loop will not solve the problem in reasonable time. You need to attack this with an analysis of divisibility: how many factors of 7 do you have in the numerator and denominator? If the numerator has more, then the result is divisible by 7.

Use the truncated quotient of r / 7^n for n from 1 to r log 7. Do the same for t and t-r. You can also adjust a running count of 7s as you iterate over the needed values.

edited Nov 21, 2019 at 19:00

answered Nov 21, 2019 at 18:47

Prune

78k14 gold badges63 silver badges83 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Thierry Lathuille Over a year ago

There are still 100 missing values, see my comment on the question.

Prune Over a year ago

@ThierryLathuille: right; you got to that repair before I did.

Collectives™ on Stack Overflow

Pascal's triangle expression not resulting in correct output

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related