Product of f(m) multiple of odd integers

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Product of f(m) multiple of odd integers

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: China Team Selection Test 2016 Test 2 Day 2 Q4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

178 posts

#1 h Mar 21, 2016, 6:04 AM • 9 Y

Y by rkm0959, shinichiman, Dukejukem, anantmudgal09, doxuanlong15052000, Mathuzb, megarnie, Adventure10, Mango247

Set positive integer $m=2^k\cdot t$ , where $k$ is a non-negative integer, $t$ is an odd number, and let $f(m)=t^{1-k}$ . Prove that for any positive integer $n$ and for any positive odd number $a\le n$ , $\prod_{m=1}^n f(m)$ is a multiple of $a$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3212 posts

#2 h Mar 21, 2016, 8:28 AM • 4 Y

Y by doxuanlong15052000, TheBeatlesVN, Mockhuynh2501, Adventure10

Here is my solution.

Note that $\left \lfloor \frac{a}{p^i} \right \rfloor$ counts all multiples of $p^i$ that are less than or equal to $a$ . From this, we will have:

$\sum_{h=1} \left \lfloor \frac{n}{2^xp_i^h} \right \rfloor$ : number of $z=2^u \cdot v$ such that $p_i \mid z, z\le n$ and $v_2(z)=u \ge x$ .

$\sum_{h=1} \left \lfloor \frac{n}{2^x p_i^h} \right \rfloor - \sum_{j=1} \left \lfloor \frac{n}{2^{x+1}p_i^h} \right \rfloor$ : number of $z=2^u \cdot v$ such that $p_i \mid z,z\le n$ and $v_2(z)=x$ .

Thus, we will have $\begin{aligned} v_{p_i} \left( \prod_{m=1}^n f(m) \right) & = \sum_{x=0} (1-x) \left \{ \sum_{h=1} \left \lfloor \frac{n}{2^x p_i^h} \right \rfloor - \sum_{j=1} \left \lfloor \frac{n}{2^{x+1}p_i^j} \right \rfloor \right \}, \\ & = \sum_{h=1} \left \lfloor \frac{n}{p_i^h} \right \rfloor - \sum_{x=1} \sum_{h=1} \left \lfloor \frac{n}{2^xp_i^h} \right \rfloor, \\ & = \sum_{h=1}^k \left \lfloor \frac{n}{p_i^h} \right \rfloor - \sum_{x=1}\sum_{h=1}^k \left \lfloor \frac{n}{2^xp_i^h} \right \rfloor. \end{aligned}$ where $k \in \mathbb{N}$ satisfied $p_i^k<n<p_i^{k+1}$ .

In order to prove $a \mid \prod_{m=1}^nf(m)$ for all $2 \nmid a, a<n$ , we need to prove that $v_{p_i} \left( \prod_{m=1}^n f(m) \right) \ge k$ for all odd prime $p_i$ that is less than or equal to $n$ and $p_i^k<n<p_i^{k+1}$ . Indeed, we will prove a more simple version of this, which is $\left \lfloor \frac{n}{p_i} \right \rfloor - \sum_{x=1}^l \left \lfloor \frac{n}{2^xp_i} \right \rfloor \ge 1, \; \text{for} \; 2^lp_i<n<2^{l+1}p_i.$ Notice that $\left \lfloor 2a \right \rfloor = \left \lfloor a \right \rfloor + \left \lfloor a+ \tfrac 12 \right \rfloor \ge 2 \left \lfloor a \right \rfloor$ so $\begin{aligned} \left \lfloor \frac{n}{p_i} \right \rfloor & \ge 2 \left \lfloor \frac{n}{2p_i} \right \rfloor, \\ & \ge \left \lfloor \frac{n}{2p_i} \right \rfloor+ 2 \left \lfloor \frac{n}{2^2p_i} \right \rfloor, \\ & \ge ... \\ & \ge \sum_{x=1}^{l-1} \left \lfloor \frac{n}{2^{x}p_i} \right \rfloor+2 \left \lfloor \frac{n}{2^lp_i} \right \rfloor, \\ & \ge \sum_{x=1}^l \left \lfloor \frac{n}{2^xp_i} \right \rfloor+1. \end{aligned}$ Therefore, $\begin{aligned} v_{p_i} \left( \prod_{m=1}^n f(m) \right) & = \sum_{h=1}^k \left \{ \left \lfloor \frac{n}{p_i^h} \right \rfloor - \sum_{x=1} \left \lfloor\frac{n}{2^xp_i^h} \right \rfloor \right \}, \\ & \ge k. \end{aligned}$ From this, the statement of the problem follows. $\blacksquare$

