# Project Euler #203: Squarefree Binomial Coefficients

# Project Euler #203: Squarefree Binomial Coefficients

janos_jung + 2 comments Without spoiling the challange, could somebody plz answer me how the following criterion is meant:

"Find the sum of the distinct squarefree numbers in the first rows of Pascal's triangle."

The question asks for the sum of

*distinct*squarefree numbers. QUESTION: Does this mean the sum of all the numbers witch have distinct mod (10E9+7)? I mean in the binomial table with millions of large numbers, I dont see, why two distinct numbers couldnt have the same modulo 10E9+7. How to account for those numbers?kmcshane + 1 comment The problem only requires that the sum should be expressed mod 10e7. Some distinct coefficients, I assume, can have the same modulo, but that is irrelevant.

janos_jung + 1 comment Since value of the coefficients grow exponentially, after a few dozen of rows, even int64 wont be enough to store a single coefficient. Hence

*if*using modulo arithmetic (mod E9+7) through all the coefficient calculations is a valid solution, I see no way around it. So after a few rows no actual coefficient is evaluated only its modE9+7 modulo.Now my problem is, that I must keep somehow track of the distinct (==not equal) coefficients. Tracking all the coefficients is undoable, (besides potentially being too many of them) since by using modulo arithmetic all the way long I can not get the actual coefficient only its mod (E9+7). Which may (or may not??) collide between to distinct coefficients whixh have the same modulo E9+7.

If I was sure that the modulo(E9+7) will not collide between two distict coefficients, a hash table with keys being the different modulo (E9+7) remainders and values being a bool would be an efficient way to keep track of uniquessness of squarefree numbers.

oleg_bChallenge Author + 0 comments From https://www.hackerrank.com/faq/sharing-code :

Don't share hints/codes/strategy during a live contest — it violates the contest rules.

oleg_bChallenge Author + 1 comment QUESTION: Does this mean the sum of all the numbers witch have distinct mod (10E9+7)?

No.

How to account for those numbers?

That is a substantial part of the problem.

janos_jung + 0 comments Hi Oleg,

could you please give me a hint (in private message if the problem is still open)? I just would like to know how to solve the problem..

Also it possible for two distinct squarefree Binomial coeffs in the input value range of the problem to have colliding mod(10E9+7) or does unequality of two squarefree Binom coeffs also imply the two of them having distinct modulo(10E9+7)?

Thanks in advance!

No more comments

Sort 1 Discussion, By:

Please Login in order to post a comment