- #1

- 368

- 0

there is general formula for findind out, "Which highest power of x is divisible n! with?" Eg. Which highest power of 5 is divisable 50! with?

But I forgot it and can't find it now...will somebody help me please?

Thank you.

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter twoflower
- Start date

- #1

- 368

- 0

there is general formula for findind out, "Which highest power of x is divisible n! with?" Eg. Which highest power of 5 is divisable 50! with?

But I forgot it and can't find it now...will somebody help me please?

Thank you.

- #2

AKG

Science Advisor

Homework Helper

- 2,565

- 4

- #3

- 368

- 0

AKG said:^{12}.

Yes, this manual approach is clear. But there is also a general formula..

- #4

AKG

Science Advisor

Homework Helper

- 2,565

- 4

(a

(a

(a

(a

(3, 1, 0, 0, ...)

(3, 1, 1, 0, 0, ...)

(4, 2, 1, 0, 0, ...)

(4, 2, 1, 1, 0, 0, ...)

(7, 2, 1, 1, 0, 0, ...)

(7, 4, 1, 1, 0, 0, ...)

(8, 4, 2, 1, 0, 0, ...)

(8, 4, 2, 1, 1, 0, 0, ...)

(10, 5, 2, 1, 1, 0, 0, ...)

(10, 5, 2, 1, 1, 1, 0, 0, ...)

(11, 5, 2, 2, 1, 1, 0, 0, ...)

The exponent of 2 changes every 2 rows, the exponent of 3 changes every 3 rows, the exponent of p will change every p rows. Ignoring repetition, the exponents for 2 go: 0, 1, 3, 4, 7, 8, 10, 11, ...

For 3, they go 0, 1, 2, 4, 5, ...

For 5, they go 0, 1, 2, ...

Some numbers are skipped in the above sequences because powers occur, i.e. in the sequence for 2, it goes from 1 to 3 without going through 2 because the 4 in 4! contributes two 2's, not just 1. I'm very tired right now, but I suppose if you can generalize what's going on here, it might be a helpful step in finding a general formula.

Well I suppose if you just want to know the general formula and aren't trying to figure it out yourself, then the above isn't much help.

- #5

VietDao29

Homework Helper

- 1,424

- 3

I suppose that this is **not** a homework problem... So here's my approach.

Let's say that [x] is the function that will return the integer part before the decimal point of the number*x*, eg: [**37**.5534] = 37.

Say, you need to find the largest p that satisfies:

x^{p} divides n!, for some given x (x is **prime**), and n.

Let: [tex]\rho := \left[ \frac{\ln n}{\ln x} \right][/tex], ie: [tex]\rho[/tex] is the largest positive integer such that: [tex]x ^ \rho \leq n[/tex]

So for every x consecutive integers there's one integer that's divisible by x, for every x^{2} consecutive integers there's one integer that's divisible by x^{2}, for every x^{3} consecutive integers there's one integer that's divisible by x^{3},...

So the largest p can be obtained by:

[tex]p := \sum_{i = 1} ^ \rho \left[ \frac{n}{x ^ i} \right][/tex]

---------------------

If x is**not** prime, then you can *prime-factorize* it:

[tex]x = \lambda_1 ^ {\alpha_1} \ \lambda_2 ^ {\alpha_2} \ \lambda_3 ^ {\alpha_3} \ ... \lambda_k ^ {\alpha_k}[/tex]

Where: [tex]\lambda_i, \ i = 1..k[/tex] are primes.

Then: [tex]x ^ p = (\lambda_1 ^ {\alpha_1} \ \lambda_2 ^ {\alpha_2} \ \lambda_3 ^ {\alpha_3} \ ... \lambda_k ^ {\alpha_k}) ^ p = \lambda_1 ^ {\alpha_1 p} \ \lambda_2 ^ {\alpha_2 p} \ \lambda_3 ^ {\alpha_3 p} \ ... \lambda_k ^ {\alpha_k p}[/tex]

If x^{p} divides n! then [tex]\lambda_i ^ {\alpha_i p}, \ i = 1..k[/tex] must also divide n!.

So you can use the same method (*as shown above*) to find the largest [tex]\rho_i, \ i = 1..k[/tex] such that [tex]\lambda_i ^ {\rho_i}, \ i = 1..k[/tex] divides n!.

Then define: [tex]\beta_i := \left[ \frac{\rho_i}{\alpha_i} \right], \ i = 1..k[/tex].

And the largest p can be found by:

[tex]p = \min (\beta_i), \ i = 1..k[/tex]

Let's say that [x] is the function that will return the integer part before the decimal point of the number

Say, you need to find the largest p that satisfies:

x

Let: [tex]\rho := \left[ \frac{\ln n}{\ln x} \right][/tex], ie: [tex]\rho[/tex] is the largest positive integer such that: [tex]x ^ \rho \leq n[/tex]

So for every x consecutive integers there's one integer that's divisible by x, for every x

So the largest p can be obtained by:

[tex]p := \sum_{i = 1} ^ \rho \left[ \frac{n}{x ^ i} \right][/tex]

---------------------

If x is

[tex]x = \lambda_1 ^ {\alpha_1} \ \lambda_2 ^ {\alpha_2} \ \lambda_3 ^ {\alpha_3} \ ... \lambda_k ^ {\alpha_k}[/tex]

Where: [tex]\lambda_i, \ i = 1..k[/tex] are primes.

Then: [tex]x ^ p = (\lambda_1 ^ {\alpha_1} \ \lambda_2 ^ {\alpha_2} \ \lambda_3 ^ {\alpha_3} \ ... \lambda_k ^ {\alpha_k}) ^ p = \lambda_1 ^ {\alpha_1 p} \ \lambda_2 ^ {\alpha_2 p} \ \lambda_3 ^ {\alpha_3 p} \ ... \lambda_k ^ {\alpha_k p}[/tex]

If x

So you can use the same method (

Then define: [tex]\beta_i := \left[ \frac{\rho_i}{\alpha_i} \right], \ i = 1..k[/tex].

And the largest p can be found by:

[tex]p = \min (\beta_i), \ i = 1..k[/tex]

Last edited:

- #6

- 1,307

- 109

[tex]\frac{n-\mu}{p-1},[/tex]

where [itex]\mu[/itex] is the sum of the digits of the base p representation of n.

Share: