Subprime factorization and the numbers of binomial coefficients exactly divided by powers of a prime (Q2882924)

In this paper the notion of \textit{subprime factorization} is used to establish recurrence relations for \(\theta_{j} (n,p)\), \(i.e.\), the number of binomial coefficients in a given row of Pascal's triangle that are divisible by \(p^j\) and not divisible by \(p^{j+1}\), where \(p\) is a prime. \textit{W. B. Everett} [Integers 8, No. 1, Article A11, 8 p. (2008; Zbl 1202.11017)] had already given the general formula for \(\theta_{j} (n,p)\) from a corrected version of which he starts proving these new recurrence relations with significant consequences in terms of computational savings.NEWLINENEWLINEThe paper is organized as follows.NEWLINENEWLINEThe \textit{Introduction} describes the progress in the prime divisibility of binomial coefficients through the set of regular tilings of Pascal's triangle by the works of \textit{J. W. L. Glaisher} [Quart. J. 30, 150--156 (1898; JFM 29.0152.05)], \textit{N. J. Fine} [Am. Math. Mon. 54, 589--592 (1947; Zbl 0030.11102)], \textit{L. Carlitz} [Rend. Circ. Mat. Palermo, II. Ser. 16, 299--320 (1967; Zbl 0177.06701)] and of \textit{F.~T.~Howard} [Proc. Am. Math. Soc. 29, 236--242 (1971; Zbl 0221.05016); Proc. Am. Math. Soc. 37, 358--362 (1973; Zbl 0261.05008)]. A theorem by \textit{E. Rowland} [J. Comb. Number Theory 3, No. 1, 15--25 (2011; Zbl 1245.11027)] is also recalled. The author remarks that his motivation for seeking the general recurrence relations presented here was the notion of \textit{binomial predictors} by \textit{V. Shevelev} [``Binomial predictors'', \url{arXiv:0907.3302}and J. Integer Seq. 14, No. 2, Article 11.2.8, 8 p. (2011; Zbl 1229.11032)] which provides a recursive definition of \(\Theta (n,p)=\{ \theta_{0} (n,p), \theta_{1} (n,p), \dots \}\) for a particular class of \(n\).NEWLINENEWLINEThe \textit{Section 2} explains the notion of subprime factorization (\(sub\)scripted \(prime\) symbol) and indicates that it results in the general formula \(\theta_{j} (n,p)\) for the number of binomial coefficients exactly divided by a fixed power of a prime. Before passing from prime to subprime factorization, advantageous for the elimination of powers, the author recalls some basic concepts in the geometry of binomial coefficients described by \textit{W. Stephen} [Am. Math. Mon. 91, 566--571 (1984; Zbl 0553.05004)]. The author also identifies an approach adaptable to other problems in the conversion from a self-similar scalar object to an infinite set of regular tilings.NEWLINENEWLINEThe \textit{Section 3} offers three simple numerical examples to help in visualizing the recurrence relations.NEWLINENEWLINEThe \textit{Section 4} presents the proofs of all the formulas, the most interesting of which is the recurrence in the special case \(n = p^{k} m-1\): NEWLINE\[NEWLINE\Theta (n,p) = p^{k} \Theta (m-1,p).NEWLINE\]NEWLINE In the proofs the author employs the method of induction, the combination of \(like\) terms and some achievements about the subprime-divisibility triangles and the self-congruency supplied in the \textit{Section 2}. As a notable curiosity, one of the divisibility properties for the arithmetical triangle has alternatively been proved by \textit{K. Kokhas'} [``Amazing properties of binomial coefficients'', \url{http://www.turgor.ru/lktg/2012/1/1-1en.pdf}].NEWLINENEWLINEThe \textit{Conclusions} discuss the relative computational efficiency of the methods for determining the number of binomial coefficients exactly divided by a fixed power of a prime that is traditionally computed by counting the number of carries when adding \(n-k\) and \(k\) in base \(p\), with a basic rate of increase as \(p^{r}\). The mathematical justification derives from a work by \textit{E. E. Kummer} [J. Reine Angew. Math. 44, 93--146 (1852; ERAM 044.1198cj)] related to the connection between binomial expressions and the number of carries that result in the sum, in different bases, of the variables forming the binomial coefficient. The author remarks how his new general recurrence relations allow to diminish the rate of increase in computational steps to \(r^{2}\), that is a further improvement of the previously found \(2^{r}\).