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!

  • 1
    $\begingroup$ To make sure that I understand: if $\{x\}=x-\lfloor x\rfloor$, you want to find all positive integers $i$ such that $$\left\{\frac{n}i\right\}<\left\{\frac{n}{i+1}\right\}\;?$$ $\endgroup$ – Brian M. Scott May 2 '12 at 5:19
  • 1
    $\begingroup$ When you say "$\mod 1$" you need to specify which equivalence class representatives you want to evaluate the inequality on. $\endgroup$ – Brett Frankel May 2 '12 at 5:19
  • $\begingroup$ @BrianM.Scott: Yes, that's exactly what I'm trying to do. $\endgroup$ – Blender May 2 '12 at 5:20
  • $\begingroup$ @BrettFrankel: I'm not entirely sure about notation for inequalities involving the modulo operator, but I think this makes a bit more sense: $\frac{n}{i}\text{ (mod 1) } < \frac{n}{i + 1}\text{ (mod 1) for } n, i\in\mathbb{N}$ $\endgroup$ – Blender May 2 '12 at 5:23
  • $\begingroup$ @Blender That doesn't make it any more clear, since there are infinitely many representatives for a real number (mod 1). But your discussion with indicates that you are picking representatives in $[0,1)$, which answers my question. $\endgroup$ – Brett Frankel May 2 '12 at 5:26

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<i<n$, 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<i<\frac{n}2$ 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<i<\frac{n}2-1$ 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\}$.)

  • $\begingroup$ Thank you for the detailed answer, I really appreciate it. Is there any reason you chose $3$ and $2$ for the bounds in this expression: $\frac{n}3<i<\frac{n}2$? The reason why I'm looking for an analytic solution for $i$ is because I'm trying to factor a large number, just to see how efficiently I can do it. Each of the possible $i$'s corresponds to a possible factor of a number $n$. I've found graphically that these $i$'s grow very predictably for arbitrary $n$, as you can see in this graph I tried to make (each peaks correspond to an $i$). $\endgroup$ – Blender May 2 '12 at 6:39
  • $\begingroup$ @Blender: The idea is to look at ranges in which all $\frac{n}i$ have the same integer part. The next interval to consider under this approach would be $\frac{n}4<i<\frac{n}3$, and so on. $\endgroup$ – Brian M. Scott May 2 '12 at 6:41
  • $\begingroup$ Ah, that makes sense. I'll definitely try to see what I can do with this. $\endgroup$ – Blender May 2 '12 at 6:42

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:


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.

  • $\begingroup$ The code that I have works exactly the same was as you have described, but I'm trying to find a way to analytically solve for $i$ or at least make the solution easier to calculate. $\endgroup$ – Blender May 2 '12 at 6:03
  • $\begingroup$ I'm basically trying to factor a number with only two prime factors. If you look at the value of the function for $i$ ranging from $0$ to $\sqrt{n}$, you can see that the distance between the peaks of the function is growing predictably. Instead of trying to factor the number by trying every possible factor, I thought it might be a bit faster to try only the factors that correspond to the peaks, as the set of all prime factors of the number will exist within the solution set of the inequality I posted in my question. Hopefully that makes at least some sense. $\endgroup$ – Blender May 2 '12 at 6:08
  • $\begingroup$ It makes sense, but I think it's hopeless. I doubt you can get any useful information about the peaks without doing more work than it would take to find the prime factors by other means. $\endgroup$ – Gerry Myerson May 2 '12 at 6:16
  • $\begingroup$ I guess you're right. Thanks for the help! $\endgroup$ – Blender May 2 '12 at 6:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.