This post has been edited 4 times. Last edited by shinichiman, Mar 22, 2016, 9:58 AM
Reason: changing the latex from \left[ to \left \lfloor

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

695 posts

#3 h Mar 22, 2016, 4:03 AM • 3 Y

Y by AlastorMoody, hakN, Adventure10

Set $M = \prod_{m = 1}^n f(m).$ It's enough to show that for an arbitrary odd prime $p \le n$ , the inequality $\nu_p(M) \ge \nu_p(a)$ holds.

Choose $x, y \in \mathbb{N}_0$ so that $p^x \le n < p^{x + 1}$ and $2^y \le n < 2^{y + 1}.$ For $i \ge 1$ , define indicator variables $\alpha_i, \beta_i$ on $\mathbb{N}$ by
$\begin{align*} \alpha_i(k) = \begin{cases} 1 & \text{if } p^i \mid k \\ 0 & \text{otherwise} \end{cases} \\ \beta_i(k) = \begin{cases} 1 & \text{if } 2^i \mid k \\ 0 & \text{otherwise} \end{cases} \end{align*}$
Now, we are ready for the calculation. Put $A = \sum_{m = 1}^n \nu_p(m)$ and $B = \sum_{m = 1}^n \nu_p(m)\nu_2(m)$ so that
$\begin{align*} \nu_p(M) = \sum_{m = 1}^n \nu_p\left(f(m)\right) = \sum_{m = 1}^n \nu_p(m)\big(1 - \nu_2(m)\big) = A - B. \end{align*}$ Computation of A
Computation of B
Finish

Remark: This calculation is similar to the one used to prove Legendre's Formula.

This post has been edited 3 times. Last edited by Dukejukem, Mar 22, 2016, 3:05 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1671 posts

pad

#4 h Dec 9, 2019, 2:04 AM • 2 Y

Y by Pluto1708, Adventure10

Take some odd prime $p\mid a$ . Notice
$\begin{align*} f(n) = \left(\frac{n}{2^{\nu_2(n)}}\right)^{1-\nu_2(n)} \implies \nu_p(f(n)) &= (1-\nu_2(n))[\nu_p(n) - \nu_2(n)\nu_p(2)] \\ &= (1-\nu_2(n))\nu_p(n). \end{align*}$ Now,
$\begin{align*} \nu_p(f(1)\cdots f(m)) =\sum_{n=1}^m \nu_p(f(n)) &= \sum_{n=1}^m [\nu_p(n) - \nu_2(n)\nu_p(n)] \\ &= \sum_{n=1}^m \nu_p(n) - \sum_{n=1}^m \nu_2(n)\nu_p(n) \\ &= \sum_{i \ge 1} \left\lfloor \frac{m}{p^i} \right\rfloor - \sum_{n=1}^m \nu_2(n)\nu_p(n). \end{align*}$ But by an easy double counting argument, we see that
$\sum_{n=1}^m \nu_2(n) \nu_p(n) = \sum_{i\ge 1} \sum_{j\ge 1} \left\lfloor \frac{n}{2^ip^j} \right\rfloor.$ The highest $\nu_p(a)$ for $a$ ranging over all odds at most $m$ is $\lfloor \log_p(m) \rfloor$ . We want to show
$\begin{align*} &\sum_{i \ge 1} \left\lfloor \frac{m}{p^i} \right\rfloor - \sum_{i\ge 1} \sum_{j\ge 1} \left\lfloor \frac{n}{2^ip^j} \right\rfloor \ge \lfloor \log_p(m) \rfloor \\ &\sum_{i\ge 1} \sum_{j\ge 1} \left\lfloor \frac{n}{p^i2^j} \right\rfloor \le \left(\sum_{i\ge 1} \left\lfloor \frac{m}{p^i} \right\rfloor \right) - \lfloor \log_p(m) \rfloor . \end{align*}$ For $i$ fixed,
$\sum_{j\ge 1} \left\lfloor \frac{n}{p^i2^j} \right\rfloor \le \left\lfloor \frac{n}{p^i} \right\rfloor \sum_{j\ge 1} \frac{1}{2^j} < \left\lfloor \frac{n}{p^i} \right\rfloor.$ But both sides are integers, so
$\sum_{i\ge 1} \sum_{j\ge 1} \left\lfloor \frac{n}{p^i2^j} \right\rfloor \le \sum_{i\ge 1} \left( \left\lfloor \frac{n}{p^i} \right\rfloor -1 \right) = \left( \sum_{i\ge 1} \left\lfloor \frac{n}{p^i} \right\rfloor \right) - \lfloor \log_p(m) \rfloor.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

804 posts

#5 h Dec 9, 2019, 4:41 AM • 1 Y

Y by Adventure10

shinichiman wrote:

Here is my solution.

Note that $\left \lfloor \frac{a}{p^i} \right \rfloor$ counts all multiples of $p^i$ that are less than or equal to $a$ . From this, we will have:

$\sum_{h=1} \left \lfloor \frac{n}{2^xp_i^h} \right \rfloor$ : number of $z=2^u \cdot v$ such that $p_i \mid z, z\le n$ and $v_2(z)=u \ge x$ .

$\sum_{h=1} \left \lfloor \frac{n}{2^x p_i^h} \right \rfloor - \sum_{j=1} \left \lfloor \frac{n}{2^{x+1}p_i^h} \right \rfloor$ : number of $z=2^u \cdot v$ such that $p_i \mid z,z\le n$ and $v_2(z)=x$ .

Thus, we will have $\begin{aligned} v_{p_i} \left( \prod_{m=1}^n f(m) \right) & = \sum_{x=0} (1-x) \left \{ \sum_{h=1} \left \lfloor \frac{n}{2^x p_i^h} \right \rfloor - \sum_{j=1} \left \lfloor \frac{n}{2^{x+1}p_i^j} \right \rfloor \right \}, \\ & = \sum_{h=1} \left \lfloor \frac{n}{p_i^h} \right \rfloor - \sum_{x=1} \sum_{h=1} \left \lfloor \frac{n}{2^xp_i^h} \right \rfloor, \\ & = \sum_{h=1}^k \left \lfloor \frac{n}{p_i^h} \right \rfloor - \sum_{x=1}\sum_{h=1}^k \left \lfloor \frac{n}{2^xp_i^h} \right \rfloor. \end{aligned}$ where $k \in \mathbb{N}$ satisfied $p_i^k<n<p_i^{k+1}$ .

In order to prove $a \mid \prod_{m=1}^nf(m)$ for all $2 \nmid a, a<n$ , we need to prove that $v_{p_i} \left( \prod_{m=1}^n f(m) \right) \ge k$ for all odd prime $p_i$ that is less than or equal to $n$ and $p_i^k<n<p_i^{k+1}$ . Indeed, we will prove a more simple version of this, which is $\left \lfloor \frac{n}{p_i} \right \rfloor - \sum_{x=1}^l \left \lfloor \frac{n}{2^xp_i} \right \rfloor \ge 1, \; \text{for} \; 2^lp_i<n<2^{l+1}p_i.$ Notice that $\left \lfloor 2a \right \rfloor = \left \lfloor a \right \rfloor + \left \lfloor a+ \tfrac 12 \right \rfloor \ge 2 \left \lfloor a \right \rfloor$ so $\begin{aligned} \left \lfloor \frac{n}{p_i} \right \rfloor & \ge 2 \left \lfloor \frac{n}{2p_i} \right \rfloor, \\ & \ge \left \lfloor \frac{n}{2p_i} \right \rfloor+ 2 \left \lfloor \frac{n}{2^2p_i} \right \rfloor, \\ & \ge ... \\ & \ge \sum_{x=1}^{l-1} \left \lfloor \frac{n}{2^{x}p_i} \right \rfloor+2 \left \lfloor \frac{n}{2^lp_i} \right \rfloor, \\ & \ge \sum_{x=1}^l \left \lfloor \frac{n}{2^xp_i} \right \rfloor+1. \end{aligned}$ Therefore, $\begin{aligned} v_{p_i} \left( \prod_{m=1}^n f(m) \right) & = \sum_{h=1}^k \left \{ \left \lfloor \frac{n}{p_i^h} \right \rfloor - \sum_{x=1} \left \lfloor\frac{n}{2^xp_i^h} \right \rfloor \right \}, \\ & \ge k. \end{aligned}$ From this, the statement of the problem follows. $\blacksquare$

I understand the fundamental for the claim but what are you using to give bashed the series? I'm lost in things like the last $2$ lines where you get a limit $1$ or I can't got it in the best... If you have the topics for working with series like these I'll appreciate that you share it

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

452 posts

aops29

#6 h Jan 29, 2020, 8:02 AM • 2 Y

Y by AlastorMoody, Adventure10

I had to attach my solution because I had defined

\floor{}

as a macro locally... it doesn't work on AoPS.

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2785 posts

#7 h Mar 29, 2020, 5:01 PM

Y by

Note $f(m)=\frac{m^{1-\nu_2(m)}}{2^{\nu_2(m)-\nu_2(m)^2}}$ . Let $S=\prod_{k=1}^m f(k)=\frac{\prod_{k=1}^m k^{1-\nu_2(k)}}{2^{\sum_{k=1}^m (\nu_2(k)-\nu_2(k)^2)}}$ . First we prove $\nu_2(S)\ge 0$ . To see this, note that $\nu_2(\prod_{k=1}^m k^{1-\nu_2(k)})=\sum_{k=1}^m (\nu_2(k)-\nu_2(k^{\nu_2(k)})=\sum_{k=1}^m (\nu_2(k)-\nu_2(k)^2)$ , meaning that $\nu_2(S)$ is exactly 0.

Next, suppose we have arbitrary prime $p$ ; then, we will prove $\nu_p(S)\ge z$ where $z=\lfloor \log_p m\rfloor$ (note this is enough to finish the problem). Because $\nu_p(S)=\sum_{k=1}^m (1-\nu_2(k))\nu_p(k)$ , what we are trying to prove is equivalent to $\nu_p(m!)\ge \sum_{k=1}^m \nu_2(k)\nu_p(k)+z$ . By Legendre's, $\nu_p(m!)=\sum_{j=1}^{z} \lfloor \frac{n}{p^j} \rfloor$ . By a double-counting argument that's basically the 2-D version of the one used to prove Legendre, we get $\sum_{k=1}^m \nu_2(k)\nu_p(k)=\sum_{1\le i, 1\le j\le z} \lfloor \frac{n}{2^i5^j}\rfloor$ . Hence, we desire to prove $\sum_{j=1}^z (\lfloor \frac{m}{p^j}\rfloor-\sum_{i=1}^{\infty} \lfloor \frac{m}{2^ip^j}\rfloor)\le z$ .

To prove this, it suffices to prove for all $j\in [1, z]$ , $\lfloor \frac{m}{p^j}\rfloor >\sum_{i=1}^{\infty} \frac{m}{2^ip^j}$ , which is equivalent to $\sum_{i=1}^{\infty} \{\frac{m}{2^ip^j}\}>\{\frac{m}{p^j}\}$ . Letting $m\equiv r\pmod{p^j}$ , we see that $m\pmod{2^ip^j}\ge r$ , so $\sum_{i=1}^{\infty} \{\frac{m}{2^ip^j}\}\ge \frac{r}{2p^j}+\frac{r}{4p^j}+...=\frac{r}{p^j}$ , and equality can hold only if $m=r$ . But this is not possible unless $j=z$ and $m\in (p^z, 2p^z)$ , but in this case the overall sum is balanced out by an earlier $j$ . Hence, we are now done with the problem.

This post has been edited 2 times. Last edited by Stormersyle, Mar 29, 2020, 5:03 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

168 posts

#8 h Apr 18, 2020, 4:21 PM • 4 Y

Y by mathematicsy, JAKE_PERALTA, centslordm, mathitoo

Nice problem! Here's a quite different solution:

Let $p$ be an odd prime and define $G_p(n)=v_p(\prod_{m=1}^n f(m))=\sum_{m=1}^n v_p(m)-v_2(m)v_p(m).$ Let $\alpha_p(n)$ be such that $p^{\alpha_p(n)} \le n < p^{\alpha_p(n)+1}.$
We want $G_p(n) \ge \alpha_p(n)$ for all $n \in \mathbb{N}.$

The main ideia is the following:
Lemma: $G_p(2n+1)-v_p(2n+1) \ge G_p(2n)= G_p(n)+ v_p(\binom{2k}{k}).$
Proof: Indeed, $G_p(2n+1)-v_p(2n+1) \ge G_p(2n)=\sum_{m \le 2n} v_p(m)- \sum_{2m \le 2n} v_2(2m)v_p(2m)$ $= v_p((2n)!)- \sum_{m=1}^n (v_2(m)v_p(m)+v_p(m))= v_p(\binom{2n}{n})+2v_p(n!)-(\sum_{m=1}^n v_2(m)v_p(m)) - v_p(n!)$ $= v_p(\binom{2n}{n})+G_p(n). \Box$
Now, if $\alpha_p(2n)=\alpha_p(n)+1$ , then $\{n/p^{\alpha_p(n)} \}>1/2$ so $v_p(\binom{2n}{n}) \ge 1$ , which implies $G_p(2n) \ge G_p(n)+1$ , then $G_p(2n)-\alpha_p(2n) \ge G_p(n)-\alpha_p(n).$
If $2n+1=p^{\alpha_p(n)+1}$ , then we clearly have $G_p(2n+1)-\alpha_p(2n+1) = \alpha_p(n)+G_p(2n)-\alpha_p(2n).$
So we always have $G_p(2n+1)-\alpha_p(2n+1) \ge G_p(2n)-\alpha_p(2n) \ge G_p(n)-\alpha_p(n)$ and we are done by induction since $G_p(1)-\alpha_p(1) \ge 0. \blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2125 posts

#9 h Apr 18, 2020, 6:00 PM • 1 Y

Y by SenatorPauline

Storage

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1065 posts

Eyed

#10 h May 31, 2020, 4:52 AM

Y by

Lemma 1: $a\geq 1+\lfloor\frac{a}{2}\rfloor + \lfloor\frac{a}{4}\rfloor + \ldots$ for $a\in \mathbb{Z}_{>0}$ .

Proof:
$\lfloor\frac{a}{2}\rfloor + \lfloor\frac{a}{4}\rfloor + \ldots$ $< \frac{a}{2} + \frac{a}{4} + \ldots$ $=a$ Since $a\in \mathbb{Z}_{>0}$ , we are done.

Lemma 2: $\sum_{k=1}^{m}v_{p}(k)v_{2}(k)$
$= \lfloor\frac{\lfloor\frac{m}{p}\rfloor}{2}\rfloor + \lfloor\frac{\lfloor\frac{m}{p}\rfloor}{4}\rfloor + \ldots$ $+\lfloor\frac{\lfloor\frac{m}{p^{2}}\rfloor}{2}\rfloor + \lfloor\frac{\lfloor\frac{m}{p^{2}}\rfloor}{4}\rfloor + \ldots$ $+\ldots$
Proof: We have:
$\sum_{k=1}^{m}v_{p}(k)v_{2}(k)$ $=\sum_{k=1}^{\lfloor\frac{m}{p}\rfloor} v_{2}(k) + \sum_{k=1}^{\lfloor\frac{m}{p^{2}}\rfloor} v_{2}(k) + \ldots$ because for each $k$ where $v_{p}(k) = r$ , then $k$ is already counted $r-1$ times in the previous sums. This becomes:
$\sum_{k=1}^{\infty}v_{2}\left(\lfloor\frac{m}{p^{k}}\rfloor!\right)$ $= \lfloor\frac{\lfloor\frac{m}{p}\rfloor}{2}\rfloor + \lfloor\frac{\lfloor\frac{m}{p}\rfloor}{4}\rfloor + \ldots$ $+\lfloor\frac{\lfloor\frac{m}{p^{2}}\rfloor}{2}\rfloor + \lfloor\frac{\lfloor\frac{m}{p^{2}}\rfloor}{4}\rfloor + \ldots$ $+\ldots$
We move onto to problem. Let $p$ be a prime, and let $\log_{p}(m) = c$ . I claim that
$v_{p}\left(\prod_{k=1}^{m}f(k)\right)\geq c$ This is because, we have
$v_{p}\left(\prod_{k=1}^{m}f(k)\right)$ $=\sum_{k=1}^{m}v_{p}(f(k))$ $=\sum_{k=1}^{m}v_{p}(k)(1-v_{2}(k))$ $=\sum_{k=1}^{m}v_{p}(k) - \sum_{k=1}^{m}v_{2}v_{p}(k)$ $=\lfloor\frac{m}{p}\rfloor + \lfloor\frac{m}{p^{2}}\rfloor + \ldots$ $- \lfloor\frac{\lfloor\frac{m}{p}\rfloor}{2}\rfloor + \lfloor\frac{\lfloor\frac{m}{p}\rfloor{4}}\rfloor + \ldots$ $+\lfloor\frac{\lfloor\frac{m}{p^{2}}\rfloor}{2}\rfloor + \lfloor\frac{\lfloor\frac{m}{p^{2}}\rfloor}{4}\rfloor + \ldots\text{ By Lemma 2}$ $=\sum_{k=1}^{\infty}\left[\lfloor\frac{m}{p^{k}}\rfloor - \sum_{l=1}^{\infty}\lfloor\frac{\lfloor\frac{m}{p^{k}}\rfloor}{2^{l}}\rfloor\right]$ $\geq \sum_{k=1}^{c} 1\text{ by Lemma 1}$ $=c$ Then, since $v_{p}(a)\leq c$ for all $a\leq m$ , we are finished.

This post has been edited 1 time. Last edited by Eyed, May 31, 2020, 4:53 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2726 posts

#11 h Sep 8, 2020, 6:49 PM

Y by

It suffices to show for all odd primes $p \leq m$ that $v_p[f(1)\ldots f(m)] \geq \lfloor \log_{p} m\rfloor$ . Now that we know what to do, the rest of the problem is just a direct bash. Simplifications give $v_p\left[\prod_{i = 1}^m f(m)\right] = \sum_{i = 1}^m v_p[f(i)] = \sum_{i =1}^m \left((1 - v_2[i]) \cdot v_p\left[\frac{i}{2^{v_2[i]}}\right]\right) = \sum_{i = 1}^m v_p[i] - \sum_{i = 1}^m v_2[i]v_p[i]$ so it suffices to show $\sum_{i = 1}^m v_p[i] - \sum_{i = 1}^m v_2[i]v_p[i] \geq \lfloor \log_{p} m\rfloor$ for odd primes $p \leq m$ . A pretty conventional double count gives that $\sum_{i = 1}^m v_p[i] = v_p[m!] = \sum_{i = 1}^{\infty} \left\lfloor\frac{m}{p^i}\right\rfloor$ and a second double count gives that $\sum_{i = 1}^m v_2[i]v_p[i] = v_p[1^{v_2[1]} \cdot 2^{v_2[2]} \cdot \ldots \cdot m^{v_2[m]}] = v_p[m!!] + v_p[m!!!] + \ldots$ where $m!\ldots !$ followed by $n$ exclamation marks denotes the product of all $i \leq m$ divisible by $2^{n - 1}$ . Notice that we can kill all the twos in the prime factorization of $m!!, m!!!,$ and so on since $p$ is odd. Hence, we see that $v_p[m\underbrace{!\ldots !}_{i+1}] = v_p\left[\left\lfloor \frac{m}{2^i}\right\rfloor !\right] = \left\lfloor\frac{\left\lfloor\frac{m}{2^i}\right\rfloor}{p^j}\right\rfloor$ so we can rewrite $\sum_{i = 1}^m v_2[i]v_p[i] = \sum_{j = 1}^{\infty} \sum_{i = 1}^{\infty} \left\lfloor\frac{\left\lfloor\frac{m}{2^i}\right\rfloor}{p^j}\right\rfloor$ and therefore it remains to prove that $\sum_{j = 1}^{\infty} \left(\left\lfloor \frac{m}{p^j} \right\rfloor - \sum_{i = 1}^{\infty} \left\lfloor\frac{\left\lfloor\frac{m}{2^i}\right\rfloor}{p^j}\right\rfloor\right) \geq \lfloor \log_p{m}\rfloor.$ For $j > \lfloor \log_p{m}\rfloor$ it is clear that the object inside the parenthesis is zero since both terms are zero. Hence we may replace the outer sum bound of $\infty$ with $\lfloor \log_p{m}\rfloor$ . Lastly, note that for all $j$ , $\left\lfloor \frac{m}{p^j} \right\rfloor > \sum_{i = 1}^{\infty} \left\lfloor\frac{\left\lfloor\frac{m}{p^j}\right\rfloor}{2^i}\right\rfloor = \sum_{i = 1}^{\infty} \left\lfloor\frac{\left\lfloor\frac{m}{2^i}\right\rfloor}{p^j}\right\rfloor \implies \left\lfloor \frac{m}{p^j} \right\rfloor - \sum_{i = 1}^{\infty} \left\lfloor\frac{\left\lfloor\frac{m}{2^i}\right\rfloor}{p^j}\right\rfloor \geq 1$ hence in our final sum, each term is $\geq 1$ and since there are $\lfloor \log_p{m} \rfloor$ nonzero terms we arrive at the bound. $\blacksquare$

Remark: Terrible bash but a good exercise.

This post has been edited 1 time. Last edited by jj_ca888, Sep 8, 2020, 6:49 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1184 posts

L567

#12 h Aug 31, 2021, 9:05 AM • 1 Y

Y by kamatadu

Solved with bora_olmez

It suffices to show the result for when $a$ is a prime power. So let $a = p^k$ be the largest power of $p$ which is $\le n$ . The only terms that contribute to the $v_p$ are the ones with $p | m$ so consider only those. Suppose $pl$ is the largest multiple of $p$ below $n$

We'll split the bounding into parts. First, consider the contributions by all multiples $pz$ with $1 \le z \le l$ , ignoring the possibility when $p | z$ , which we will deal with later.

The total $v_p$ of the product from this is $\sum_{z=1}^{l} (1 - v_2(z)) = l - \sum_{z=1}^{l} v_2(z) = l - v_2(l!)$ . But since $v_2(l!) = l - s_2(l)$ (Sum of digits in binary), this is just $s_2(l)$

Similarly, we can obtain that the contribution from when the $v_p$ is $2$ is $s_2 \left(\left \lfloor \frac{l}{p} \right \rfloor \right)$ and in general, when the $v_p$ is $c$ , then the contribution is $s_2 \left(\left \lfloor \frac{l}{p^{c-1}} \right \rfloor \right)$

So, the total $v_p$ of the product is $\sum_{c = 0}^{k-1} s_2 \left(\left \lfloor \frac{l}{p^{c-1}} \right \rfloor \right) \ge \sum_{c = 0}^{k-1} 1 = k$ , as desired. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

46 posts

#13 h Nov 17, 2021, 12:46 PM

Y by

Let $q$ be an odd prime power. We can see that if $\lfloor \frac{m}{q} \rfloor =t$ then we have that the amount of times we have $q$ in the product is $v_q=\lceil \frac {t}{2}\rceil - \lfloor \frac{t}{4} \rfloor -\lfloor \frac{t}{8} \rfloor - \cdots$ But we can clearly see that $\lfloor \frac{t}{4} \rfloor +\lfloor \frac{t}{8} \rfloor + \cdots < t(\frac{1}{4}+\frac18 + \cdots) = t\frac12 \leq \lceil \frac {t}{2}\rceil$ so we clearly have that $v_q\geq 1$ , implying that for each odd prime $p$ $v_p(f(1)f(2)\cdots f(m))\geq max(v_p(f(i))) \geq v_p(a)$ and thus $a|f(1)f(2)\cdots f(m)$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

579 posts

#14 h Dec 24, 2021, 7:11 PM

Y by

$\textbf{Claim: }$ For all prime powers $q\leq m$ , $\sum_{q\mid i,i\leq m} (1-v_2(i)) \geq 1$ .
$\textbf{Proof: }$ Let $g(i) = 1-v_2(i)$ and $h(m) = \sum_{i=1}^m g(i)$ . It is sufficient to show that $h(m)\geq 1$ for all $m$ . We claim that $h(m)$ is the number of 1s in the binary representation of $m$ . This is true by induction because when you add 1 to $m$ , the number of digits goes down by $v_2(m+1)$ and there's the new carryover, for a net change of $1-v_2(m+1)$ . $\square$ .

The conclusion clearly follows from this. Every prime power divisor of $a$ contributes at least one prime factor, which means that $f(1)\cdots f(m)$ matches all of $a$ 's $v_p$ values.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5000 posts

#15 h Apr 27, 2022, 6:41 PM

Y by

We begin with an important lemma:

Lemma: For all $n \geq 1$ we have
$\sum_{i=1}^n (1-\nu_2(n))\geq 1.$ Proof: It is sufficient to show that
$\sum_{k=1}^n \nu_2(k)<n,$ since the LHS is an integer. We count the LHS in the same way as used in the proof of Legendre's formula; it equals
$\sum_{i \geq 1} \left\lfloor\frac{n}{2^i}\right\rfloor<\sum_{i \geq 1} \frac{n}{2^i}=n,$ as desired. $\blacksquare$

Let $p \leq m$ be an odd prime, so $\nu_p(f(i))=(1-\nu_2(i))\nu_p(i)$ . Let $n \geq 1$ be the largest integer such that $p^n \leq m$ , so $n=\nu_p(\mathrm{lcm}(1,\ldots,m))$ . Now, again counting as in Legendre's,
$\begin{align*} \nu_p(f(1)\ldots f(m))&=\sum_{i=1}^m (1-\nu_2(i))\nu_p(i)\\ &=\sum_{j=1}^n j\sum_{k=1}^{\lfloor m/p^j\rfloor} (1-\nu_2(k))\\ &\geq \sum_{j=1}^n j=n \end{align*}$ where we reach the third line from the second with our lemma. Thus $p^n \mid f(1)\ldots f(m)$ . Since this is for any $p \leq m$ it follows that $\mathrm{lcm}(1,\ldots,m) \mid f(1)\ldots f(m)$ , which implies the desired result. $\blacksquare$

This post has been edited 1 time. Last edited by IAmTheHazard, Jun 7, 2022, 1:25 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1500 posts

#17 h Apr 13, 2023, 5:39 PM

Y by

In other words, $f(x) = \left(\frac{x}{2^{\nu_2(x)}}\right)^{1-\nu_2(x)}$ .

Fix $m$ and consider $\nu_p$ individually.
It remains to show that $\nu_p(f(1)f(2) \dots f(m)) \ge \left\lfloor\log_p(m)\right\rfloor$
Then,
$\nu_p(f(x)) = (1 - \nu_2(x))\nu_p(x)$ and
$\nu_p(f(1)f(2)\dots f(m)) = \sum_{i=0}^{m} (1 - \nu_2(i))\nu_p(i)$
Using the fact that for $a, b, c \ge 1$ we have
$\left\lfloor\frac{a}{bc}\right\rfloor = \left\lfloor\frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor$ the RHS is equal to
$\sum_{k=0}^\infty \left(\left\lfloor\frac{m}{p^k}\right\rfloor - \sum_{j=1}^\infty \left\lfloor\frac{m}{2^jp^k}\right\rfloor \right) \ge \left\lfloor\log_p(m)\right\rfloor$

This post has been edited 1 time. Last edited by YaoAOPS, Apr 21, 2024, 6:07 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

22 posts

#18 h Jul 17, 2023, 3:13 AM

Y by

Note that it is enough to prove that for arbitrary $p \geq 3$ , $p^\alpha \mid f(1)f(2) \cdots f(m)$ , where $\alpha = \left \lfloor \log_p m \right \rfloor$ . For arbitrary $q$ with $q^e \mid \mid n$ we can write out $\nu_q(f(n))$ as the following:

$\nu_q(f(n)) = e(1 - \nu_2(n)) = \nu_q(n) - \nu_q(n)\nu_2(n)).$
Denote $m_i = \left \lfloor \frac{m}{p^i} \right \rfloor > 0$ for $1 \leq i \leq \alpha$ . We then calculate $\nu_p(f(1) \cdots f(m))$ as follows:

$\begin{align*} \nu_p&(f(1) \cdots f(m)) = \nu_p(f(1)) + \cdots + \nu_p(f(m))\\ &= \sum_{n = 1}^m (\nu_p(n) - \nu_p(n)\nu_2(n)) \\ &= \sum_{i = 1}^\alpha \left \lfloor \frac{m}{p^i} \right \rfloor - \sum_{i = 1}^\alpha \sum_{j \geq 1} \left \lfloor \frac{m}{2^jp^i} \right \rfloor \\ &= \sum_{i = 1}^\alpha \left(m_i - \sum_{j \geq 1} \left \lfloor \frac{m_i}{2^j} \right \rfloor \right) \\ &= \sum_{i = 1}^\alpha \left(m_i - \nu_2(m_i!) \right) = \sum_{i = 1}^\alpha s_2(m_i) \\ &\geq \sum_{i = 1}^\alpha 1 = \alpha. \end{align*}$
And we're done. Note that in the second to last line $s_2(n)$ denotes the sum of digits of $n$ in binary.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

268 posts

#19 h Dec 12, 2023, 4:26 AM • 1 Y

Y by sixoneeight

Solved with xook and xonk, also known as sixoneeight and popop614.

Remark that for a fixed $n$ , we have that $\nu_p (f(n)) = \nu_p(n) (1 - \nu_2(n))$ .

Now,
$\begin{align*} \sum_{n = 1}^m \nu_p(n) (1 - \nu_2(n)) &= \sum_{n=1}^m \nu_p(n) - \sum_{n=1}^m \nu_p(n) \nu_2(n) \\ &= \sum_{j = 1}^\infty \left \lfloor \frac{m}{p^j} \right \rfloor - \sum_{j = 1}^{\log_p{m}} \sum_{p^j \mid n} \nu_2(n) \\ &= \sum_{j = 1}^\infty \left \lfloor \frac{m}{p^j} \right \rfloor - \sum_{j = 1}^{\log_p{m}} \sum_{k \le m/p^j} \nu_2 (k) \\ &= \sum_{j = 1}^\infty \left \lfloor \frac{m}{p^j} \right \rfloor - \sum_{j = 1}^{\log_p{m}} \sum_{i=1}^\infty \left \lfloor \frac{\left \lfloor \frac{m}{p^j} \right \rfloor}{2^i} \right \rfloor \\ &= \sum_{j = 1}^\infty \left \lfloor \frac{m}{p^j} \right \rfloor - \sum_{i = 1}^\infty \sum_{j = 1}^\infty \left \lfloor \frac{m}{2^ip^j} \right \rfloor \end{align*}$
Therefore we want to show
$\nu_p(m!) - \sum_{i=1}^\infty \sum_{j=1}^\infty \left \lfloor \frac{m}{2^ip^j} \right \rfloor \ge \lfloor \log_p (m). \rfloor$
It thus suffices to prove the inequality
$\left \lfloor \frac{m}{p^j} \right \rfloor \ge \sum_{i=1}^\infty \left \lfloor \frac {m}{2^ip^j} \right \rfloor + 1, \qquad j \le \lfloor \log_p(m) \rfloor$ whereupon summing it over $j$ we win.
Assume that it is true for $p^j \le m < 2^{\text{OOK}+1}p^j$ , where $\text{OOK}$ is some nonnegative integer. Observe that the weaker version of the inequality without the $+1$ is true for all integers $m$ because its the same thing as dropping the floors.

If $m = 2^{\text{OOK}+1}p^j$ , observe both sides are just easily equal.

Let $2^{\text{OOK}+1}p^j \le m < 2^{\text{OOK}+2}p^j$ . Let $m = 2^{\text{OOK}+1}p^j + n$ . Then
$\text{LHS} = 2^{\text{OOK}+1} + \left \lfloor \frac{n}{p^j} \right \rfloor \ge 1 + \sum_{i = 1}^{\text {OOK} + 1} \frac{2^{\text{OOK} + 1}p^j}{2^ip^j} + \sum_{i = 1}^\infty \left \lfloor \frac{n}{2^ip^j} \right \rfloor = \sum_{i=1}^{\infty} \left \lfloor \frac{m}{2^i p^j} \right \rfloor + 1$ We now verify that this is true for $p^j \le m < 2p^j$ . But this is easy since both sides are $1$ . Therefore, by induction, the inequality is true for $m \ge p^j$ , or precisely $\log_p m \ge j$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8857 posts

#20 h Dec 26, 2023, 11:06 PM

Y by

Let $p$ be some prime factor of $a$ . Suppose that $pr \leq m < pr+1$ . It suffices to show that the sum $(\nu_p(i) + 1)(1-\nu_2(i))$ across $1 \leq i \leq r$ is positive.

Recalling that the number of integers with $\nu_2$ equal to $k$ less than $r$ is $\left \lfloor \frac{r+2^k}{2^{k+1}} \right \rfloor$ , it suffices to prove the inequality $\sum_{i=1}^{\lfloor \log_p r \rfloor} \sum_{k=1}^\infty i(k-1)\left \lfloor \frac{\left \lfloor \frac r{p^{i-1}}\right \rfloor+2^k}{2^{k+1}} \right \rfloor < \sum_{i=1}^{\lfloor \log_p r \rfloor} i\left \lfloor \frac{\left \lfloor \frac r{p^{i-1}} \right \rfloor+1}2 \right \rfloor.$ Here, we double-count layers as in Legendre's formula. So it suffices to show the inequality for each term, or $S = \sum_{k=1}^\infty (k-1) \left \lfloor \frac{r + 2^k}{2^{k+1}} \right \rfloor < \left \lfloor \frac{r+1}2\right \rfloor.$ By Legendre again, $S = \sum_{k=1}^\infty \left \lfloor \frac r{2^k} \right \rfloor - \left \lfloor \frac{r+2^k}{2^{k+1}} \right \rfloor$ as replacing the $k-1$ term with $k$ yields $\nu_2(r!)$ precisely. On the other hand, this is now clear because $\left \lfloor \frac r{2^k} \right \rfloor \leq \left \lfloor \frac{r+2^{k-1}}{2^k } \right \rfloor$ and equality occurs if and only if $r \bmod 2^k \in [0, 2^{k-1})$ . Now, if $r$ is odd, then $\left \lfloor \frac{r+1}2 \right \rfloor > \left \lfloor \frac r2\right \rfloor$ and it follows that $S = \left \lfloor \frac r2\right \rfloor + \sum_{k=1}^\infty \left \lfloor \frac r{2^{k+1}} \right \rfloor - \left \lfloor \frac{r+2^k}{2^{k+1}}\right \rfloor \leq \left \lfloor \frac r2\right \rfloor < \left \lfloor \frac{r+1}2\right \rfloor.$ When $r$ is even, taking $s = \nu_2(r)$ and $r = 2^st$ yields that $\left \lfloor \frac{r + 2^s}{2^{s+1}} \right \rfloor = \left \lfloor \frac{t+1}2 \right \rfloor > \left \lfloor \frac t2\right \rfloor =\left \lfloor \frac r{2^{s+1}} \right \rfloor$ so the inequality remains strict. This proves the result.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

662 posts

#21 h Jan 19, 2024, 12:36 PM

Y by

It suffices to show that $\sum_{i=1}^{\infty} \left(\left\lfloor \frac{m}{p^i} \right\rfloor - \sum_{j=0}^{\infty} \left\lfloor \frac{m}{2^jp^i} \right\rfloor\right) = \left(\left\lfloor \frac{m}{p} \right\rfloor - \left\lfloor \frac{m}{2p} \right\rfloor - \left\lfloor \frac{m}{4p} \right\rfloor - \ldots\right) + \left(\left\lfloor \frac{m}{p^2} \right\rfloor - \left\lfloor \frac{m}{2p^2} \right\rfloor - \left\lfloor \frac{m}{4p^2} \right\rfloor - \ldots\right) \cdots$ is atleast $\log_p$ , however this is trivial as each term is greater than equal to $1$ .

This post has been edited 1 time. Last edited by math_comb01, Oct 4, 2024, 4:58 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

792 posts

#22 h Oct 1, 2024, 7:09 PM

Y by

For an arbitrary prime $p$ , it suffices to show
$\begin{align*} \sum_{i=1}^{\infty} \left(\left\lfloor \frac{m}{p^i} \right\rfloor - \sum_{j=0}^{\infty} \left\lfloor \frac{m}{2^jp^i} \right\rfloor\right) &= \left(\left\lfloor \frac{m}{p} \right\rfloor - \left\lfloor \frac{m}{2p} \right\rfloor - \left\lfloor \frac{m}{4p} \right\rfloor - \ldots\right) \\ &+ \left(\left\lfloor \frac{m}{p^2} \right\rfloor - \left\lfloor \frac{m}{2p^2} \right\rfloor - \left\lfloor \frac{m}{4p^2} \right\rfloor - \ldots\right) \\ &+ \left(\left\lfloor \frac{m}{p^3} \right\rfloor - \left\lfloor \frac{m}{2p^3} \right\rfloor - \left\lfloor \frac{m}{4p^3} \right\rfloor - \ldots\right) \\ &+ \left(\ldots\right) \end{align*}$
is at least $\lfloor \log_pm \rfloor$ . But this follows from Legendre's, as each individual sum (of the nested sum) is at least 1 when $1 \leq i \leq \lfloor \log_pm \rfloor$ (and becomes 0 afterwards). $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

220 posts

kingu

#23 h Oct 25, 2024, 6:30 PM

Y by

It seems that I completely forgot to do this write-up. Gsolved with Shreyasharma.

Fix an odd prime $p$ , and notice that it suffices to show the result for prime powers, so assume $m = p^k$ . So, we will count the number of positive contributions and negative contributions to the product and show that $\sum_{i=1}^{p^k} \nu_p(f(i)) \ge k$ .
By a Legendre-like argument we can conclude that the positive terms in the sum will be
$\sum_{i=1}^{k} \left\lfloor \frac{p^k}{p^i} \right\rfloor = \sum_{i=1}^{k-1}p^i$ and the negative terms will be a similar reasoning be
$\sum_{i=1}\sum_{j=1}^{k}\left\lfloor \frac{p^k}{2^{i}p^{j}} \right\rfloor \le \sum_{i=1}\sum_{j=1}^{k}\frac{p^{k-j}-1}{2^{i}} = \sum_{j=1}^{k-1}(p^j - 1)$ From here it is clear to see that their difference is bigger than or equal to $k$ , as desired. $\Box$
Remark. $m = p^k$ is just aesthetic

This post has been edited 1 time. Last edited by kingu, Oct 25, 2024, 6:38 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

316 posts

#24 h Jan 29, 2025, 6:41 PM

Y by

It suffices to prove that for any odd prime $p,$ $f(1)f(2)\dots f(m)$ is divisible by $p^k$ where $p^k \leq m < p^{k + 1}.$

We can write
$\begin{align*} \nu_p\left(\prod_{i = 1}^m f(i)\right) & = \sum_{j = 1}^k (1 - j)\sum_{i = 1}^\infty \left(\left\lfloor \frac m{2^jp^i} \right\rfloor - \left\lfloor \frac m{2^{j + 1}p^i} \right\rfloor \right) \\ & = \sum_{i = 1}^k \left\lfloor \frac m{p^i} \right\rfloor - \sum_{j = 1}^\infty \sum_{i = 1}^k \left\lfloor \frac m{2^jp^i} \right\rfloor \\ & = \sum_{i = 1}^k \left(\left\lfloor \frac m{p^i}\right\rfloor - \sum_{j = 1}^\infty \left\lfloor \frac m{2^jp^i} \right\rfloor\right) \end{align*}$ Lemma: $\left\lfloor \frac m{p^i}\right\rfloor - \left\lfloor\sum_{j = 1}^\infty\frac m{2^j p^i}\right\rfloor \geq 1$ Proof: First, we sub $n = \left\lfloor\frac m{p^i}\right\rfloor$ . Assume $2^k \leq n < 2^{k + 1},$ so we prove $\left\lfloor n\right\rfloor - \sum_{j = 1}^k\left\lfloor\frac n{2^j}\right\rfloor \geq 1$

Note that $2\lfloor\alpha\rfloor \leq \lfloor 2\alpha\rfloor \leq 2\lfloor\alpha\rfloor + 1.$
$\begin{align*} \lfloor n\rfloor \geq 2\left\lfloor \frac n2\right\rfloor \\ & \geq \left\lfloor \frac n2\right\rfloor +2\left\lfloor \frac n4\right\rfloor \\ & \geq \sum_{i = 1}^k \left\lfloor \frac n{2^i}\right\rfloor + \left\lfloor \frac n{2^k}\right\rfloor \\ & = \sum_{i = 1}^k \left\lfloor \frac n{2^i}\right\rfloor + 1 \end{align*}$ which finishes.
The problem follows immediately.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4175 posts

#26 h Tuesday at 5:01 PM

Y by

The problem is essentially asking us to show that for any positive integer $m$ and odd prime $p$ , we have
$\sum_{n\leq m} v_p(n)(1-v_2(n))\geq \lfloor \log_p(m)\rfloor.$ We rewrite
$v_p(n)=\sum_{p^r\mid n}1$ so that this becomes
$\sum_{n\leq m} \sum_{p^r\mid n}(1-v_2(n))\geq \lfloor \log_p(m)\rfloor$ $\sum_{r} \sum_{p^r\mid n, n\leq m} (1-v_2(n))\geq \lfloor \log_p(m)\rfloor$ $\sum_{r} \sum_{a\leq \lfloor m/p^r\rfloor} (1-v_2(a))\geq \lfloor \log_p(m)\rfloor.$
Claim: All prefix sums of $1-v_2(n)$ are positive, meaning that the inner sum is at least $1$ as long as $p^r\leq m$ .

This is equivalent to showing that $v_2(n!)\leq n-1$ , but this is clearly true as $v_2(n!)=n-s_2(n)$ where $s_2$ is the sum of digits in binary.

Thus, since the inner sum is at least $1$ for $\lfloor \log_p(m)\rfloor$ values of $r$ (and $0$ for larger $r$ ), we are done.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a