Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2012 AMC 12B Problems/Problem 24"
(→‎Solution 2)
 
(23 intermediate revisions by 2 users not shown)
Line 2: Line 2:
  
 
Define the function <math>f_1</math> on the positive integers by setting <math>f_1(1)=1</math> and if <math>n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}</math> is the prime factorization of <math>n>1</math>, then <cmath>f_1(n)=(p_1+1)^{e_1-1}(p_2+1)^{e_2-1}\cdots (p_k+1)^{e_k-1}.</cmath>
 
Define the function <math>f_1</math> on the positive integers by setting <math>f_1(1)=1</math> and if <math>n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}</math> is the prime factorization of <math>n>1</math>, then <cmath>f_1(n)=(p_1+1)^{e_1-1}(p_2+1)^{e_2-1}\cdots (p_k+1)^{e_k-1}.</cmath>
−
For every <math>m\ge 2</math>, let <math>f_m(n)=f_1(f_{m-1}(n))</math>. For how many <math>N</math> in the range <math>1\le N\le 400</math> is the sequence <math>(f_1(N),f_2(N),f_3(N),\dots )</math> unbounded?
+
For every <math>m\ge 2</math>, let <math>f_m(n)=f_1(f_{m-1}(n))</math>. For how many <math>N</math>s in the range <math>1\le N\le 400</math> is the sequence <math>(f_1(N),f_2(N),f_3(N),\dots )</math> unbounded?
  
 
'''Note:''' A sequence of positive numbers is unbounded if for every integer <math>B</math>, there is a member of the sequence greater than <math>B</math>.
 
'''Note:''' A sequence of positive numbers is unbounded if for every integer <math>B</math>, there is a member of the sequence greater than <math>B</math>.
Line 8: Line 8:
 
<math>\textbf{(A)}\ 15\qquad\textbf{(B)}\ 16\qquad\textbf{(C)}\ 17\qquad\textbf{(D)}\ 18\qquad\textbf{(E)}\ 19 </math>
 
<math>\textbf{(A)}\ 15\qquad\textbf{(B)}\ 16\qquad\textbf{(C)}\ 17\qquad\textbf{(D)}\ 18\qquad\textbf{(E)}\ 19 </math>
  
−
== Solution ==
+
== Solution 1==
  
 
First of all, notice that for any odd prime <math>p</math>, the largest prime that divides <math>p+1</math> is no larger than <math>\frac{p+1}{2}</math>, therefore eventually the factorization of <math>f_k(N)</math> does not contain any prime larger than <math>3</math>. Also, note that <math>f_2(2^m) = f_1(3^{m-1})=2^{2m-4}</math>, when <math>m=4</math> it stays the same but when <math>m\geq 5</math> it grows indefinitely. Therefore any number <math>N</math> that is divisible by <math>2^5</math> or any number <math>N</math> such that <math>f_k(N)</math> is divisible by <math>2^5</math> makes the sequence <math>(f_1(N),f_2(N),f_3(N),\dots )</math> unbounded. There are <math>12</math> multiples of <math>2^5</math> within <math>400</math>. <math>2^4 5^2=400</math> also works: <math>f_2(2^4 5^2) = f_1(3^4 \cdot 2) = 2^6</math>.
 
First of all, notice that for any odd prime <math>p</math>, the largest prime that divides <math>p+1</math> is no larger than <math>\frac{p+1}{2}</math>, therefore eventually the factorization of <math>f_k(N)</math> does not contain any prime larger than <math>3</math>. Also, note that <math>f_2(2^m) = f_1(3^{m-1})=2^{2m-4}</math>, when <math>m=4</math> it stays the same but when <math>m\geq 5</math> it grows indefinitely. Therefore any number <math>N</math> that is divisible by <math>2^5</math> or any number <math>N</math> such that <math>f_k(N)</math> is divisible by <math>2^5</math> makes the sequence <math>(f_1(N),f_2(N),f_3(N),\dots )</math> unbounded. There are <math>12</math> multiples of <math>2^5</math> within <math>400</math>. <math>2^4 5^2=400</math> also works: <math>f_2(2^4 5^2) = f_1(3^4 \cdot 2) = 2^6</math>.
Line 27: Line 27:
  
 
In conclusion, there are <math>12+1+4+1=18</math> number of <math>N</math>'s ... <math>\framebox{D}</math>.
 
In conclusion, there are <math>12+1+4+1=18</math> number of <math>N</math>'s ... <math>\framebox{D}</math>.
 +
 +
== Solution 2==
 +
