AoPS Academy
be an odd prime number. How many -element subsets 
of 
are there, the sum of whose elements is divisible by ?
be a positive integer. Ana and Banana play a game. Banana thinks of a function 
and a prime number 
. He tells Ana that 
is nonconstant, 
, and 
for all integers 
. Ana's goal is to determine the value of . She writes down integers 
. After seeing this list, Banana writes down 
in order. Ana wins if she can determine the value of from this information. Find the smallest value of for which Ana has a winning strategy.
be an integer, show that there are infinite perfect squares of the form 
, let 
be the number of ones in the binary representation of 
. What is the minimum value of ?
![$f \in C([0,1];[0,1])$](http://latex.artofproblemsolving.com/4/7/5/475518b7db0b787dd90b93f602c7b912c663fba3.png)
bijective, 
and ![$(a_k) \in [0,1]^\mathbb N$](http://latex.artofproblemsolving.com/a/d/8/ad8a80d847c60ee8e916a1f9b08b7b03ec17c814.png)
with 
converge.
converge?
, where 
. Verify by direct substitution that 
satisfies the quadratic equation 
and deduce that the value of is 
.
. Show that 
, show that the value of 
is 
.![$f\in C^1[a,b]$](http://latex.artofproblemsolving.com/8/4/8/848da12534d564560fe1cb016142159234be98b4.png)
, 
and suppose that 
, 
, is such that
for all ![$x\in [a,b]$](http://latex.artofproblemsolving.com/7/8/d/78d9dcd969a2c45f7cc9234aa1377b6ec1c2d5d3.png)
. Is it true that 
for all ?
is called perfect if the sum of its positive divisors 
is twice , that is, 
. For example, 
is a perfect number since the sum of its positive divisors is 
, which is twice . Prove that if is a positive perfect integer, then:![\[
\sum_{p|n} \frac{1}{p + 1} < \ln 2 < \sum_{p|n} \frac{1}{p - 1}
\]](http://latex.artofproblemsolving.com/0/c/0/0c08f527e87f7aae4ca5226f19bd084249551fe3.png)
where the sums are taken over all prime divisors 
of .
![$f\in C[0,b]$](http://latex.artofproblemsolving.com/8/9/8/898aec0300888e562794b7a551be34f5c2676236.png)
, 
and let 
be periodic with period 
. Prove that 
has a limit as 
and
where 
, 
, and 
are nonnegative integers.
and 
, define 
as the greatest exponent 
such that 
divides 
. Prove that there are infinitely many such that 
and infinitely many 
such that 
.
denote the sum of digits of in base . Then, by Legendre's formula
, so 
, which means 
. However, 
, so 
. Hence, we have 
.
, so 
, which means 
. However, 
, so 
. Hence, we have 
.
be the largest power of prime that divides a positive integer . Then, 
and 
.
for all positive integers , so 
Now, 
, so if 
is even, the 
s could pair among themselves to multiply to 
, giving 
. Otherwise, if is odd, there exists an unpaired , giving 
. 
such that either 
for all 
or 
for all . We work on each of these cases separately. For the former, consider some 
such that is a power of 
. Then, by Legendre's formula, we have 
where 
denotes the sum of digits of in base . It follows that 
, which implies that either 
or is a power of , and both possibilities are absurd.
such that 
is an even power of . Then, by Legendre's formula, 
However, 
for some nonnegative integer 
, so 
. It again follows that 
, or is a power of , contradiction. Thus, we are done. 
, where 
is the sum of the digits of expressed in base . Note that 
, and 
.
for infinetly many positive integers . Taking 
, 
suffices. Clearly, 
and , so the conclusion immediately follows (after all, the statement is true without the floors and adding the floor only adds potential to subtract from the RHS).
for infinetly many positive integers . Taking 
, suffices. Clearly, 
. Additionally, because 
, 
so the inequality rewrites to 
which is obviously true as powers of are never powers of . 
is unbounded in both directions. However, this is relatively straightforward - in addition to what has been done with the powers of and we need only prove that the sum of digits of powers of , is unbounded (but this is a short contradiction argument with a maximal digit sum).
satisfies 
, where is odd
, since 
s appear more frequently than s
by legendre
.
, since 
, so 
satisfies 
, where is odd
.
, since 
, so 
.
and 
, define to be the largest integer 
such divides . Prove that the sequence ![\[ E_{10}(1) - E_9(1), E_{10}(2) - E_9 (2), E_{10} (3) - E_9 (3), \ldots, \]](http://latex.artofproblemsolving.com/b/8/3/b83df57786b40714d92f59709d2b4b223f67c9fa.png)
has infinitely many positive elements and infinitely many negative elements.
. Since 
for all positive integers and , and 
.
, with equality iff is a power of ![\[\nu_p(n!) = \frac{n - s_p(n)}{p - 1} \le \frac{n-1}{p-1},\]](http://latex.artofproblemsolving.com/a/a/7/aa77561c6b5b7b746d87ca5417782a36243c7d43.png)
with equality iff 
, which happens when is a power of (where denotes the sum of digits of in base ). 
is a power of greater than 
, then we have that 
and since isn't a power of , 
. Hence ![\[E_{10}(n) = \nu_5(n!) > \frac{\nu_3(n!)}{2} \ge E_9(n),\]](http://latex.artofproblemsolving.com/3/3/c/33cb1dbe14ad74fdd579dda5a777d2c24c1b7dff.png)
so 
is positive whenever is a power of greater than . has infinitely many negative elements. We claim that is negative if is a power of greater than . Note that since isn't a power of , 
and 
. Since is a power of , 
, so is even. Thus, ![\[E_9(n) = \frac{n-1}{4} > \nu_5(n!) = E_{10}(n),\]](http://latex.artofproblemsolving.com/c/e/8/ce8b5f67ae2bd4c05c64e119d4f338112d23a0f4.png)
so must be negative, as desired.
for all primes and integers , where denotes the sum of the digits of in base .
. But since 
, we have .
for all integers .
.
for all integers .
.
and , define as the greatest exponent such that divides . Prove that there are infinitely many such that and infinitely many such that .
and 
. Let 
be the sum-of-digits base function., 
then 
so 
. This isn't true for 
and for 
it's easy to prove 
by induction. Thus if 
then 
and also 
. for 
. Then 
and 
so 
. And if we pick 
then similarly 
. This clearly implies the claim of the problem.
and 
.
for 
where 
.
Clearly there exists some integer 
such that 
. Again, by Legendre's theorem, we have
and since 
, we get that
for all as claimed.
for 
where .
from which it follows that 
, because 
. such that 
. Again, by Legendre's theorem, we have
and since 
, we get that
for all as claimed, and we are done. 
![\[E_{10}(n)=\nu_5(n)=\frac{n-s_5(n)}{4}\]](http://latex.artofproblemsolving.com/7/6/2/762af9503a2403eb2a0226a973648a99486925cf.png)
and![\[E_{9}(n)=\lfloor\nu_3(n)/2\rfloor=\left\lfloor\frac{n-s_3{n}}{4}\right\rfloor.\]](http://latex.artofproblemsolving.com/4/8/0/480f7e0827171b2bf8ad0e3e5b5df56370c2a491.png)
Thus we can use the classes of examples 
and 
, which clearly work. 
is unbounded both above and below. First I will show that it is unbounded above. We have that and we have that 
. for some , from the application of the legendre formula we obtain 
and we obtain that 
where is equal to the sum
in base 3, as is not a power of we get 
, now to prove the unbounded section, suppose has digits in base , there exists a 
such that
and 
, thus the first digits of in base are the same as the first digits of , however as 
there exists a digit 
after the -th digit in base in base , is strictly greater than the digit sum of . Thus we get is unbounded above, proving unbounded below is similar except instead of, 
is used.
in both directions. By Legendre's formula, the main expression we are interested in is![\[ \sum_{i=1}^{\infty} \left\lfloor \frac{n}{5^i} \right\rfloor - \left\lfloor \frac{1}{2}\sum_{i=1}^{\infty} \left\lfloor \frac{n}{3^i} \right\rfloor \right\rfloor \]](http://latex.artofproblemsolving.com/a/d/9/ad94a77b582cd02f3990e57be372721f866286a0.png)
since and 
, by comparing terms individually.
inequality 
same idea 
this sum goes to 
which yields 
you get the desired result 
where is the sum of digits of in base by legrende.
tells us 
while 
and we know 
be the sum of the digits of in base 
By Legendre's, 
consider for all positive integers 
We guarantee and 
consider for all positive integers We guarantee 
and 
Then, the floor does not affect anything as 
QED
Prove that
,![\[E_{10}(n) = \nu_{5}(n!) = \frac{n-s_5(n)}{4}\quad \text{and}\quad E_9(n) = \left\lfloor\frac{1}{2}\nu_3(n!)\right\rfloor = \left\lfloor \frac{n-s_3(n)}{4}\right\rfloor.\]](http://latex.artofproblemsolving.com/f/2/9/f295b87976543184dadbef99785f8de73b30cfcd.png)
Now for any 
,
to get 
to force 
denote the sum of the digits of 
for primes 
It therefore follows that
and we also have
Now, note that for 
we have
as desired, because 
is clearly always an integer for 
where 
as desired, because 
is clearly an integer for 
so we are done. 
be the largest power of 
and 
.
will take the least exponent out of those of its prime factors. Since 
for all 
.
.
is even, because in that case the 
.
such that one of the following is true:
for all 
for all 
such that 
This yields that 
so 
for some integer 
such that 
for some 
.
We notice that 
for some integer 
Therefore, we have that 
for some integer 
.
satisfies ![\[2E_9(n) = \left\lfloor\frac n3 \right\rfloor + \left\lfloor\frac n9 \right\rfloor + \cdots = \frac{n-1}{2} > \frac{n}{2} - \frac{8}{5} > 2E_{10}(n) = 2\left(\left\lfloor\frac n5 \right\rfloor + \cdots \right) \]](http://latex.artofproblemsolving.com/9/d/7/9d7d68cfe6cc9d1ba5e0e0f6c70f7ccb43f27543.png)
as 
.
satsfies ![\[2E_{10}(n) = 2(\left\lfloor\frac n5 \right\rfloor + \cdots) = \frac{n-1}{2} > \frac{n}{2} - \frac{4}{3} > 2E_{9}(n) = \left(\left\lfloor\frac n3 \right\rfloor + \cdots \right) \]](http://latex.artofproblemsolving.com/4/2/4/42421bfad6a9e8eba363f34ca51e9ac7154cf9e3.png)
as 
.
and 
so we take 
and it is also easy to see 
so we take 
and 
Since 
and 
,
From here it is clear that choosing 
for a positive integer 
.
(even 
)
,
for 
and 
for ![\[ \frac{5^{3^k}-1}{4} - \frac{1}{2}(5^{3^k} +1)\sum_{i=1}^k \frac{1}{3^i} + \frac{k}{2} - \frac{5^{3^k}}{2}\sum_{i=k+1}^{\infty}\frac{1}{3^i} = \frac{2k-2 + 3^{-k}}{4} \]](http://latex.artofproblemsolving.com/e/b/d/ebde940863c72c4c0333447125fe841df6ba6b78.png)
which can be unboundedly positive.
for a positive integer 
and the outside floor) is evaluated to 
(note that the outside floor actually disappears, as the ratio is an integer due to 
)
)
,
for 
for 
.![\[ (9^{5^k}+1)\sum_{i=1}^k \frac{1}{5^i} - k + 9^{5^k}\sum_{i=k+1}^{\infty}\frac{1}{5^i} - \frac{9^{5^k} - 1}{4} = \frac{2-5^{-k} - 4k}{4} \]](http://latex.artofproblemsolving.com/8/7/c/87ce80ecb5dec0bf4fec0de0a6b769c13b398c38.png)
which can be unboundedly negative.
for a positive integer 
.
Hence the overall upper bound is 
,
.
does not seem to work for the positive direction - calculations give the final constant at 
(We technically didn't even need Legendre!)
denote the sum of digits of 
which is equal to 1 and 
we get 
gives 
because 
,
gives 
where 
.
solves.
gives 
and 
gives the other 
i tried 
since 
and 
and since 