Here's the question you clicked on:
FoolForMath
Another cute number theory problem, Set \( N = 2^{10} \times 3^{9} \). If \( n\in \mathbb{N} \) and \( n|N^2 \), how many of \(n\) are there such that \(n<N\) but \( n \nmid N \) ?
I think you messed up the definition of "cute". IT does NOT mean devilishly hard.
how do you read n|N^2 ?? i seem to have forgotten
This is fun. Don't remove it, please. D:
Isnt N a number? How is it a set?
In this context, Set = let
Oh. Okay. Thanks!
Nothing is wild about this problem.
no ... i just find my logic too wild
I agree. There are certain things seeping into my brain.
@experimentx At least 15, man.
In the set of naturals, all numbers \(2^{i}\) with \(0\leq i \leq 9\) satisfy \(n < N\) and \(n \mid N\). Similarly, all numbers \(3^{i}\) with \(0\leq i \leq 9\). And likewise all values of \(f(i,j)=2^i3^j\) for all values of \(i\) and \(j\) between \(0\) and \(9\). This implies all \(n\) satisfying both \(n<N\) and \(n \nmid N\) cannot fall into either of those forms. However, I haven't fully understood the importance of the parameter \(n \mid N^2\)...
Is it 84? Am I even close?
Argh. There are minor details that I messed up just now.
Close, very close :) But then I would appreciate a general and formal solution.
I am getting the feeling that \(\{n: n\mid N^2 \wedge n<N \wedge n\nmid N\}\) is an empty set.. Hmm..
Well. The given number is \[2^{10} * 3^{9}. \] Now in order for it to divide N but not N^2 it has to be of a form \[2^m * 3^n\] However, Their product must be less than N. So the possible cases Could be Now I assumed that at least One of m or n must be greater than their respective powers in N in order for it to not divide N.
Now, If it is some, say, \[3^{11} * 2^m\]
OOOH, I may have something. Consider: \(n|N^2\) is equivalent to \(N^2=k_1n\) for some integer \(k_1\). Via a little algebra, \(N=\frac{k_1}{N}n\). Since \(N\) is an integer, \(N=k'n\) for some integer \(k'\). Via definition of \(a | b\), \(n|N\). Therefore, there is no \(n\) such that \(n|N^2\) and \(n\nmid N\). Thus, \(0\).
Actually, oops. \(\frac{k_1}{N}\) is not always an integer.
And similarly I did it for cases of 2 and ..... Obviously missed some.
My proof ironically illustrates that the original parameters are necessary: If \(n \geq N\), then \(n \mid N\) for many \(n\).
The set \(\{n:(n<N)\wedge( n|N)\wedge (n|N^2)\}\) is enumerated by the function \[f(i,j)=2^i3^j \text{ if } 0\leq i \leq 9 \text{ and }0 \leq j \leq 8 .\] I believe \(\{n:(n<N)\wedge( n\nmid N)\wedge (n|N^2)\}\) is large. Consider: If \(n \nmid N\), then \(\frac{N}{n}\neq k\) for some integer \(k\). This implies \(\frac{N}{n}=u\) for \(\{u:u \notin \mathbb{Z}\}\). Multiply both sides by \(N\) and you get \(\frac{N^2}{n}=uN\). Recall that \(n\) must be less than \(N\). This tells you that \(0<u<1\). The product \(uN\) is an integer at \(u=\left\{f(i,j)^{-1}=\frac{1}{2^i3^j}\right\}\) with \(0 \leq i \leq 10\) and \(0 \leq j \leq 9\) and \(2^i3^j\neq 1\). This tells us that \(n \mid N^2\) for \(109\) \(n\). (\((i,j)=(0,0)\) is excluded.) All other cases must not divide \(N^2\). Since the set \(\{1,\dots,N-1\}\) has \(N-1\) elements, we have that the cardinality of \(\{n:(n<N)\wedge( n|N)\wedge (n|N^2)\}\) is \(N-110\). :)
OOPS. I meant for the set to be: \(\{n:(n<N)\wedge (n \nmid N)\wedge (n|N^2)\}\) at the bottom!
The choices we have for \(n=2^i3^j\) are At \(i=0,1, \cdots, 9\): \(j=0,1,\cdots 9\). At \(i=10\): \(j=0,1,\cdots 8\). The number of all n's is \(10\cdot 10+9=109.\)
I think I can clarify my post: If \(n \nmid N\), then \(\frac{N}{n} \neq k\) for some integer \(k\). If \(\frac{N}{n} \neq k\) , then \(\frac{N}{n}=u\) for some \(u\) that is not an integer. If \(n<N\), then \(0 < u < 1\). If \(0<u<1\), then \(u=\frac{1}{b}\) for some integer \(b\). If \(\frac{N}{n}=u\), then \(\frac{N^2}{n}=uN\). Therefore, \(n | N^2\) if and only if \(uN\) is an integer. If \(N=2^{10}\cdot 3^{9}\), then \(uN\) is an integer if and only if \(b=2^i3^j\) for \(0 \leq i \leq 10\), \(0 \leq j \leq 9\), and \((i,j)\neq(0,0)\). There are \(109\) such \(b\). Therefore, there are \(109\) \(n\) such that \(n \nmid N\), \(n<N\), and \( n \mid N^2\).
Im getting 90 as an answer <.<
There is a little flaw in Limitless' argument. If n<N, then\[1<\frac{N}{n}\]so u would have to be greater than 1, not in between 0 and 1.
I looked at the problem this way. If:\[n\mid N^2\]then n has to be of the form:\[n=2^a\cdot 3^b\]where:\[0\le a \le 20,0\le b\le 18\]But we dont want n to divide N, so a cant be less than 11 and b cant be less than 10 at the same time. Also, we dont want n to be bigger than N, so a cant be bigger than 9 and b cant be bigger than 8 at the same time. So what conditions on a and b are we looking for? We want all n such that:\[n=2^a3^b\]such that only one of these two conditions are met: either:\[11\le a\le 20, 0\le b\le 8, n<N\]or \[0\le a \le 9, 10\le b\le 18, n<N\]So we nee to count these possibilities.
Using the brute force method, @joemath314159 is correct. There are 90 possibilities.
Yeah, i could only brute force it too. Im not sure if there is a clever way to attempt this problem.
You could probably place some bounds on the sum of the exponents somehow.
i just sat there and went:\[2^{11}, 2^{11}\cdot 3, 2^{11} \cdot 3^2, \ldots 2^{11}\cdot 3^8\]"How many of these are less than 2^10*3^9? Not this one, not that one" etc etc. Went from the exponent of 2 being 11 all the way to 20, then did the same thing with 3 being the larger exponent. Took forever >.<
I did a similar thing. Used Wolfram to help me though. Put 2^11*3^8 < 2^10*3*9 2^12*3^8 < 2^10*3*9 2^12*3^7 < 2^10*3*9 ... whenever it said "true" I increased the exponent of 2, and if it said "false" I decreased the exponent of 3. Then switched it around so that I was increasing the exponent of 3, and decreasing the exponent of 2.
Right. I should have used Wolfram >.< I was subtracting the two numbers. Checking if the result was positive or negative.
90 is the right answer.
And there exists a very smart/easy solution. It is possible to generalize to any given N.
I think writing it as \[2^{m - 10} < 3^{9 - n}\] Where either n > 9 Or m > 10, Makes things a lot simpler.
There are 90 as many people suggested above. Here they are \[ \begin{array}{cccccccccc} 2^{11} & 2^{12} & 2^{11} 3^1 & 2^{13} & 2^{12} 3^1 & 2^{14} & 2^{11} 3^2 & 2^{13} 3^1 & 2^{15} & 2^{12} 3^2 \\ 2^{14} 3^1 & 2^{11} 3^3 & 3^{10} & 2^{16} & 2^{13} 3^2 & 2^{15} 3^1 & 2^{12} 3^3 & 2^1 3^{10} & 2^{17} & 2^{14} 3^2 \\ 2^{11} 3^4 & 3^{11} & 2^{16} 3^1 & 2^{13} 3^3 & 2^2 3^{10} & 2^{18} & 2^{15} 3^2 & 2^{12} 3^4 & 2^1 3^{11} & 2^{17} 3^1 \\ 2^{14} 3^3 & 2^3 3^{10} & 2^{11} 3^5 & 2^{19} & 3^{12} & 2^{16} 3^2 & 2^{13} 3^4 & 2^2 3^{11} & 2^{18} 3^1 & 2^{15} 3^3 \\ 2^4 3^{10} & 2^{12} 3^5 & 2^{20} & 2^1 3^{12} & 2^{17} 3^2 & 2^{14} 3^4 & 2^3 3^{11} & 2^{11} 3^6 & 2^{19} 3^1 & 3^{13} \\ 2^{16} 3^3 & 2^5 3^{10} & 2^{13} 3^5 & 2^2 3^{12} & 2^{18} 3^2 & 2^{15} 3^4 & 2^4 3^{11} & 2^{12} 3^6 & 2^{20} 3^1 & 2^1 3^{13} \\ 2^{17} 3^3 & 2^6 3^{10} & 2^{14} 3^5 & 2^3 3^{12} & 2^{11} 3^7 & 2^{19} 3^2 & 3^{14} & 2^{16} 3^4 & 2^5 3^{11} & 2^{13} 3^6 \\ 2^2 3^{13} & 2^{18} 3^3 & 2^7 3^{10} & 2^{15} 3^5 & 2^4 3^{12} & 2^{12} 3^7 & 2^{20} 3^2 & 2^1 3^{14} & 2^{17} 3^4 & 2^6 3^{11} \\ 2^{14} 3^6 & 2^3 3^{13} & 2^{11} 3^8 & 2^{19} 3^3 & 3^{15} & 2^8 3^{10} & 2^{16} 3^5 & 2^5 3^{12} & 2^{13} 3^7 & 2^2 3^{14} \\ \end{array} \]
This is fascinating. I did actually screw that up--thank you for the correction. I would love to figure out what the elegant argument is, but it eludes me.
What is the elegant solution? :/