2
$\begingroup$

Let me first pose the questions free of context:

Given prime $p$ and positive integers $b$ and $N$, define $F(p,b,N) = \Big\lfloor (1/b) \sum_{i=1}^\infty \lfloor N/p^i \rfloor \Big\rfloor.$

That is, $F(p,b,N)$ is the exponent of $p$ in the prime factorization of $N!$, divided by $b$, and the quotient truncated to the greatest integer.

Let $\hat F$ approximate $F$ by dropping all use of the floor function: $\hat F(p,b,N) = (1/b) \sum_{i=1}^\infty N/p^i = N/b(p-1).$

The question is this: Given various $p$ and $b$, how valid is it to use $\hat F(p,b,1)$ (that is, ignoring $N$) as a proxy for comparing $F$ itself over all $N$? Specifically:

Conjecture 1. Suppose $p_1$, $p_2$ are primes and $b_1$, $b_2$ are positive integers such that $\hat F(p_1, b_1, 1) < \hat F(p_2, b_2, 1)$. Then $F(p_1,b_1,N) \leq F(p_2,b_2,N)$ for all positive integers $N$.

Conjecture 2. Suppose $p_1, p_2, \ldots, p_k$ are distinct primes and $b_1, b_2, \ldots, b_k$ are positive integers such that $\hat F(p_i, b_i, 1) = \hat F(p_j, b_j, 1)$ for all $1 \leq i, j \leq k$. Then there are infinitely many positive integers $N$ such that, for all $1 < i \leq k$, we have $F(p_1,b_1,N) < F(p_i,b_i,N)$.

You may ask: Out of what blue did these conjectures arise? The context is a not-very-deep discussion of how to calculate the number of trailing zeros of $N!$ written in various bases. You can see it, including the use of these conjectures, here: http://denenberg.com/fzeros.pdf .

1 Answers 1

1

Is the following not a counterexample to conjecture 1? $N=27$, $p_1=3$, $b_1=13$. Here $\hat{F}(3,13,1)=1/((3-1)13)=1/26$, and $F(3,13,27)=\left\lfloor(1/13)(9+3+1)\right\rfloor=1.$ OTOH, if $p_2=2$, $b_2=25$, then $\hat{F}(2,25,1)=1/((2-1)25)=1/25>\hat{F}(3,13,1)$. Yet we have $ F(2,25,27)=\left\lfloor(1/25)(13+6+3+1)\right\rfloor=0. $

The heuristic motivation in my search was to try an $(N,p_1,b_1)$ combination, where the floor-functions won't do much damage to the value of $F$. Then try a couple less fitting $(p_2,b_2)$ combos for that same $N$. So let $N$ be a power of $p_1$, find a $b_1$ such that it divides $\nu_{p_1}(N!)$, and take it from there.

This is not necessarily the smallest counterexample. I just happened to start my search from $(N,p_1)=(27,3)$.

[Edit] Smaller counterexamples:

$N=16,p_1=2,b_1=15$ gives $\hat{F}(2,15,1)=1/15$ and $F(2,15,16)=\lfloor(8+4+2+1)/15\rfloor=1.$ Choose $p_2=3, b_2=7$, so $\hat{F}(3,7,1)=1/14>1/15$, but $F(3,7,16)=\lfloor(5+1)/7\rfloor=0.$

$N=8,p_1=2,b_1=7$ gives $\hat{F}(2,7,1)=1/7$ and $F(2,7,8)=\lfloor(4+2+1)/7\rfloor=1.$ Choose $p_2=3, b_2=3$, so $\hat{F}(3,3,1)=1/6>1/7$, but $F(3,3,8)=\lfloor(2+0)/3\rfloor=0.$

Producing counterexamples with powers of primes doesn't seem to be too difficult, because one can tune up the parameters to help the side that is losing in the long run. A study of these will hopefully allow you to refine the conjecture?