\documentclass[12pt,reqno]{article} \def \endpf{{\ \ $\Box$ \medbreak}} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{question}[theorem]{Question} \begin{center} \vskip 1cm{\LARGE\bf Binomial Coefficient Predictors } \vskip 1cm \large Vladimir Shevelev\\ Department of Mathematics \\ Ben-Gurion University of the Negev\\ Beer-Sheva 84105 \\ Israel \\ \href{mailto:shevelev@bgu.ac.il}{\tt shevelev@bgu.ac.il}\\ \end{center} \vskip .2 in \begin{abstract} For a prime $p$ and nonnegative integers $n,k,$ consider the set $A_{n, k}^{(p)}=\{x\in [0,1,...,n]: p^k||\binom {n} {x}\}.$ Let the expansion of $n+1$ in base $p$ be $n+1=\alpha_{0} p^{\nu}+\alpha_{1}p^{\nu-1}+\cdots+\alpha_{\nu},$ where $0\leq \alpha_{i}\leq p-1, i=0, \ldots, \nu.$ Then $n$ is called a \slshape binomial coefficient predictor in base $p$\upshape ($p$-BCP), if $|A_{n, k}^{(p)}|=\alpha_{k}p^{\nu-k}, k=0,1, \ldots, \nu.$ We give a full description of the $p$-BCP's in every base $p.$ \end{abstract} \section{Introduction}\label{s1} Let $p$ be a prime. For nonnegative integers $n,k,$ consider the set \begin{equation}\label{1} A_{n,k}^{(p)}=\{x\in [0,1, \ldots, n]: p^k||\binom {n} {x}\}. \end{equation} A natural question that arises in connection with the set (\ref{1}) is the following. \begin{question}\label{q1} How, knowing $n,$ can we find the finite sequence $$|A^{(p)}_{n,0}|, |A_{n, 1}^{(p)}|, \ldots $$ (of course, without direct calculation)? \end{question} In 1899, Glaisher \cite{5} found a simple formula for $|A^{(2)}_{n,0}|.$ It was the first result on a thorny path of solution of this difficult problem. Unfortunately, this topic was forgotten for almost a half-century. Only in 1947, Fine \cite{3} obtained a generalization of Glaisher's result for $|A^{(p)}_{n,0}|.$ 20 years later, Carlitz \cite{1} solved a difficult problem for evaluation of $|A^{(p)}_{n,1}|$ and by this made, after the first Glaisher-Fine results, the first step on a way of creating a \slshape theory \upshape of the question. Now only four years later Hovard \cite{8} found a full solution of the question in case $p=2,$ by discovering a formula for $|A^{(2)}_{n,k}|.$ Since then it became certain that a general solution of the question is possible. Besides, Hovard \cite{9} found a solution for $|A^{(p)}_{n,2}|.$ After these results of Hovard there appear many other works. We indicate only papers by Granville \cite{7} Huard, Spearman and Williams \cite{10,11,12}. Finally in 2008, Everett \cite{2}, using his origin matrix method, obtained a full solution of the question, although, due to its generality, the Everett formula is complicated. The aim of this paper is to show that there are cases for which Question~\ref{q1} is solved practically immediately. An essential resource for the discovery of such cases is the famous Kummer theorem on carries which could possibly lead in the future to more general results with simpler formulas. In this paper we select cases for which a solution of Question~\ref{q1} for an arbitrary $p$ and a fixed $n$ immediately follows from the expansion of $n+1$ in base $p.$ Conversely, in the limits of these cases, knowing the sequence $\{|A^{(p)}_{n, k}|\},$ we can ``predict" the expansion of $n+1$ in base $p.$ In the connection with this, we introduce the following notion. \begin{definition}\label{df1} Let $p$ be prime and $n$ be a nonnegative integer. A nonnegative integer $n$ is called a \slshape binomial coefficient predictor in base $p$\upshape ($p$-BCP) if the numbers $|A_{n, k}^{(p)}|$ are summands of the expansion of $n+1$ in base $p ;$ more exactly, $|A_{n, k}^{(p)}|=\alpha_{k}p^{\nu-k}, k=0,1,\ldots,\nu,$ such that the expansion of $n+1$ in base $p$ is: $n+1=\alpha_{0} p^{\nu}+\alpha_{1}p^{\nu-1}+\cdots+\alpha_{\nu},$ where $0\leq \alpha_{i}\leq p-1, i=0,\ldots,\nu.$ \end{definition} Consider some examples. \begin{example}\label{ex1} It is easy to see that, for every $p,$ $n=0$ is \upshape $p$-BCP. \end{example} Indeed, $|A_{0,0}^{(p)}|=1, $ that is the expansion of 1 in every base $p$. \begin{example}\label{ex2} Let $p=2, n=11.$ \end{example} Then $n+1=8+4.$ The row of the binomial coefficients $\{\binom {n} {x}, x=0,1,\ldots,11\}$ is $$1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1. $$ Here $|A_{11,0}^{(2)}|=8, |A_{11,1}^{(2)}|=4, |A_{11,k}^{(2)}|=0, k\geq2.$ Thus, by the definition, $n=11$ is $2$-BCP. \begin{example}\label{ex3} Let $p=3, n=23.$ Then $n+1=2\cdot3^2+2\cdot3.$ \end{example} Here $|A_{23,0}^{(3)}|=18, |A_{23,1}^{(3)}|=6, |A_{23,k}^{(3)}|=0, k\geq2.$ Thus $n=23$ is $3$-BCP. Below we use the symbol $\vee$ for concatenation. In this paper we prove the following. \begin{theorem}\label{thm1} A number $n\geq0$ is a $p$-BCP if and only if one of the three following conditions holds: (a) $n=0;$ (b) $p\geq3$ and the expansion of $n$ in base $p$ is of the form $$i\vee(p-1)\vee(p-1)\vee\cdots\vee(p-1),$$ where $1\leq i\leq p-1;$ (c) the expansion of $n$ in base $p$ is of the form $$ (p-1)\vee\cdots\vee(p-1)\vee(p-2)\vee(p-1)\vee\cdots\vee(p-1).$$ \end{theorem} \begin{definition}\label{df2} A nonnegative integer $n$ is called \upshape a Zumkeller number (see sequence \seqnum{A089633} in Sloane's {\it Encyclopedia} \cite{19}) \slshape, if either it is 0 or its binary expansion has all digits $1,$ except, maybe, one. \end{definition} \begin{corollary}\label{cr1} $n\geq0$ is $2$-BCP if and only if $n$ is a Zumkeller number. \end{corollary} \section{Some classical results on binomial coefficients}\label{s2} The binomial coefficients play a very important role in numerous questions of number theory. For example, there is a well-known proof of the beautiful Chebyshev theorem, using the binomial coefficients (see, for example, a version of the proof due to Finsler in \cite{20}). A connection between some questions of divisibility of the binomial coefficients and the old conjecture of the infinity of twin primes was given by the author in \cite{17}. The first important contributions to the theory of binomial coefficients are due to Legendre (1830), Kummer (1852) and Lucas (1878). Let $p$ be a prime and $a_p(n)$ be the exponent such that \begin{equation}\label{2} p^{a_p(n)}|| n. \end{equation} Let, furthermore, \begin{equation}\label{3} n=n_0p^m+n_1p^{m-1}+\cdots+n_m,0\leq n_i\leq p-1, \end{equation} be the expansion of $n$ in base $p.$ Denote \begin{equation}\label{4} s_p(n)=n_0+n_1+\cdots+n_m. \end{equation} A.-M. Legendre (see \cite{14}, p.12) proved that (in our notation) \begin{equation}\label{5} a_p(n!)=(n-s_p(n))/(p-1). \end{equation} For another proof, see, e.g., \cite{16}. From (\ref{5}) we immediately obtain: $$ a_p(\binom {n} {x})=a_p(n!)-a_p(x!)-a_p((n-x)!)=$$ $$((n-s_p(n))-(x-s_p(x))-(n-x-s_p(n-x))/(p-1)=$$ \begin{equation}\label{6} (s_p(x)+s_p(n-x)-s_p(n))/(p-1). \end{equation} \begin{example}\label{ex4} \end{example} Since $s_2(2n)=s_2(n),$ then for the central binomial coefficients we find \begin{equation}\label{7} a_2(\binom {2n} {n})=s_2(n); \ a_2(\binom {2n+1} {n})=s_2(n+1)-1. \end{equation} Notice that in \cite{18} was posed a question which remains open up to now. \begin{question}\label{q2} Does the diophantine equation $s_p(n)=s_q(n),$ where $p\neq q$ are fixed primes, have infinitely many solutions? \end{question} It easy to see that, by (\ref{6}), the following equalities are equivalent: $$s_p((p-1)n)= s_q((q-1)m),$$ $$ (p-1)a_p(\binom {pn} {p})=(q-1)a_q(\binom {qm} {q}).$$ Furthermore, note that a trivial inequality holds (it formally follows from (\ref{6})) $$ s_p(x+y)\leq s_p(x)+s_p(y).$$ Moreover, using (\ref{6}), we conclude that the equality holds if and only if $\binom {x+y} {x}$ is not multiple of $p.$ Now we give another treatment of Question~\ref{q1}. Consider the equation \begin{equation}\label{8} s_p(x)+s_p(n-x)-s_p(n)=k(p-1), x\in[0,1,\ldots,n]. \end{equation} For $k\geq0, $ denote $\lambda_p^{(k)}(n)$ the number of solutions of (\ref{8}). Thus we see that \begin{equation}\label{9} |A_{n, k}^{(p)}|=\lambda_p^{(k)}(n), k=0,1,\ldots \end{equation} In 1852, Kummer \cite{13} made an important observation (a proof one can find, e.g., in \cite{4}): \slshape$ a_p(\binom {n} {x})$ is the number of carries which appear in adding $x$ and $n-x$ in base $p.$\upshape Another important result was obtained by Lucas \cite{15}. He proved that if together with (\ref{3}) \begin{equation}\label{10} t=t_0p^m+t_1p^{m-1}+\cdots+t_m, 0\leq t_i\leq p-1. \end{equation} then \begin{equation}\label{11} \binom {n} {t}\equiv\prod_{i=0}^{m}\binom {n_i} {t_i}\pmod p. \end{equation} From this we immediately obtain the next corollary (\cite{3}). \begin{corollary}\label{cr2} \begin{equation}\label{12} \lambda_p^{(0)}(n)=(n_0+1)(n_1+1)\cdots(n_m+1). \end{equation} \end{corollary} \bfseries Proof. \mdseries Indeed, (\ref{12}) gives the number of all nonzero products in (\ref{11}), when $0\leq t_i\leq n_i, i=0,\ldots,m . $ Since $t_i, n_i\in [0,\ldots,p-1],$ then none of the considered products is divisible by $p$. \endpf Note that in the binary case in (\ref{12}) it is sufficient to consider factors with $n_i=1$ only. Therefore, we have \begin{equation}\label{13} \lambda_2^{(0)}(n)=2^{s_2(n)}. \end{equation} The latter is the 1899 result of J. Glaisher. Note that in \cite{6} A. Granville gives an elegant proof of (\ref{13}), using unexpected new arguments. \section{Proof of necessity}\label{s3} We easily derive a proof of necessity by using {\it only} the first condition of Definition~\ref{df1}, i.e., from the equality $|A_{n,0}^{(p)}|=\alpha_0p^{\nu}.$ In connection with (\ref{3}), note that $\nu\neq m$ only when $n_0=n_1=\cdots=n_m=p-1.$ In other cases we consider the equality $|A_{n,0}^{(p)}|=\alpha_0p^{m}.$ In turn, $\alpha_0 \neq n_0\leq p-2$ only when $n_1=\cdots=n_m=p-1.$ Let now $n$ be $p$-BCP when $n_0=p-1,$ but not all $n_i$ equal $p-1.$ Thus, we have \begin{equation}\label{14} |A_{n,0}^{(p)}|=(p-1)p^{m}. \end{equation} From this equality and Corollary~\ref{cr2} we conclude that exactly $m$ from $m+1$ brackets in product (\ref{12}) equal $p,$ while one bracket equals $p-1.$ This means that exactly $m-1$ digits from $ n_1,\ldots, n_m $ equal to $p-1,$ while one digit equals $p-2$. \endpf \section{Proof of sufficiency}\label{s4} Here we use the Kummer theorem in the following equivalent form: $ a_p(\binom {n} {x})$ is the number of carries which appear in subtracting $x$ from $n$ in base $p.$\upshape Let $n\geq0$ satisfy the conditions of Theorem~\ref{thm1}. Evidently, in the trivial case when $n=p^{m+1}-1=\underbrace{(p-1)\vee (p-1)\vee\cdots\vee (p-1)}_{m+1}$ we have a $p$-BCP. Indeed, here $n+1=p^{m+1}$ and, by (\ref{9}) and (\ref{12}), $|A_{n, 0}^{(p)}|=p^{m+1}.$ On the other hand, for every $x\leq n,$ in subtracting $x$ from $n$ in base $p$ we have no carries, that is, $|A_{n,k}^{(p)}|=0, k\geq1.$ Analogously, we have a $p$-BCP in case $n=n_0\vee \underbrace{(p-1)\vee (p-1)\vee\cdots\vee (p-1)}_{m}, n_0\leq p-2.$ Indeed, here $n+1=(n_0+1)p^m $ and, by (\ref{9}) and (\ref{12}), $|A_{n,0}^{(p)}|=(n_0+1)p^{m}$ and before and again we have no carries in subtracting $x$ from $n$ in base $p.$ Let now $n$ have a unique digit $p-1$ in its expansion in base $p.$ Consider such an $n$ of the general form: \begin{equation}\label{15} n=\underbrace{(p-1)\vee \cdots\vee (p-1)}_{t}\vee(p-2)\vee\underbrace{(p-1)\vee \cdots\vee (p-1)}_{m-t}. \end{equation} Then $$n+1=\underbrace{(p-1)\vee \cdots\vee (p-1)}_{t+1}\vee \underbrace{0\vee \cdots\vee 0}_{m-t}=$$ \begin{equation}\label{16} (p-1)(p^m+p^{m-1}+\cdots+p^{m-t}). \end{equation} Let $x$ have the form \begin{equation}\label{17} x=x_0\vee \cdots\vee x_{t-1}\vee x_t\vee x_{t+1}\vee\cdots\vee x_m \end{equation} in base $p.$ If $x_t\leq p-2,$ then in subtracting $x$ from $n$ in base $p$ we have no carries. Evidently, the number of such $x$'s is \begin{equation}\label{18} |A_{n,0}^{(p)}|=p^t(p-1)p^{m-t}=(p-1)p^{m}. \end{equation} If $x_t=p-1,$ such that also the equality \begin{equation}\label{19} x_t=x_{t-1}=x_{t-2}=\cdots=x_r=p-1, \end{equation} holds, then, in view of $x\leq n,$ the length of this chain is not more than $t,$ that is, \begin{equation}\label{20} 1\leq r\leq t. \end{equation} In this case the number of carries is equal to the length of the chain, i.e., $t-r+1,$ and, by Kummer's theorem, we have \begin{equation}\label{21} x\in A_{n,t-r+1}^{(p)}. \end{equation} Putting \begin{equation}\label{22} t-r+1=k, \end{equation} we easily calculate $|A_{n,k}^{(p)}|.$ \begin{equation}\label{23} |A_{n,k}^{(p)}|=p^{m+1-k}\cdot \frac {p-1} {p}=(p-1)p^{m-k}, k=1,\ldots,t, \end{equation} where the factor $\frac {p-1} {p}$ corresponds to the digit $x_{r-1},$ i.e., the place after the end of chain (\ref{19}). Comparison of (\ref{18}) and (\ref{23}) with (\ref{16}) shows that $(p,n)$ is a $p$-BCP. This completes the proof of Theorem~\ref{thm1}. \endpf \section{Acknowledgments}\label{s5} The author is grateful to J.-P. Allouche for sending a scanned copy of pp.\ 10-12 of Legendre's book \cite{14}, to D. Berend for important advice, and to Ch. Greathouse for some improvements. \begin{thebibliography}{20} \bibitem 1 L. Carlitz, The number of binomial coefficients divisible by a fixed power of a prime, \itshape Rend. Circ. Mat. Palermo \upshape(2) \bfseries 16 \mdseries (1967) 299--320. \bibitem 2 W. B. Everett, Number of binomial coefficients divisible by a fixed power of a prime, \itshape INTEGERS \upshape \bfseries 8 \mdseries (2008), \#A11. \bibitem 3 N. J. Fine, Binomial coefficients modulo a prime, \itshape Amer. Math. Monthly \upshape \bfseries 54 \mdseries (1947), 589--592. \bibitem 4 A. Fraenkel and A. Kontorovich, The Sierpi\'{n}ski sieve of nim-varieties and binomial coefficients, \itshape INTEGERS \upshape \bfseries 7 \mdseries (2)(2007), \#A14. \bibitem 5 J. Glaisher, On the residue of a binomial-theorem coefficient with respect to a prime modulus, \itshape Quarterly J. of Pure and Applied Math. \upshape \bfseries 30 \mdseries (1899), 150--156. \bibitem 6 A. Granville, Zaphod Beeblebrox's brain and the fifty-ninth row of Pascal's triangle, \itshape Amer. Math. Monthly \upshape \bfseries 99 \mdseries (1992), 318--331; \bfseries 104 \mdseries (1997), 848--851. \bibitem 7 A. Granville, Arithmetic properties of binomial coefficients. I. Binomial coefficients modulo prime powers. {\it Organic Mathematics}, CMS Conf. Proc., Vol.\ 20, Amer. Math. Soc., Providence, 1997, pp.\ 253--276. \bibitem 8 F. T. Howard, The number of binomial coefficients divisible by a fixed power of 2, \itshape Proc. Amer. Math. Soc. \upshape \bfseries 29 \mdseries (1971), 236--242. \bibitem 9 F. T. Howard, Formulas for the number of binomial coefficients divisible by a fixed power of a prime, \itshape Proc. Amer. Math. Soc. \upshape \bfseries 37 \mdseries (1973), 358--362. \bibitem {10} J. G. Huard, B. K. Spearman, and K. S. Williams, Pasal's triangle (mod 9), \itshape Acta Arith. \upshape \bfseries 78 \mdseries (1997), 331--349. \bibitem {11} J. G. Huard, B. K. Spearman, and K. S. Williams, On Pascal's triangle modulo $p^2$, \itshape Colloq. Mathem. \upshape \bfseries 74 \mdseries (1997), 157--165. \bibitem {12} J. G. Huard, B. K. Spearman, and K. S. Williams, Pascal's triangle (mod 8), \itshape Europ. J. Combin. \upshape \bfseries 19 \mdseries (1998), 45--62. \bibitem {13} E. E. Kummer, \"{U}ber die Erg\"anzungss\"atze zu den allgemeinen Reciprocit\"atsgesetzen, \itshape J. Reine Angew Math. \upshape \bfseries 44 \mdseries (1852), 93--146. \bibitem {14} A.-M. Legendre, \itshape Th\'{e}orie de Nombres, \upshape Firmin Didot Fr\`{e}res, Paris, 1830. \bibitem {15} E. Lucas, Th\'{e}orie des fonctions num\'{e}riques simplement p\'{e}riodiques, \itshape Amer. J. Math. \upshape \bfseries 1 \mdseries (1878), 184--240, 289--321. \bibitem {16} J.-C. Schlage-Puchta and J. Spilker, Altes und neues zur Quersumme, \itshape Math. Semesterber. \upshape \bfseries 49 \mdseries (2002), 209--226. \bibitem {17} V. Shevelev, On divisibility of $\binom {n-i-1} {i-1}$ by $i$, \itshape Int. J. Number Theory \upshape \bfseries 3 \mdseries (2007), 119--139. \bibitem {18} V. Shevelev, Compact integers and factorials, \itshape Acta Arith. \upshape \bfseries 126 \mdseries (2007), 195--236. \bibitem {19} N. J. A. Sloane, \textit{The On-Line Encyclopedia of Integer Sequences}, \href{http://oeis.org}{\tt http://oeis.org}. \bibitem {20} E. Trost, \itshape Primzahlen, \upshape Birkh\"{a}user-Verlag, 1953. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11B65; Secondary 11A07, 11A15. \noindent \emph{Keywords: } binomial coefficient, maximal exponent of a prime dividing an integer, p-ary expansion of integer, Kummer's theorem. \bigskip \hrule \bigskip \noindent (Concerned with sequence \seqnum{A089633}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received March 29 2010; revised version received April 5 2010; September 3 2010; January 19 2011; February 13 2011. Published in {\it Journal of Integer Sequences}, March 25 2011. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document} .