Project Euler #148: Exploring Pascal's triangle.

  • + 1 comment

    I almost solved it in O(1) time. But according to my algo for test case 100,100 no of entries divisible by 7 is 3217. But testcase answer is 5050-2361 = 2869. How I am able to find more no of entries divisible by 7, than actually is.

    Here is my algo......

    8th row (7C1, 7C2, ... 7C6) are all divisible by 7;

    9th row (8C2, 8C3, ... 8C6) are all divisible by 7;

    10th row (9C3, 9C4, ... 9C6) are all divisible by 7;

    11th row (10C4, 10C5, 10C6) are all divisible by 7;

    12th row (11C5, 11C6) are divisible by 7;

    13th row (12C6) is only no. divisible by 7;

    14th row NONE is divisible by 7;

    So I generalise it like this....

    8th row (1 to 6) total 6 entries

    9th row (2 to 6) total 5 entries

    .

    .

    13the row (6) total 1 entries

    Sum of entries divisible by 7 till 14th row is 6+5+4+...+1 = 21;

    Start again with 15th row count entries divisible by 7.

    15th row (1-13) total 13 entries

    16th row (2-13) total 12 entries

    .

    .

    20th row (6-13) total 8 entries

    21th row 0 entries

    Sum it 13+12+...+8 = (7+6)+(7+5)+(7+4)+...+(7+1) = (42 + 21);

    Find Sum again from row 22nd to 28

    For rows(22-28): (42*2 + 21)

    For rows(29-35): (42*3 + 21)

    .

    .

    Actually we can generalise it........

    For rows(1-7): (0);

    For rows(8-14): (42*0 + 21);

    For rows(15-21): (42*1 + 21);

    For rows(22-28): (42*2 + 21);

    For rows(29-35): (42*3 + 21);

    For rows(36-42): (42*4 + 21);

    .

    .

    .

    For rows(92-98): (42*11 + 21);

    For row 99th (98C1, 98C2, ... 98C97) total 97 entries are divisible by 7.

    For row 100th 96 entries are divisible.

    Total will be 3217 entries divisible by 7.

    But in testcase answer it is 5050 - 2361 = 2689.

    Can somebody explain where I am wrong....?

    Please... Thanks...