The p-adic valuation for Pascal's triangle row

by fungarwai, Dec 25, 2018, 11:07 PM

Here we discuss for different values of m when $\nu_p\left(\binom{n}{m}\right)=0,1$ with fixed integer n and prime p

Let $n=\sum_{k\ge 0} n_k p^k,m=\sum_{k\ge 0} m_k p^k$, consider $\binom{n}{m}$ with Kummer's theorem

When the number of carry is 0, take $0\le m_k\le n_k$, there are $n_k+1$ different values of $m_k$,

Totally, there are $(n_0+1)(n_1+1)\dots (n_N+1)$ different values of m

Specially when p=2, there are $2^{n_0+n_1+\dots+n_N}$ different values of m

When the number of carry is 1, suppose the carry take place at $m_k$,

$m_k+(n_k+p-m_k)\le p-1+p-1\Rightarrow n_k\le p-2$, $n_{k+1}-1\ge 0\Rightarrow n_{k+1}\ge 1$

$n_k+p-m_k\le p-1\Rightarrow m_k\ge n_k+1$, $m_{k+1}\le n_{k+1}-1$

there are $p-1-n_k$ different values of $m_k$ and $n_{k+1}$ different values of $m_{k+1}$

For each k, there are $\frac{(n_0+1)(n_1+1)\dots (n_N+1)(p-1-n_k)n_{k+1}}{(n_k+1)(n_{k+1}+1)}$ different values of m

Totally, there are $\sum_{n_k\le p-2, n_{k+1}\ge 1} \frac{(n_0+1)(n_1+1)\dots (n_N+1)(p-1-n_k)n_{k+1}}{(n_k+1)(n_{k+1}+1)}$ different values of m

Specially when p=2, there are totally $\sum_{n_k=0,n_{k+1}=1}2^{n_0+n_1+\dots+n_N-1}$ different values of m

Example

General Formula

There is a general formula suggested by William B. Everett.
NUMBER OF BINOMIAL COEFFICIENTS DIVISIBLE BY A FIXED POWER OF A PRIME

$\theta_j(n,p)=\sum_{w_1+w_2+\cdots+w_r=j\atop w_i\in\{0,1\}} F(w_1)L(w_r)\prod_{i=1}^{r-1} M(w_i, w_{i+1})$

where $F(w_1)=\begin{cases} c_0+1 & if~w_1=0\\p-c_0-1 & if~w_1=1\end{cases}$

$L(w_r)=\begin{cases} c_r+1 & if~w_r=0\\c_r & if~w_r=1\end{cases}$

$M(w_i,~w_{i+1})=\begin{cases} c_i+1 & if~w_i=0~and~w_{i+1}=0\\
p-c_i-1 & if~w_i=0~and~w_{i+1}=1\\
c_i & if~w_i=1~and~w_{i+1}=0\\
p-c_i & if~w_i=1~and~w_{i+1}=1\end{cases}$


Python program for general cases

input values for n, p, nu to get the number of values of m where $nu=\nu_p\left(\binom{n}{m}\right)$

  1. import math
  2. n = int(input("n="))
  3. p = int(input("p="))
  4. nu = int(input("nu_p="))
  5. N=0
  6. for m in range(0,n+1):
  7. s=0
  8. for k in range(0,int(math.log(n,p))+1):
  9. s=s+int(n/(p**k))-int(m/(p**k))-int((n-m)/(p**k))
  10. if s==nu:
  11. N=N+1
  12. print(N)


[pywindow]
import math
n = int(input("n="))
p = int(input("p="))
nu = int(input("nu_p="))
N=0
for m in range(0,n+1):
 s=0
 for k in range(0,int(math.log(n,p))+1):
  s=s+int(n/(p**k))-int(m/(p**k))-int((n-m)/(p**k))
 if s==nu:
  N=N+1
print(N)
[/pywindow]
This post has been edited 7 times. Last edited by fungarwai, Aug 21, 2021, 12:45 PM

Comment

1 Comment

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
This is a very nice explanation of kummers

by rzlng, Dec 25, 2018, 11:14 PM

Notable algebra methods with proofs and examples

avatar

fungarwai
Shouts
Submit
  • Nice blog!

    by Inconsistent, Mar 18, 2024, 2:41 PM

  • hey, nice blog! really enjoyed the content here and thank you for this contribution to aops. Sure to subscribe! :)

    by thedodecagon, Jan 22, 2022, 1:33 AM

  • thanks for this

    by jasperE3, Dec 3, 2021, 10:01 PM

  • I am working as accountant and studying as ACCA student now.
    I graduated applied mathematics at bachelor degree in Jinan University but I still have no idea to find a specific job with this..

    by fungarwai, Aug 28, 2021, 4:54 AM

  • Awesome algebra blog :)

    by Euler1728, Mar 22, 2021, 5:37 AM

  • I wonder if accountants need that kind of math tho

    by Hamroldt, Jan 14, 2021, 10:55 AM

  • Nice!!!!

    by Delta0001, Dec 12, 2020, 10:20 AM

  • this is very interesting i really appericate it :)

    by vsamc, Oct 29, 2020, 4:42 PM

  • this is god level

    by Hamroldt, Sep 4, 2020, 7:48 AM

  • Super Blog! You are Pr0! :)

    by Functional_equation, Aug 23, 2020, 7:43 AM

  • Great blog!

    by freeman66, May 31, 2020, 5:40 AM

  • cool thx! :D

    by erincutin, May 18, 2020, 4:55 PM

  • How so op???

    by Williamgolly, Apr 30, 2020, 2:42 PM

  • Beautiful

    by Al3jandro0000, Apr 25, 2020, 3:11 AM

  • Nice method :)

    by Feridimo, Jan 23, 2020, 5:05 PM

  • This is nice!

    by mufree, May 26, 2019, 6:40 AM

  • Wow! So much Algebra.

    by AnArtist, Mar 15, 2019, 1:19 PM

  • :omighty: :omighty:

    by AlastorMoody, Feb 9, 2019, 5:17 PM

  • 31415926535897932384626433832795

    by lkarhat, Dec 25, 2018, 11:53 PM

  • rip 0 shouts and 0 comments until now

    by harry1234, Nov 17, 2018, 8:56 PM

20 shouts
Tags
About Owner
  • Posts: 859
  • Joined: Mar 11, 2017
Blog Stats
  • Blog created: Sep 15, 2018
  • Total entries: 18
  • Total visits: 5855
  • Total comments: 8
Search Blog
a