math.NT — Number Theory
Powers of a Prime in the Image of Summatory Valuation Functions
J.-L. Nicolas asked how often a power of belongs to the image of , where is the -adic valuation, and showed that the number of exponents with in the image and the number of the other exponents both tend to infinity. We prove that lies in the image of if and only if is a sum of distinct terms of the superincreasing sequence . For every exponent there is at most one possible largest term , given by , and membership is then decided by an explicit recursion on pairs of integers at most , in at most steps. The exponents without such a and the exponents decided in at most one step form explicit infinite families, described completely, which contain the three families of Nicolas. The states of the recursion form a forest and the set of successful states is symmetric; this yields further explicit families and the bounds and , whereas the families of Nicolas give the constants and . The reduction, the unique candidate, the recursion and the symmetry extend to for every prime . Computations in exact integer arithmetic reproduce the table of Nicolas and give for , with between and for .