heureka

avatar
Usernameheureka
Score26364
Membership
Stats
Questions 17
Answers 5678

 #1
avatar+26364 
+2

How many numbers between 1 and 1,000 have exactly 3 prime factors, not necessarily distinct

{such as 3^3, 2^2 x 5, 2 x 3 x 5........etc, are perfectly valid)?

 

I assume: 246

1.) 8 3
2.) 12 3
3.) 18 3
20 3
27 3
28 3
30 3
42 3
44 3
45 3
50 3
52 3
63 3
66 3
68 3
70 3
75 3
76 3
78 3
92 3
98 3
99 3
102 3
105 3
110 3
114 3
116 3
117 3
124 3
125 3
130 3
138 3
147 3
148 3
153 3
154 3
164 3
165 3
170 3
171 3
172 3
174 3
175 3
182 3
186 3
188 3
190 3
195 3
207 3
212 3
222 3
230 3
231 3
236 3
238 3
242 3
244 3
245 3
246 3
255 3
258 3
261 3
266 3
268 3
273 3
275 3
279 3
282 3
284 3
285 3
286 3
290 3
292 3
310 3
316 3
318 3
322 3
325 3
332 3
333 3
338 3
343 3
345 3
354 3
356 3
357 3
363 3
366 3
369 3
370 3
374 3
385 3
387 3
388 3
399 3
402 3
404 3
406 3
410 3
412 3
418 3
423 3
425 3
426 3
428 3
429 3
430 3
434 3
435 3
436 3
438 3
442 3
452 3
455 3
465 3
470 3
474 3
475 3
477 3
483 3
494 3
498 3
506 3
507 3
508 3
518 3
524 3
530 3
531 3
534 3
539 3
548 3
549 3
555 3
556 3
561 3
574 3
575 3
578 3
582 3
590 3
595 3
596 3
598 3
602 3
603 3
604 3
605 3
606 3
609 3
610 3
615 3
618 3
627 3
628 3
637 3
638 3
639 3
642 3
645 3
646 3
651 3
652 3
654 3
657 3
658 3
663 3
665 3
668 3
670 3
678 3
682 3
692 3
705 3
710 3
711 3
715 3
722 3
724 3
725 3
730 3
741 3
742 3
747 3
754 3
759 3
762 3
764 3
772 3
775 3
777 3
782 3
786 3
788 3
790 3
795 3
796 3
801 3
805 3
806 3
814 3
822 3
826 3
830 3
833 3
834 3
844 3
845 3
847 3
854 3
861 3
867 3
873 3
874 3
885 3
890 3
892 3
894 3
897 3
902 3
903 3
906 3
908 3
909 3
915 3
916 3
925 3
927 3
931 3
932 3
935 3
938 3
942 3
946 3
956 3
957 3
962 3
963 3
964 3
969 3
970 3
978 3
981 3
986 3
245.) 987 3
246.) 994 3

 

laugh

Jun 7, 2019
 #1
avatar+26364 
+4

sequence proof

 

\(\text{Let $\mathbf{y=1+x}$ or $\mathbf{x = y-1}$ }\)

\(\begin{array}{|rcll|} \hline f(x) &=& & \dfrac{1}{y} + \dfrac{2}{y^2} + \dfrac{3}{y^3} + \dfrac{4}{y^4} +\ldots + \dfrac{n-1}{y^{n-1}}+ \dfrac{n}{y^n} \quad | \quad \cdot y \\ yf(x) &=&1 +& \dfrac{2}{y } + \dfrac{3}{y^2} + \dfrac{4}{y^3} + \dfrac{5}{y^4} +\ldots + \dfrac{n}{y^{n-1}} \\ \hline yf(x)-f(x) &=& 1 + & \dfrac{1}{y } + \dfrac{1}{y^2} + \dfrac{1}{y^3} + \dfrac{1}{y^4} +\ldots + \dfrac{1}{y^{n-1}} - \dfrac{n}{y^n} \\ (y-1)f(x) &=& 1 + & \dfrac{1}{y } + \dfrac{1}{y^2} + \dfrac{1}{y^3} + \dfrac{1}{y^4} +\ldots + \dfrac{1}{y^{n-1}} - \dfrac{n}{y^n} \quad | \quad y-1 = x \\ xf(x) &=& 1 + & \dfrac{1}{y } + \dfrac{1}{y^2} + \dfrac{1}{y^3} + \dfrac{1}{y^4} +\ldots + \dfrac{1}{y^{n-1}} - \dfrac{n}{y^n} \\ \hline \end{array} \)

 

