Number theory

[sn3ak1]

There is a positive integer n. Let's consider all numbers n/k where k is a positive integer. Demonstrate that there are no more than 2√(n + 1) of such numbers that are different from each other.
Note: For a real number x, by ⌊x⌋ we mean the largest integer not greater than x.

 

[ksdhart2]

There is a positive integer n. Let's consider all numbers n/k where k is a positive integer. Demonstrate that there are no more than 2√(n + 1) of such numbers that are different from each other.

Umm... are you sure you copied down this exercise correctly? Let \(n = 1\). According to the problem text, we're to demonstrate that there's less than \(2\sqrt{n + 1} = 2\sqrt{2} \approx 2.8284\). In other words, we have to show that there's less than 3 fractions of the form \( \frac{1}{k}, \: \: k \in \mathbb{Z}^{+} \), but we can't do that because it's not true!

Consider \(\frac{1}{1}\), \(\frac{1}{2}\), and \(\frac{1}{3}\). Would you agree these are all different numbers, that there's three of them, and three is more than two? In fact, we can easily show that, since there are infinitely many positive integers, there's also infinitely many such fractions of the form \(\frac{1}{k}\), where \(k\) is a positive integer.

At first I thought maybe you'd accidentally omitted a sentence where they told you that it must the case that \(k \leq n\)... But even then if we let \(n = 5\), the premise is still falsified. Consider:

\(\displaystyle \frac{5}{1}, \: \frac{5}{2}, \: \frac{5}{3}, \: \frac{5}{4}, \: \frac{5}{5}\)

As before, these are all different numbers, but the modified hypothesis says there should be no more than \(2\sqrt{5+1} \approx 4.8990\) such fractions, which we've clearly proven wrong.

 

[sn3ak1]

Umm... are you sure you copied down this exercise correctly? Let \(n = 1\). According to the problem text, we're to demonstrate that there's less than \(2\sqrt{n + 1} = 2\sqrt{2} \approx 2.8284\). In other words, we have to show that there's less than 3 fractions of the form \( \frac{1}{k}, \: \: k \in \mathbb{Z}^{+} \), but we can't do that because it's not true!

Consider \(\frac{1}{1}\), \(\frac{1}{2}\), and \(\frac{1}{3}\). Would you agree these are all different numbers, that there's three of them, and three is more than two? In fact, we can easily show that, since there are infinitely many positive integers, there's also infinitely many such fractions of the form \(\frac{1}{k}\), where \(k\) is a positive integer.

At first I thought maybe you'd accidentally omitted a sentence where they told you that it must the case that \(k \leq n\)... But even then if we let \(n = 5\), the premise is still falsified. Consider:

\(\displaystyle \frac{5}{1}, \: \frac{5}{2}, \: \frac{5}{3}, \: \frac{5}{4}, \: \frac{5}{5}\)

As before, these are all different numbers, but the modified hypothesis says there should be no more than \(2\sqrt{5+1} \approx 4.8990\) such fractions, which we've clearly proven wrong.

You are right I accidentally made a typo. It should be 2√(n)+1 and when i wrote n/k I meant [n/k]. So considering "Note: For a real number x, by ⌊x⌋ we mean the largest integer not greater than x." 1/2 and 1/3 would be the same integer.

 

[ksdhart2]

Ahh... okay. That's a much more difficult problem, and unfortunately I've not been able to make much headway on it. Here's some of my thoughts/observations on the matter, maybe they'll lead you somewhere.

If \(k > n\) then \( \big \lfloor \frac{n}{k} \big \rfloor = 0\) and thus 0 will always appear in the list of unique fractions.

If \(k\) is a factor of \(n\) then \( \big \lfloor \frac{n}{k} \big \rfloor \) must be unique, because factors always come in pairs. Even if \(n\) is a perfect square, in which case one of the "pairs" will be the degenerate pair \( (\sqrt{n}, \sqrt{n}) \). Because of this and the previous observation, we can always guarantee that there will be at least \(f(n) + 1\) unique fractions, where \(f(n)\) denotes the number of factors of \(n\).

Conversely, it can be seen that there will be at most \(n + 1\) unique fractions because \( \big \lfloor \frac{n}{1} \big \rfloor = n\) and the stipulation that \(k\) be a positive integer eliminates the possibility of any \( \big \lfloor \frac{n}{k} \big \rfloor \) resolving to a value greater than \(n\).

And finally, some numbers that can never appear in the list of unique fractions for a particular \(n\) are given by the ranges:

\(
\big \lfloor \frac{n}{2} \big \rfloor < x < n \\
\big \lfloor \frac{n}{3} \big \rfloor < x < \frac{n}{2} \\
\big \lfloor \frac{n}{4} \big \rfloor < x < \frac{n}{3}
\)
and so on.

 

[sn3ak1]

Ahh... okay. That's a much more difficult problem, and unfortunately I've not been able to make much headway on it. Here's some of my thoughts/observations on the matter, maybe they'll lead you somewhere.

