# P-adic valuation expression for a given natural number

• I
• DaTario

#### DaTario

TL;DR Summary
Hi All, is there a closed expression that yields the p-adic valuation of a natural number n ?
Hi All,

If p is a prime, the p-adic valuation, ## v_p(n) ##, of a positive natural number is defined as the highest power of p that divides n. For instance, ##v_3(45) = 2##.
My question is: Is there a mathematical expression for ##v_p(n)## ?

doubtful - primes are too scattered around

Thank you, mathman. Could you please elaborate a bit more on this comment?

I have just found this paper:
https://arxiv.org/ftp/arxiv/papers/1907/1907.11902.pdf
where the author derives a formula for ##v_p(n)##. The approach goes like this:

##v_p (n) = v_p (n!) – v_p ((n –1)!)##
##= (n – s_p (n))/(p –1) – (n –1– s_p (n–1))/(p –1) ##
##= (1 – s_p (n) + s_p (n–1))/(p –1)##
##= (1 – Δ s_p (n–1))/(p –1). ##

where ##s_p (n)## denotes the sum of the digits in the base-p expansion of n.

Example: ##v_3(36) = 2 ##
##36 = 1 . 9 + 1 . 27 \Rightarrow s_3(36) = 1 + 1 = 2##
##35 = 2 . 1 + 2 . 3 + 1 . 27 \Rightarrow s_3(35) = 2 + 2 + 1 = 5##
Thus,
##v_3(36) = \frac{1 - \Delta s_3(36) + \Delta s_3(35)}{3-1} = \frac{1 - 2 + 5}{2} = \frac{4}{2} = 2 ##.

Thak you all.

Last edited:
Editing the last post: In the last equation there is no ##\Delta## anymore.

Last edited:
is there some formula for the sum of the digits in the base p expansion? this is something that seems to require an iterative application of the euclidean algorithm.

Yes, mathwonk, it seems to require such algorithmic approach. Do you think using instead functions as Floor[ ], Ceiling[ ] and FractionalPart[ ], to implement ##v_p(n)##, will demand the same algorithmic structure?

I found a simple and alternative formula for ##v_p(n)##, given by:
$$v_p(n) = \lfloor \log_p (n) \rfloor - \sum_{j=1}^{\lfloor \log_p (n) \rfloor} \left \lceil \left \{ \frac{n}{p^j}\right \} \right\rceil,$$

But it does not seem to be of any practical use.

Thank you, mathman. Could you please elaborate a bit more on this comment?
No deep study. Just a gut feeling, since prime factoring seems to be "random" as a function of n.

Thank you, mathman.