\(\begin{array}{|rclcl|} \hline xf(x) &=& \underbrace{1 + \dfrac{1}{y } + \dfrac{1}{y^2} + \dfrac{1}{y^3} + \dfrac{1}{y^4} +\ldots + \dfrac{1}{y^{n-1}}}_{=s~(\text{sum of a geometric progression})} - \dfrac{n}{y^n} \\ xf(x) &=& \mathbf{s} - \dfrac{n}{y^n} \\ \hline && \mathbf{s} = 1 + \dfrac{1}{y } + \dfrac{1}{y^2} + \dfrac{1}{y^3} + \dfrac{1}{y^4} +\ldots + \dfrac{1}{y^{n-1}} \quad | \quad : y \\ && \dfrac{\mathbf{s}}{y} = \quad \dfrac{1}{y } + \dfrac{1}{y^2} + \dfrac{1}{y^3} + \dfrac{1}{y^4} +\ldots + \dfrac{1}{y^{n-1}} + \dfrac{1}{y^{n}} \\ \hline && \mathbf{s}-\dfrac{\mathbf{s}}{y} = 1- \dfrac{1}{y^{n}} \\ && \mathbf{s}\left(1-\dfrac{1}{y}\right) = 1- \dfrac{1}{y^{n}} \\ && \mathbf{s} = \dfrac{1- \dfrac{1}{y^{n}}}{1-\dfrac{1}{y}} \\ \hline xf(x) &=& \mathbf{\dfrac{1- \dfrac{1}{y^{n}}}{1-\dfrac{1}{y}}} - \dfrac{n}{y^n} \quad | \quad y=1+x \\ \mathbf{xf(x)} &=& \mathbf{\dfrac{1- \dfrac{1}{(1+x)^{n}}}{1-\dfrac{1}{1+x}} - \dfrac{n}{(1+x)^n} } \\ \hline \end{array}\)

 

\(\begin{array}{|rcll|} \hline \mathbf{xf(x)} &=& \mathbf{\dfrac{1- \dfrac{1}{(1+x)^{n}}}{1-\dfrac{1}{1+x}} - \dfrac{n}{(1+x)^n} } \\ \\ xf(x) &=& \dfrac{ \dfrac{(1+x)^{n}-1}{(1+x)^{n}}} { \dfrac{1+x-1 }{1+x}} - \dfrac{n}{(1+x)^n} \\ \\ xf(x) &=& \dfrac{ \dfrac{(1+x)^{n}-1}{(1+x)^{n}}} { \dfrac{x}{1+x}} - \dfrac{n}{(1+x)^n} \\ \\ xf(x) &=& \dfrac{\Big( (1+x)^{n}-1 \Big)(1+x) } {x(1+x)^{n}} - \dfrac{n}{(1+x)^n}\cdot \dfrac{x}{x} \\ \\ xf(x) &=& \dfrac{\Big( (1+x)^{n}-1 \Big)(1+x)-nx } {x(1+x)^{n}} \quad | \quad : x \\ \\ f(x) &=& \dfrac{\Big( (1+x)^{n}-1 \Big)(1+x)-nx } {x^2(1+x)^{n}} \\ \\ \mathbf{f(x)} &=& \mathbf{ \dfrac{ (1+x)^{n+1}-(1+x)-nx } {x^2(1+x)^{n}} } \\ \hline \end{array}\)

 

laugh

Jun 5, 2019
 #1
avatar+26364 
+5

Find the least positive four-digit solution to the following system of congruences.

\(\begin{align*} 7x &\equiv 21 \pmod{14} \\ 2x+13 &\equiv 16 \pmod{9} \\ -2x+1 &\equiv x \pmod{25} \\ \end{align*}\)

 