Say a number <math>n</math> is <math>\textit{boring}</math> if the sequence <math>\{f_k(n)\}</math> is bounded; otherwise <math>n</math> is <math>\textit{interesting}</math>.
 +
 +
It is clear that <math>n</math> is interesting iff <math>f_1(n)</math> is. For a prime, <math>p</math>, <math>f_1(p)=1</math>. Thus, for a prime, <math>p_k</math>, in the prime factorization of <math>n</math>; if <math>e_k=1</math> then <math>f_1(n)=f_1(n/p_k)</math>, so <math>n</math> is interesting iff <math>n/p_k</math> is. Continuing in this manner, we can divide <math>n</math> by all such primes <math>p_k</math> for which <math>e_k=1</math>; and <math>n</math> is interesting iff each of these resulting numbers are. Finally we will end up with a number  whose prime factorization  contains only exponents <math>\ge 2</math>. Let <math>S</math> be the set of such numbers. It suffices to find all interesting numbers in <math>S</math>; all other interesting numbers will be multiples of these. Note that  <math>f_1(n)\mid f_1(kn)</math> for all <math>k\in\mathbb{N}</math>; so by induction a multiple of an interesting number is also interesting.
 +
 +
The set <math>S</math> contains either powers of primes <math>\le 19</math>, or a product of two such powers.
 +
 +
We have <math>f_2(2^a)=f_1(3^{a-1}) = 2^{2(a-2)}</math>; since <math>2(a-2)> a</math> iff <math>a\ge 5</math>, so <math>2^5</math> and its multiples are interesting; there are <math>12</math> such.
 +
 +
We have <math>f_2(3^b)=f_1(2^{2(b-1)}) = 3^{2b-3}</math>; since <math>2b-3> b</math> iff <math>b\ge 4</math>, so <math>3^4</math> and its multiples are interesting; there are <math>4</math> such.
 +
 +
Among the remaining prime powers only <math>7^3 \textbf{ is interesting}</math> but it has no other multiples in <math>[400]</math>.
 +
 +
We are now left with numbers <math>n\in S</math> that are products of two prime powers, i.e <math>n=p^aq^b</math>, <math>a,b \ge 2</math>. 
 +
 +
We have <math>f_2(2^a3^b)= 2^{2(a-2)}3^{2b-3}</math>, so a number of this form is interesting iff <math>a\ge 5</math> or <math>b\ge 4</math>; they are already counted above.
 +
 +
If <math>5^2\mid n</math> then <math>n=2^2\cdot 5^2</math> or <math>2^3\cdot 5^2</math> or <math>3^2\cdot 5^2</math> (all boring) or <math>n=2^4\cdot 5^2=400</math>, <math>\textbf{which is interesting}</math>, but has no other multiples.
 +
 +
If <math>7^2\mid n</math> then <math>n</math> is <math>2^2\cdot 7^2</math> or <math>2^3\cdot 7^2</math> and both are boring.
 +
 +
No larger prime can divide <math>n</math> because even <math>11^2\cdot 2^2 > 400</math>.
 +
 +
We have found all the interesting numbers: <math>12</math> multiples of <math>2^5</math>, <math>4</math> multiples of <math>3^4</math>, <math>2^4\cdot 5^2</math>, and <math>7^3</math> for a total of <math>12+4+1+1= 18</math> ... <math>\framebox{D}</math>.
  
 
==Video Solution by Richard Rusczyk==
 
==Video Solution by Richard Rusczyk==

Latest revision as of 09:06, 5 November 2021

Problem

Define the function $f_1$ on the positive integers by setting $f_1(1)=1$ and if $n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ is the prime factorization of $n>1$, then \[f_1(n)=(p_1+1)^{e_1-1}(p_2+1)^{e_2-1}\cdots (p_k+1)^{e_k-1}.\] For every $m\ge 2$, let $f_m(n)=f_1(f_{m-1}(n))$. For how many $N$s in the range $1\le N\le 400$ is the sequence $(f_1(N),f_2(N),f_3(N),\dots )$ unbounded?

Note: A sequence of positive numbers is unbounded if for every integer $B$, there is a member of the sequence greater than $B$.

$\textbf{(A)}\ 15\qquad\textbf{(B)}\ 16\qquad\textbf{(C)}\ 17\qquad\textbf{(D)}\ 18\qquad\textbf{(E)}\ 19$

Solution 1

