3 ms·

I've solved about 60 problems on Project Euler but I've no clue about problems where a mod suddenly shows up in the question. How do these type of questions wor

by Bootvis 13y ago

I've solved about 60 problems on Project Euler but I've no clue about problems where a mod suddenly shows up in the question. How do these type of questions work?

thearn4 13y ago
Usually, it either implies a possible simplification step (using something like Fermat's little theorem), or its to reduce a huge answer to a range that can feasibly be pasted into the input element on their site.
- Bootvis 13y ago
  Thanks, I was thinking that mathematical techniques were used that I would never understand but this seems doable.
- Someone 13y ago
  It also may mean that there is some recurrence relation in a sequence that For example, the Fibonacci sequence, taken modulo 3 repeats every 8 numbers: 1 1 2 3 5 8 13 21 34 55 89 1 1 2 0 2 2 1 0 1 1 2 That makes it easy to answer such questions as "What is fib(3567^368857) mod 3?". Just compute 3567^368857 mod 8, and be careful to do the lookup right.
huherto 13y ago
The obvious part. Calculate the result and get the mod. Use that as a response. But probably the result is such a big number that you will not be able to calculate. That is where you to look for a trick to only calculate the mod. May be ignoring significant numbers as you do the calculation.
omn123 13y ago
Consider, for example, calculating binomial coefficients mod a large number. It's not hard to realise that C(n,k+1) = (n-k)C(n,k)/(k+1) is one way to write the binomial coefficients. So if we want to compute C(10^10,50309) mod 10^8, for example, we only ever really need to carry numbers mod 10^8 around. And since (ab) mod c = (a mob c)(b mod c) we can avoid obtaining really large numbers and can safely hold them in unsigned long ints. Since this problem is counting things, there is mostly like a recurrence-type relationship to it and at each step you would take the result mod N. Many combinatorics problems are like this. Although if you've only done 60 PE problems, then the ones in the 400s somewhat implicitly assume you've done the previous 400 since the ideas do built up.

by Bootvis 13y ago

I've solved about 60 problems on Project Euler but I've no clue about problems where a mod suddenly shows up in the question. How do these type of questions work?

thearn4 13y ago

Usually, it either implies a possible simplification step (using something like Fermat's little theorem), or its to reduce a huge answer to a range that can feasibly be pasted into the input element on their site.

Bootvis 13y ago
Thanks, I was thinking that mathematical techniques were used that I would never understand but this seems doable.
Someone 13y ago
It also may mean that there is some recurrence relation in a sequence that For example, the Fibonacci sequence, taken modulo 3 repeats every 8 numbers: 1 1 2 3 5 8 13 21 34 55 89 1 1 2 0 2 2 1 0 1 1 2 That makes it easy to answer such questions as "What is fib(3567^368857) mod 3?". Just compute 3567^368857 mod 8, and be careful to do the lookup right.

huherto 13y ago

The obvious part. Calculate the result and get the mod. Use that as a response. But probably the result is such a big number that you will not be able to calculate. That is where you to look for a trick to only calculate the mod. May be ignoring significant numbers as you do the calculation.

omn123 13y ago

Consider, for example, calculating binomial coefficients mod a large number. It's not hard to realise that C(n,k+1) = (n-k)C(n,k)/(k+1) is one way to write the binomial coefficients. So if we want to compute C(10^10,50309) mod 10^8, for example, we only ever really need to carry numbers mod 10^8 around. And since (ab) mod c = (a mob c)(b mod c) we can avoid obtaining really large numbers and can safely hold them in unsigned long ints. Since this problem is counting things, there is mostly like a recurrence-type relationship to it and at each step you would take the result mod N. Many combinatorics problems are like this. Although if you've only done 60 PE problems, then the ones in the 400s somewhat implicitly assume you've done the previous 400 since the ideas do built up.