Take the 2-minute tour ×

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 .

share|improve this question
Srivatsan is correct (though I can no longer see his comments??). I've put in the factorial where necessary, also dropping the final paragraph (which was incorrect) and changing notation slightly for consistency with the discussion at the link. –  Larry Denenberg Sep 9 '11 at 20:44
Srivatsan probably deleted his comment, since your correction made it irrelevant; same thing I'm doing with my previous comment as well. (-: –  Arturo Magidin Sep 9 '11 at 20:59
Ah, thanks, I didn't realize this was the way to do things. So maybe all three (current) comments should go? Makes me a little uncomfortable to lose history this way. –  Larry Denenberg Sep 9 '11 at 21:19
We can leave these comments if you want; the "history" of the corrections is available in the "edited" link, though. –  Arturo Magidin Sep 9 '11 at 21:22
add comment

1 Answer

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?

share|improve this answer
add comment

Your Answer


