Question

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 13 years ago

Answer 1

I think you messed up the definition of "cute". IT does NOT mean devilishly hard.

Answer 2

how do you read n|N^2 ?? i seem to have forgotten

Answer 3

This is fun. Don't remove it, please. D:

Answer 4

N divides N^2

Answer 5

and n∤N ??

Answer 6

"does not divide"

Answer 7

Isnt N a number? How is it a set?

Answer 8

In this context, Set = let

Answer 9

Oh. Okay. Thanks!

Answer 10

wild guess 1??

Answer 11

Nothing is wild about this problem.

Answer 12

no ... i just find my logic too wild

Answer 13

I agree. There are certain things seeping into my brain.

Answer 14

@experimentx At least 15, man.

Answer 15

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\)...

Answer 16

Is it 84? Am I even close?

Answer 17

Argh. There are minor details that I messed up just now.

Answer 18

Close, very close :) But then I would appreciate a general and formal solution.

Answer 19

I am getting the feeling that \(\{n: n\mid N^2 \wedge n<N \wedge n\nmid N\}\) is an empty set.. Hmm..

Answer 20

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.

Answer 21

Now, If it is some, say, \[3^{11} * 2^m\]

Answer 22

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\).

Answer 23

Actually, oops. \(\frac{k_1}{N}\) is not always an integer.

Answer 24

And similarly I did it for cases of 2 and .....
Obviously missed some.

Answer 25

My proof ironically illustrates that the original parameters are necessary: If \(n \geq N\), then \(n \mid N\) for many \(n\).

Answer 26

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\). :)

Answer 27

OOPS. I meant for the set to be:
\(\{n:(n<N)\wedge (n \nmid N)\wedge (n|N^2)\}\) at the bottom!

Answer 28

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.\)

Answer 29

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\).

Answer 30

Im getting 90 as an answer <.<

Answer 31

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.

Answer 32

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.

Answer 33

Using the brute force method, @joemath314159 is correct. There are 90 possibilities.

Answer 34

Yeah, i could only brute force it too. Im not sure if there is a clever way to attempt this problem.

Answer 35

You could probably place some bounds on the sum of the exponents somehow.

Answer 36

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 >.<

Answer 37

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.

Answer 38

Right. I should have used Wolfram >.< I was subtracting the two numbers. Checking if the result was positive or negative.

Answer 39

90 is the right answer.

Answer 40

And there exists a very smart/easy solution. It is possible to generalize to any given N.

Answer 41

I think writing it as
\[2^{m - 10} < 3^{9 - n}\] Where either n > 9 Or m > 10, Makes things a lot simpler.

Answer 42

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}
\]

Answer 43

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.

Answer 44

What is the elegant solution? :/