If \(k > n\) then \( \big \lfloor \frac{n}{k} \big \rfloor = 0\) and thus 0 will always appear in the list of unique fractions.

If \(k\) is a factor of \(n\) then \( \big \lfloor \frac{n}{k} \big \rfloor \) must be unique, because factors always come in pairs. Even if \(n\) is a perfect square, in which case one of the "pairs" will be the degenerate pair \( (\sqrt{n}, \sqrt{n}) \). Because of this and the previous observation, we can always guarantee that there will be at least \(f(n) + 1\) unique fractions, where \(f(n)\) denotes the number of factors of \(n\).

Conversely, it can be seen that there will be at most \(n + 1\) unique fractions because \( \big \lfloor \frac{n}{1} \big \rfloor = n\) and the stipulation that \(k\) be a positive integer eliminates the possibility of any \( \big \lfloor \frac{n}{k} \big \rfloor \) resolving to a value greater than \(n\).

And finally, some numbers that can never appear in the list of unique fractions for a particular \(n\) are given by the ranges:

\(
\big \lfloor \frac{n}{2} \big \rfloor < x < n \\
\big \lfloor \frac{n}{3} \big \rfloor < x < \frac{n}{2} \\
\big \lfloor \frac{n}{4} \big \rfloor < x < \frac{n}{3}
\)
and so on.

I made a simple program to analyse data and this is the output:
1 unique fraction for 1 number ( 0 )
2 unique fractions for 1 number ( 1 )
3 unique fractions for 2 numbers ( 2 3 )
4 unique fractions for 2 numbers ( 4 5 )
5 unique fractions for 3 numbers ( 6 7 8 )
6 unique fractions for 3 numbers ( 9 10 11 )
7 unique fractions for 4 numbers ( 12 13 14 15 )
8 unique fractions for 4 numbers ( 16 17 18 19 )
9 unique fractions for 5 numbers ( 20 21 22 23 24 )
10 unique fractions for 5 numbers ( 25 26 27 28 29 )
11 unique fractions for 6 numbers ( 30 31 32 33 34 35 )
12 unique fractions for 6 numbers ( 36 37 38 39 40 41 )
13 unique fractions for 7 numbers ( 42 43 44 45 46 47 48 )
14 unique fractions for 7 numbers ( 49 50 51 52 53 54 55 )
15 unique fractions for 8 numbers ( 56 57 58 59 60 61 62 63 )
16 unique fractions for 8 numbers ( 64 65 66 67 68 69 70 71 )
17 unique fractions for 9 numbers ( 72 73 74 75 76 77 78 79 80 )
18 unique fractions for 9 numbers ( 81 82 83 84 85 86 87 88 89 )
19 unique fractions for 10 numbers ( 90 91 92 93 94 95 96 97 98 99 )
20 unique fractions for 10 numbers ( 100 101 102 103 104 105 106 107 108 109 )
and so on.

I think it's possible to create a formula for fractions count for integer n, but I don't know how to do this.

 

[Steven G]

I made a simple program to analyse data and this is the output:
1 unique fraction for 1 number ( 0 )
2 unique fractions for 1 number ( 1 )
3 unique fractions for 2 numbers ( 2 3 )
4 unique fractions for 2 numbers ( 4 5 )
5 unique fractions for 3 numbers ( 6 7 8 )
6 unique fractions for 3 numbers ( 9 10 11 )
7 unique fractions for 4 numbers ( 12 13 14 15 )
8 unique fractions for 4 numbers ( 16 17 18 19 )
9 unique fractions for 5 numbers ( 20 21 22 23 24 )
10 unique fractions for 5 numbers ( 25 26 27 28 29 )
11 unique fractions for 6 numbers ( 30 31 32 33 34 35 )
12 unique fractions for 6 numbers ( 36 37 38 39 40 41 )
13 unique fractions for 7 numbers ( 42 43 44 45 46 47 48 )
14 unique fractions for 7 numbers ( 49 50 51 52 53 54 55 )
15 unique fractions for 8 numbers ( 56 57 58 59 60 61 62 63 )
16 unique fractions for 8 numbers ( 64 65 66 67 68 69 70 71 )
17 unique fractions for 9 numbers ( 72 73 74 75 76 77 78 79 80 )
18 unique fractions for 9 numbers ( 81 82 83 84 85 86 87 88 89 )
19 unique fractions for 10 numbers ( 90 91 92 93 94 95 96 97 98 99 )
20 unique fractions for 10 numbers ( 100 101 102 103 104 105 106 107 108 109 )
and so on.

I think it's possible to create a formula for fractions count for integer n, but I don't know how to do this.

Here is what I observed. If n is even then there are n/2 numbers. If n is odd, there are (n+1)/2 numbers. Now you have to think about how we can go from a given n to the first number associated with it or even the last number. It should not be that bad.