\(\begin{array}{|lrcll|} \hline & \mathbf{7x} &\mathbf{\equiv}& \mathbf{ 21 \pmod{14}} \\ & 7x &\equiv& 21 -14 \pmod{14} \\ & 7x &\equiv& 7 \pmod{14} \\ & 7x &=& 7 +14n \quad & | \quad : 7 \\ \color{blue}(1) & \mathbf{ x} &=& \mathbf{ 1+2n } ~ \text{ and } ~ n \in \mathbb{Z}\qquad [~ \text{ or } ~x \equiv 1 \pmod{2} ] \\ \hline \end{array} \)

 

\(\begin{array}{|lrcll|} \hline & \mathbf{2x+13} &\mathbf{\equiv}& \mathbf{16 \pmod{9} } \\ & 2x & \equiv & 16 -13 \pmod{9} \\ & 2x & \equiv & 3 \pmod{9} \\ & 2x & = & 3 + 9m \\\\ & \mathbf{x } & = & \mathbf{\dfrac{3 + 9m}{2}} \\ & x &=& \dfrac{8m+m+2+1}{2} \\ & x &=& 4m+1+ \underbrace{\dfrac{ m+1}{2}}_{=a} \\ & x &=& 4m+1+ a & a = \dfrac{ m+1}{2} \\ & & & & 2a = m+1 \\ & & & & \mathbf{m =2a-1} \\ & x &=& 4(2a-1)+1+ a \\ & x &=& -3+9a \\ & x &\equiv& -3 \pmod{9} \\ & x &\equiv& -3+9 \pmod{9} \\ & x &\equiv& 6 \pmod{9} \\ \color{blue}(2) & \mathbf{ x} &=& \mathbf{ 6+9m } ~ \text{ and } ~ m \in \mathbb{Z} \\ \hline \end{array}\)

 

\(\begin{array}{|lrcll|} \hline & \mathbf{-2x+1} &\mathbf{\equiv}& \mathbf{x \pmod{25} } \\ & -2x+1 &=& x +25k \\ & -3x+1 &=& 25k \\ & 3x &=& 1-25k \\ & \mathbf{x } & = & \mathbf{\dfrac{1-25k}{3}} \\ & x &=& \dfrac{1-24k-k}{3} \\ & x &=& -8k +\underbrace{\dfrac{1-k}{3}}_{=a} \\ & x &=& -8k +a & a = \dfrac{1-k}{3} \\ & & & & 3a = 1-k \\ & & & & \mathbf{k =1-3a} \\ & x &=& -8(1-3a) +a \\ & x &=& -8+25a \\ & x &\equiv& -8 \pmod{25} \\ & x &\equiv& -8+25 \pmod{25} \\ & x &\equiv& 17 \pmod{25} \\ \color{blue}(3) & \mathbf{ x} &=& \mathbf{ 17+25k } ~ \text{ and } ~ k \in \mathbb{Z} \\ \hline \end{array}\)

 

The system of congruences is now:

\(\begin{array}{|rcll|} \hline \color{blue}(1) & \mathbf{ x} &=& \mathbf{ 1+2n } ~ \text{ and } ~ n \in \mathbb{Z}\qquad [~ \text{ or } ~x \equiv 1 \pmod{2} ] \\ \color{blue}(2) & \mathbf{ x} &=& \mathbf{ 6+9m } ~ \text{ and } ~ m \in \mathbb{Z}\qquad [~ \text{ or } ~x \equiv 6 \pmod{9} ] \\ \color{blue}(3) & \mathbf{ x} &=& \mathbf{ 17+25k } ~ \text{ and } ~ k \in \mathbb{Z}\qquad [~ \text{ or } ~x \equiv 17 \pmod{25} ] \\ \hline \end{array}\)

 

