Project Euler Forum

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

vermillon wrote: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)

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

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.

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

albert_nik wrote: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!

Thank you very much guys.
That was it.

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.

The example is correct as stated.

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

Is this correct?

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

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.

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

Read there.

Очень хорошо

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

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.