Problem 288

[vermillon]

Problem 288 (View Problem)

Hello,

I have questions concerning the phrasing of this problem: (mostly due to the fact that English is not my mother tongue)
1) What does the * in "T_(n)*p^(n)" mean? Is it a multiplication sign or something else?

2) "Let NF(p,q) be the number of factors p in Nfac(p,q)." I have no idea what "the number of factors p in another number" is supposed to mean. Is it the power of factor p in the decomposition in a product of prime numbers? Any example would be more than welcome on this expression.

Thanks in advance

[remy72]

Problem 288 (View Problem)

Hello,

I have questions concerning the phrasing of this problem: (mostly due to the fact that English is not my mother tongue)
1) What does the * in "T_(n)*p^(n)" mean? Is it a multiplication sign or something else?

2) "Let NF(p,q) be the number of factors p in Nfac(p,q)." I have no idea what "the number of factors p in another number" is supposed to mean. Is it the power of factor p in the decomposition in a product of prime numbers? Any example would be more than welcome on this expression.

Thanks in advance

1) yes, the "*" stands for the multiplication sign,
2) indeed, it's the power of p in the prime decomposition of Nfac(p,q)

[vermillon]

Thanks, solved! (25" with Python, without too much optimisation)

[pgrontas]

This problem is driving me crazy.
I have the test case correct (NF(3,10000) mod 3^(20)=624955285), my algorithm is pretty fast but i keep getting the wrong answer.
Can someone please verify that:
NF(61,10^6) mod 61^9 = 1075175834078238
Thanks.

[albert_nik]

Yes, i get this too: NF(61,10^6) mod 61^9 = 1075175834078238

Maybe you have same problem with me.
If you are using
long m = (long) Math.Pow(61,10) // gives m= 713342911662882560 !!!!
check this :
61^9 = 11694146092834141
61^10=713342911662882601

[cyclops]

Yes, i get this too: NF(61,10^6) mod 61^9 = 1075175834078238

Maybe you have same problem with me.
If you are using
long m = (long) Math.Pow(61,10) // gives m= 713342911662882560 !!!!
check this :
61^9 = 11694146092834141
61^10=713342911662882601

That's interesting; I used BigInteger off the bat so never ran into that problem, but it's the type of bug I would have a hard time spotting. I'm a bit surprised double precision results in that much of an error in this situation. I'll keep that in mind for next time!

[pgrontas]

Thank you very much guys.
That was it.

[kingmoshe]

on problem 288 there is an example that say :NF(3,10000) mod 3^20=624955285. but this is not correct acctualy NF(3,9999) mod 3^20=624955285.

[TripleM]

The example is correct as stated.

[Oliver1978]

The first 10 Tn with p = 61 are [7, 30, 13, 59, 40, 50, 30, 31, 58, 17].

Is this correct?

[Georg]

These are T₁ to T₁₀. T₀ is missing.

[Oliver1978]

Typo. Wrong Index. T should start with [10, ...].

Apart from that aforementioned minor hiccup I have a more severe problem concerning my understanding of the problem. It's about "Let NF(p, q) be the number [...]". Would someone be willing to hear me about it? Privately of course, since I don't want to be blamed for spilling possibly essential information.

[Georg]

[...]
I have a more severe problem concerning my understanding of the problem. It's about "Let NF(p, q) be the number [...]".
[...]

Read there.

[Oliver1978]

Очень хорошо

[LarryBlake]

Thank you, albert_nik! I had the same Math.Pow problem (C#).

[Circling]

Having quite some trouble with this one. My code works for the example given but not for the actual question.

Can someone confirm the following:

NF(5, 10) = 735554
NF(61, 20) mod (61 ^ 10) = 118406441632680948
NF(61, 10) mod (61 ^ 3) = 34930
T_9.999.999 = 36 when p = 61

Also, can I privately contact with someone that has solved the problem?
NOTE: I use Python which can store and manipulate numbers with hundreds of digits (though slowly for obvious reasons), so owerflow is out of the question.

EDIT: Nevermind, I solved it. My error was having the N(p, q) function sum for n = 0 to q-1, not for n = 0 to q. Once I fixed that, I got the right answer. The values for NF examples are most likely false too, even though they are correct for my flawed interpretation.