\(\begin{array}{|lrcll|} \hline \color{blue}(1) & \mathbf{ x} &=& \mathbf{ 1+2n } \\ \color{blue}(2) & \mathbf{ x} &=& \mathbf{ 6+9m } \\\\ & 1+2n &=& 6+9m \\ & 2n &=& 9m+5 \\ & \mathbf{ n } &=& \mathbf{\dfrac{ 9m+5 }{2}} \\ & n &=& \dfrac{8m+m+4+1}{2} \\ & n &=& 4m+2+\underbrace{\dfrac{ m+1}{2}}_{=a} \\ & n &=& 4m+2+a & a = \dfrac{ m+1}{2} \\ & & & & 2a = m+1 \\ & & & & \mathbf{m =2a-1} \\ & x &=& 6+9m \\ & x &=& 6+9(2a-1) \\ & x &=& -3+18a \\ & x &\equiv& -3 \pmod{18} \\ & x &\equiv& -3 +18\pmod{18} \\ & x &\equiv& 15 \pmod{18} \\ \color{blue}(4) & \mathbf{ x} &=& \mathbf{ 15+18z } ~ \text{ and } ~ z \in \mathbb{Z} \\ \hline \end{array} \)

 

The system of congruences is now:

\(\begin{array}{|lrcll|} \hline \color{blue}(4) & \mathbf{ x} &=& \mathbf{ 15+18z } ~ \text{ and } ~ z \in \mathbb{Z} & [~ \text{ or } ~x \equiv 15 \pmod{18} ] \\ \color{blue}(3) & \mathbf{ x} &=& \mathbf{ 17+25k } ~ \text{ and } ~ k \in \mathbb{Z} & [~ \text{ or } ~x \equiv 17 \pmod{25} ] \\\\ & 15+18z &=& 17+25k \\ & 18z &=& 2+25k \\ & \mathbf{z} &=& \mathbf{\dfrac{ 25k + 2 } {18}} \\ & z &=& \dfrac{18k+7k+2}{18} \\ & z &=& k+\underbrace{\dfrac{ 7k+2}{18}}_{=a} \\ & z &=& k+a & a = \dfrac{ 7k+2}{18} \\ & & & & 18a = 7k+2 \\ & & & & 7k = 18a-2 \\ & & & & k = \dfrac{18a-2}{7} \\ & & & & k = \dfrac{14a+4a-2}{7} \\ & & & & k = 2a+\underbrace{\dfrac{4a-2}{7}}_{=b} \quad | \quad \\ & & & & k = 2a+b & b = \dfrac{4a-2}{7} \\ & & & & & 7b = 4a-2 \\ & & & & & 4a = 7b+2 \\ & & & & & a = \dfrac{7b+2}{4} \\ & & & & & a = \dfrac{8b-b+2}{4} \\ & & & & & a = 2b+\underbrace{\dfrac{2-b}{4}}_{=c} \\ & & & & & a = 2b+c \qquad c = \dfrac{2-b}{4} \\ & & & & & \qquad\qquad \qquad 4c = 2-b \\ & & & & & \qquad \qquad \qquad \mathbf{b= 2-4c} \\ & & & & & a = 2(2-4c)+c \\ & & & & & \mathbf{a = 4-7c} \\ & & & & k = 2(4-7c)+ 2-4c \\ & & & & \mathbf{k = 10-18c} \\ & z &=& 10-18c+4-7c \\ &\mathbf{ z }&=& \mathbf{14-25c} \\ & x &=& 15+18z \\ & x &=& 15+18(14-25c) \\ & \mathbf{x} &=& \mathbf{267-450c} ~ \text{ and } ~ c \in \mathbb{Z} & [~ \text{ or } ~x \equiv 267 \pmod{450} ] \\ \hline \end{array}\)

 

The least positive four-digit solution:

\(\begin{array}{|rcll|} \hline 267-450c &>& 999 \\ -450c &>& 999-267 \\ -450c &>& 732 \quad & | \quad :(-450) \\ c &<& -\dfrac{732}{450} \\ c &<& -1.62666666667 \\ \hline \end{array}\)

\(\begin{array}{|rcll|} \hline x_{\text{4digit}} &=& 267 -450(-2) \\ x_{\text{4digit}} &=& 267 +900 \\ \mathbf{x_{\text{4digit}}} &=& \mathbf{1167} \\ \hline \end{array}\)

 

 

laugh

Jun 4, 2019