0
$\begingroup$

In essence, my problem boils down to finding all $i$ that satisfies this inequality ($n$ is constant):

$ \frac{n}{i} \text{ (mod 1) } < \frac{n}{i+1} \text{ (mod 1) for }n,i\in\mathbb{N}, i < \sqrt{n} $

The problem that I face is that any sort of manipulation that I try to perform doesn't really make sense in the end, as cross-multiplying will result in $0$ on both sides as both sides will be integers and subtracting one side from the other will yield a useless expression in the end.

I also tried replacing the modulo with the subtraction of integers $p, q \in \mathbb{N}$ from each side of the inequality, but that lead me to a recursive solution for $i$.

Can anyone offer me any tips on how I can approach this problem? Any help is appreciated immensely!

  • 0
    @Kaz: Right, I'm only worrying about the fractional part of the real number. $i$ will always be smaller than $\sqrt{n}$.2012-05-02

2 Answers 2

1

The following approach may be of some use, if you care to pursue it further. Or it may not.

I'll use the notation in my comment on the question. Let $I(n)=\left\{i\in\Bbb N:\left\{\frac{n}i\right\}<\left\{\frac{n}{i+1}\right\}\right\}\;.$

If $i>n$, the inequality reduces to $\dfrac{n}i<\dfrac{n}{i+1}$, which is false, so $I(n)\subseteq\{1,\dots,n\}$.

Clearly $n\in I(n)$. If $\frac{n}2, then $1\le\frac{n}{i+1}<\frac{n}i<2$, so $\left\{\frac{n}{i+1}\right\}=\frac{n}{i+1}-1$ and $\left\{\frac{n}i\right\}=\frac{n}i-1$, and $i\notin I(n)$. In other words, the unique $i\in\left(\frac{n}2,n\right)\cap I(n)$ is $n$.

If $\frac{n}3 then $2<\frac{n}i<3$. If $n$ is even, $2\le\frac{n}{i+1}<\frac{n}i<3$, and $i\notin I(n)$, while $\frac{n}2\in I(n)$ iff $n>2$.

If $n$ is odd and $\frac{n}3 we also have $i\notin I(n)$, but for $i=\left\lfloor\frac{n}2\right\rfloor=\frac{n-1}2$ we have $\left\{\frac{n}{i+1}\right\}=\left\{\frac{2n}{n+1}\right\}=\frac{n-1}{n+1}$ and $\left\{\frac{n}i\right\}=\left\{\frac{2n}{n-1}\right\}=\frac2{n-1}\;,$ and it's easily verified that $\frac2{n-1}<\frac{n-1}{n+1}$ $-$ and hence $i\in I(n)$ $-$ iff $n>4$.

It follows that for $n\ge 4$ the unique $i\in\left(\frac{n}3,\frac{n}2\right)\cap I(n)$ is $\left\lfloor\frac{n}2\right\rfloor\in I(n)$. ($I(2)=\{2\}$, and $I(3)=\{3\}$.)

  • 0
    Ah, that makes sense. I'll definitely try to see what I can do with this.2012-05-02
0

I don't know what sort of an answer you are looking for. It's easy enough to write a program that will spit out all the solutions for a given $n$. In Maple,

for n from 1 to 100 do if frac(10007/n)$\lt$frac(10007/(n+1)) then print(n) fi od

gives you all the $i$ that work for $n=10007$, for example. If you want a formula that somehow gives you the values of $i$ that work without trying them all, I'd be surprised if such a thing existed. Look at the output of the code above:

$1,2,3,5,7,8,10,11,13,15,16,17,20,21,23,25,29,30,33,34,35,38,41,42,45,46,50,51,52,54,58,59,61,62,64,69,71,73,74,75,76,78,80,82,84,87,90,100$.

Well, it's roughly half the numbers, but there are strings of consecutive numbers ($73,74,75,76$), and gaps (nothing between 64 and 69, for example). What exactly are you hoping to accomplish?

If what you want is good code, there's a website for that.

  • 0
    I guess you're right. Tha$n$ks for the help!2012-05-02