Come in if you like programming AND math

[h9uest]

Hi all:

My cousin, who is a high school student receiving programming training on his school team, showed me what they did for training. I was impressed, and feel like sharing it with you guys. See below:

#include   <stdio.h>
long   g(long   k)
{
    if   (k   <=   1)   return   k;
    return   (2002   *   g(k   -   1)   +   2003   *   g(k   -   2))   %   2005;
}

int   main()   
{
    long   n;
    scanf( "%ld ",   &n);
    printf( "%ld\n ",   g(n));
    return   0;
} 

Input: 2005

Question: what is the output?



P.S. Do note, that they are required to answer the question without using computers. Their coach required them to get the answer within 10 minutes. Unfortunately, I failed.

But I modified the program to get the answer, which was correct.

So if anyone could solve the problem with Math, i.e. giving the analytical solution, it will be great.

Thanks.

[ultifinitus]

Lol- quite honestly looks like homework.

I came in, and was disappoint. (intentional lack of "ed")

[Catfish]

This is as far as I got. Anybody got some paper and pencil at hand?

g(2005) = ((2002 * g(2004) + 2003 * g(2003)) % 2005
g(2004) = ((2002 * g(2003) + 2003 * g(2002)) % 2005
g(2003) = ((2002 * g(2002) + 2003 * g(2001)) % 2005
g(2002) = ((2002 * g(2001) + 2003 * g(2000)) % 2005
(...)
g(3) = ((2002 * g(2) + 2003 * g(1)) % 2005
g(2) = ((2002 * g(1) + 2003 * g(0)) % 2005
g(1) = 1
g(0) = 0

Edit: Also, how much time does it take the program to output the solution?

[h9uest]

@ultifinitus:
You're free to distrust me, and of course, you're free to laugh out loud, however loud you want. But be cautious. Don't make you neighbour think you've gone mad and dial 911. Laughing too loud can be a signal of insanity.


@Catfish:
Mathematically, I'm in a situation similar to yours. I then think about summing all these on both sides of the "=" signs, and get something like:

sigma_g(from 2 to k) = (2002 * sigma_g(from 1 to k-1) + 2003 * sigma_g(from 0 to k-2)) % 2005

So if we temporarily don't look at % 2005, then it's a linear relation of sigma_g (k-1 items).
I can solve that and get the analytical solution for sigma_g (k-1 items).

But how should I deal with the % 2005? I'm pretty bad with number theory and don't deal with % quite often in Math. I have no idea how to proceed.

Also, how much time does it take the program to output the solution?

If you run the program as it is, it takes like forever. But if you change the recursive structure into an iterative one, it outputs the result within 1 second: 31.

The answer doesn't really matter much, and it's actually a cheat to modify the program in the way I did. What interests me is how we solve the problem as required: use math, and within 10 minutes.

Anyone shed light on it?

[Catfish]

But how should I deal with the % 2005? I'm pretty bad with number theory and don't deal with % quite often in Math. I have no idea how to proceed.

From what I know if we have X % 2005 there are more cases...
1) if X == 2005 * Y then the result is 0 (Y can also be 0)
2) if X == 2005 + Y then the result is Y (for Y positive and not part of case 1)
3) if X == 2005 - Y then the result is X (for Y positive and not part of case 1)

Also, sum both sides of "="? I don't think so. You simply need to use the previous two numbers in the calculation of the higher up number.
I think there's a pattern to be found so we can deduce the result of g(2005).

Edit: what's the result btw?
Edit 2: sorry didn't see it in your post.
Edit 3: I'd also like to see your iterative version, my brain is dead.

[kev82]

Ignore the modulus and you can solve the iteration to get

1002*g(n) = 2003^n + 1001*(-1)^n

You can't take modulus of this because 2003^2005 is too big. However, we can use the analytic form to derive the following expressions.

1st formula: g(n+1) = 2003*g(n) - 2002*(-1)^n
2nd formula: 1002*g(2*n) = (1002*g(n) - 1001*(-1)^n)^2 + 1001

You can then do the calculation as follows taking modulus each time (because the numbers aren't too big now)

g(2005) <-- g(2004) (1st formula)
g(2004) <-- g(1002) (2nd formula)
g(1002) <-- g(501) (2nd formula)
g(501) <-- g(500) (1st formula)
...
...

The total number of calculations is logarithmic in n. So easily possible for a human with a calculator.

[h9uest]

Yeah, I know what % does. What I meant was, I could recognize the pattern for the series where we don't have %. But I have no idea how to proceed mathematically with % added in, i.e. can't recognize the pattern for this sort. But if you think that's not the way to go, I don't want to influence you. Just ignore it.

Edit 3: I'd also like to see your iterative version, my brain is dead.

Algorithmically, the pattern of recursion reminded me of the problem of Fibonacci (spelled correctly?) series. And I was taught to use dynamic programming to convert the recursive structure into an iterative one. And I'm doing the same thing here:

#include <iostream>

long   g(long   k)
{
	long g0 = 0;
	long g1 = 1;
	long residue;
	
        for(long i=2;i <= k; i++)
	{
                residue = (g1*2002 + g0*2003) % 2005;
                g0 = g1;
                g1 = residue;
	};

	return residue;
};

int   main()   
{
        long   n;
	std::cin >> n;
	n = g(n);
	std::cout << n;
        return   0;
};

Still, any idea on the math side will be greatly appreciated.

[ne555]

You can't take modulus of this because 2003^2005 is too big

In that case you can use
(a*b) % m == [ (a%m) * (b%m) ]%m
a^n == a^{n/2} * a^{n/2} * a^{n%2}

[h9uest]

@kev82 & ne555:
Thank you for the inputs! They're helpful :)