Problem 258

[zwuupeape]

Hey. Can anyone please confirm my result?

I use the same parameters (modulo 20092010, find gk for k = 10 ^ 18), except:

gk = 1 if 0 <= k <= 10

gk = g(k-10) + g(k-9) for k > 10

I get 11649166.

For modulo 260, find gk for k = 10 ^ 16, gk = 1 if 0 <= k <= 30 else gk = g(k-30) + g(k-29), I get 145.

Correct ??

[bladewang]

I found g(k) == 2^(k/2000), if k is a multiple of 2000
and
g(10¹⁸) == 2^{(5*10^14)}
so, the answer is same to
2^{(5*10^14)} mod 20092010


It's my code in Python:

Code: Select all

n = 20092010
print (((2**10000%n)**100000%n)**100000%n)**5%n

the result is 8340206

it's wrong ……
WHY ???

[zwuupeape]

This is incorrect. It is only true for k < 2000*2000.

Also, you might consider using Python's built-in modular exponentiation, you don't have to raise the number to the power and then take the modulo.

[quilan]

Also, you might consider using Python's built-in modular exponentiation, you don't have to raise the number to the power and then take the modulo.

Yupyup... pow(a,b,m) is awesome. Learn it, live it, love it.

[Jochen_P]

Yeah, this will print the wrong result in no time

Code: Select all

n = 20092010
print pow(pow(pow(pow(2,10000,n),100000,n),100000,n),5,n)

this one too:

Code: Select all

print  pow(2,10**18/2000, 20092010)

Can Anyone confirm 22189656 for k = 10¹⁰ ?

[harryh]

No, that's not correct (for k=10¹⁰).

[Jochen_P]

dang!

thanx

[edit] removed other result as it was implausible ?

[zwuupeape]

No, this is not true.

[quilan]

Can Anyone confirm 22189656 for k = 10¹⁰ ?

You've got some wrong approaches here, but it strikes me as somewhat silly such that 22189656 > 20092010. Your end result is greater than your modulus?

[quilan]

So, I solved the problem and I don't want to pollute the board for it by asking for help, but could some kindly soul PM me about how in the heck the method the majority of people used works? I must have completely missed that entire section in my lin-alg classes.

Edit: Got the idea behind the main idea thanks to zwuupeape but still confused about the identity named in the first post.

Edit2: Got it now. Thanks guys, you rock!

[daniel.is.fischer]

Edit: Got the idea behind the main idea thanks to zwuupeape but still confused about the identity named in the first post.

Explanation sent, hope that clarifies it.

[Jochen_P]

Can Anyone confirm 22189656 for k = 10¹⁰ ?

You've got some wrong approaches here, but it strikes me as somewhat silly such that 22189656 > 20092010. Your end result is greater than your modulus?

Um, yeah, that was a silly mistake in the generator, which impelemented the modulus calc in each step but returned twice the modulus ... didn't even realize the result was greater than the modulus

I stopped working on this problem completely and deleted my efforts so far. Will return to it when I am less silly

[viv_ban]

Can somebody please confirm my result. For
g_k = 1 for k = 0 to 14
g_k = (g_k-14+ g_k-15) mod 10^6 for k>= 15

I got g_10^18 = 336460

[zwuupeape]

You mean gk = 1 for 0 <= k <= 15, then this is correct.

[viv_ban]

Thanks zwuupeape.
Is it possible to solve this question in less than 1 min?
I need to perform around 70*2000³ operations and I don't think python can perform this many operations with in 1 min. Even after optimization I can reduce total operations to 70*2000^2.8 which again is not enough to solve the problem in1 min.
Is there exist a better algorithm? If so what kind of order should I be looking for?

[hk]

There exists an O(n²) method.

[ThomasH]

I do have the same problem that quilan had: I solved the problem (in very LONG runtime) and gained access to the forum, but I have no idea, why the method i.e. of the first post is working. Could some kindly soul PM me some hints for further reading?

[quilan]

I do have the same problem that quilan had: I solved the problem (in very LONG runtime) and gained access to the forum, but I have no idea, why the method i.e. of the first post is working. Could some kindly soul PM me some hints for further reading?

I'll send some info once I get into work this morning...

[ThomasH]

quilan, thank you very much for your quick response - and a warm thank you, too, to daniel.is.fischer und zwuupeape, who were quoted by quilan.

[OskarS]

Can I just ask a quick question:

In order to solve this problem, do you at any point need to deal with complex numbers? Because the way I'm doing it, you have to, but I'm starting to think that I've might have gone down the wrong alley here.

If anyone could either reply or PM me with the answer, I'd be mighty grateful. Just a yes or no needed (though I wouldn't turn down more help, obviously . Thanks!