First of all, notice that for any odd prime $p$, the largest prime that divides $p+1$ is no larger than $\frac{p+1}{2}$, therefore eventually the factorization of $f_k(N)$ does not contain any prime larger than $3$. Also, note that $f_2(2^m) = f_1(3^{m-1})=2^{2m-4}$, when $m=4$ it stays the same but when $m\geq 5$ it grows indefinitely. Therefore any number $N$ that is divisible by $2^5$ or any number $N$ such that $f_k(N)$ is divisible by $2^5$ makes the sequence $(f_1(N),f_2(N),f_3(N),\dots )$ unbounded. There are $12$ multiples of $2^5$ within $400$. $2^4 5^2=400$ also works: $f_2(2^4 5^2) = f_1(3^4 \cdot 2) = 2^6$.

Now let's look at the other cases. Any first power of prime in a prime factorization will not contribute the unboundedness because $f_1(p^1)=(p+1)^0=1$. At least a square of prime is to contribute. So we test primes that are less than $\sqrt{400}=20$:

$f_1(3^4)=4^3=2^6$ works, therefore any number $\leq 400$ that are divisible by $3^4$ works: there are $4$ of them.

$3^3 \cdot Q^2$ could also work if $Q^2$ satisfies $2~|~f_1(Q^2)$, but $3^3 \cdot 5^2 > 400$.

$f_1(5^3)=6^2 = 2^2 3^2$ does not work.

$f_1(7^3)=8^2=2^6$ works. There are no other multiples of $7^3$ within $400$.

$7^2 \cdot Q^2$ could also work if $4~|~f_1(Q^2)$, but $7^2 \cdot 3^2 > 400$ already.

For number that are only divisible by $p=11, 13, 17, 19$, they don't work because none of these primes are such that $p+1$ could be a multiple of $2^5$ nor a multiple of $3^4$.

In conclusion, there are $12+1+4+1=18$ number of $N$'s ... $\framebox{D}$.

Solution 2

Say a number $n$ is $\textit{boring}$ if the sequence $\{f_k(n)\}$ is bounded; otherwise $n$ is $\textit{interesting}$.

It is clear that $n$ is interesting iff $f_1(n)$ is. For a prime, $p$, $f_1(p)=1$. Thus, for a prime, $p_k$, in the prime factorization of $n$; if $e_k=1$ then $f_1(n)=f_1(n/p_k)$, so $n$ is interesting iff $n/p_k$ is. Continuing in this manner, we can divide $n$ by all such primes $p_k$ for which $e_k=1$; and $n$ is interesting iff each of these resulting numbers are. Finally we will end up with a number whose prime factorization contains only exponents $\ge 2$. Let $S$ be the set of such numbers. It suffices to find all interesting numbers in $S$; all other interesting numbers will be multiples of these. Note that $f_1(n)\mid f_1(kn)$ for all $k\in\mathbb{N}$; so by induction a multiple of an interesting number is also interesting.

The set $S$ contains either powers of primes $\le 19$, or a product of two such powers.

We have $f_2(2^a)=f_1(3^{a-1}) = 2^{2(a-2)}$; since $2(a-2)> a$ iff $a\ge 5$, so $2^5$ and its multiples are interesting; there are $12$ such.

We have $f_2(3^b)=f_1(2^{2(b-1)}) = 3^{2b-3}$; since $2b-3> b$ iff $b\ge 4$, so $3^4$ and its multiples are interesting; there are $4$ such.

Among the remaining prime powers only $7^3 \textbf{ is interesting}$ but it has no other multiples in $[400]$.

We are now left with numbers $n\in S$ that are products of two prime powers, i.e $n=p^aq^b$, $a,b \ge 2$.

We have $f_2(2^a3^b)= 2^{2(a-2)}3^{2b-3}$, so a number of this form is interesting iff $a\ge 5$ or $b\ge 4$; they are already counted above.

If $5^2\mid n$ then $n=2^2\cdot 5^2$ or $2^3\cdot 5^2$ or $3^2\cdot 5^2$ (all boring) or $n=2^4\cdot 5^2=400$, $\textbf{which is interesting}$, but has no other multiples.

If $7^2\mid n$ then $n$ is $2^2\cdot 7^2$ or $2^3\cdot 7^2$ and both are boring.

No larger prime can divide $n$ because even $11^2\cdot 2^2 > 400$.

We have found all the interesting numbers: $12$ multiples of $2^5$, $4$ multiples of $3^4$, $2^4\cdot 5^2$, and $7^3$ for a total of $12+4+1+1= 18$ ... $\framebox{D}$.

Video Solution by Richard Rusczyk

https://artofproblemsolving.com/videos/amc/2012amc12b/276

~dolphin7


See Also

2012 AMC 12B (Problems • Answer Key • Resources)
Preceded by
Problem 23 		Followed by
Problem 25
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2012_AMC_12B_Problems/Problem_24&oldid=164649"