Intereting Posts

how do i prove that $17^n-12^n-24^n+19^n \equiv 0 \pmod{35}$
Why does Benford's Law (or Zipf's Law) hold?
Evaluate $\int_{0}^{\pi }\theta ^{3}\log^{3}\left ( 2\sin\frac{\theta }{2} \right )\mathrm{d}\theta $
Compute $P(X>40\; |\; X>10)$ where $X$ has an exponential distribution
Unique line in $\mathbb{P}^3$ through a point $p$ and intersecting two disjoint lines
If a and b are relatively prime and ab is a square, then a and b are squares.
Hilbert space and its dual
Motivation behind Dedekind's cut set
Arithmetic function to return lowest in-parameter
Integration with respect to counting measure.
Finding a combinatorial argument for an interesting identity: $\sum_k \binom nk \binom{m+k}n = \sum_i \binom ni \binom mi 2^i$
Solutions of $p!q! = r!$
Prove composition is a measurable function
Probability: 10th ball is blue
Integral: $\int_{-\infty}^{\infty} \frac{dx}{(e^x+x+1)^2+\pi^2}$

Consider a 2D line $A x + B y + C = 0$ with integer coefficients $A, B, C$. Find the lattice point $(x, y)$ closest to the line, such that $|x|, |y| \leq n$ for some integer $n$. ($x$ and $y$ are integers, of course).

It is given that the line intersects the $y$ axis at $y_0 = -\frac{C}{B}$ and $-1 < y_0 < 0$. I.e. the line is shifted from the origin, but not by “much”.

Note that if the line would go through the origin, i.e. $y_0 = 0$, $(x,y)$ pairs could be easily enumerated with convergents and semiconvergents of $\frac{A}{B}$. However, here we have a small offset so that’s not the case anymore. I suspect some similar approach still exists.

What would be an efficient way to get such $(x,y)$ point?

- Fermat's Last Theorem near misses?
- Floor function inequality $\lfloor a\sqrt{2}\rfloor\lfloor b\sqrt{7}\rfloor <\lfloor ab\sqrt{14}\rfloor$
- Calculate $\lim_{n \to \infty} \sqrt{|\sin n|}$
- Gap between smooth integers tends to infinity (Stoermer-type result)?
- Irrationality of $\sum_{p\in\mathbb{P}} \frac{1}{2^{p}}$
- Can the golden ratio accurately be expressed in terms of e and $\pi$

For example, the following picture shows some such line (red) and the closest point to it (blue) for $n = 8$.

- What is the sum of the squares of the differences of consecutive element of a Farey Sequence
- Why is the Möbius strip not orientable?
- Equal perimeter and area
- Circle on Riemann sphere
- Circle areas on squared grid
- Family of geometric shapes closed under division
- The Euler characteristic & a cube with holes?
- Inscribed kissing circles in an equilateral triangle
- Least greedy square
- Decomposing an Affine transformation

Okay I figured this. As I suspected an approach similar to Euclidean algorithm works. The idea is as follows:

For any given $x$, $y = [\frac{A x + C}{-B}]$, where $[z]$ means $round(z)$. So this essentially asks to find an $x$ within $[x_{min}, x_{max}]$ that minimizes $d(x)=|A x + C + B\ [\frac{A x + C}{-B}]|$.

Let’s cover a couple of edge cases first. If $A=0$, then $d(x)$ does not depend on $x$ so we can just return $x_{min}$. Therefore, from now on we can assume $A\neq0$.

If $A<0$, we can simply negate both $A$ and $C$ which makes $A>0$ without changing the value of $d(x)$. Therefore, from now on we can assume $A>0$.

First note that $|z|=|-z|$ and $-[z] = [-z]$. I.e. sign doesn’t affect absolute value functor, and it can freely move through the round functor.

The previous statement then trivially follows because:

$$

\begin{align}

d(x) & =|A x + C + B\ [\frac{A x + C}{-B}]| \\\\

& =|-A x – C – B\ [\frac{A x + C}{-B}]| \\\\

& =|-A x – C + B\ [\frac{-A x – C}{-B}]|

\end{align}

$$

Similarly, we can change the sign of $B$ so that it is always positive. We get:

$$

\begin{align}

d(x) & =|A x + C + B\ [\frac{A x + C}{-B}]| \\\\

& =|A x + C – B\ [\frac{A x + C}{B}]|

\end{align}

$$

What’s convenient now is that both $A>0$ and $B>0$. Let’s write $A=qB+r$ where $0 \leq r < B$. Then:

$$

\begin{align}

d(x) & =|A x + C – B\ [\frac{A x + C}{B}]| \\\\

& =|(qB+r) x + C – B\ [\frac{(qB+r) x + C}{B}]| \\\\

& =|(qB+r) x + C – B\ [qx+\frac{r x + C}{B}]| \\\\

& =|(qB+r) x + C -Bqx -B\ [\frac{r x + C}{B}]| \\\\

& =|r x + C -B\ [\frac{r x + C}{B}]| \\\\

\end{align}

$$

This means we can make $A<B$ by simply replacing it by the remainder of division of $A$ by $B$. Therefore, from now on assume $A<B$.

Since $A<B$, this means the range $[y_{min},y_{max}]$ of values that $y=[\frac{A x + C}{B}]$ takes is smaller than $[x_{min}, x_{max}]$ and this is the crucial observation here.

At the beginning we said that for any given $x$, the best $y=[\frac{A x + C}{-B}]$. Reciprocally for any fixed $y$, the best $x=[\frac{B y + C}{-A}]$.

This gives $d(x) = B y + C + A [\frac{B y + C}{-A}]$, which is the same problem but with reduced limits. In particular $(A, B, C) \implies (B, A\%B, C)$ like in Euclidean algorithm, and the size of range for $y$ is $\frac{A\%B}{B}$ of that of range for $x$.

This gives an $O(\log B)$ algorithm of finding $(x,y)$. We just need to take some care in correctly covering the boundaries of ranges $[x_{min},x_{max}]$ and $[y_{min},y_{max}]$.

Here is my implementation.

- Finding Boolean/Logical Expressions for truth tables in algebraic normal form(ANF)
- Density of set of splitting primes
- Consider numbers of the type $n=2^m+1$. Prove that such an n is prime only if $n=F_K$ for some $ k \in N$, where $F_k$ is a Fermat Prime.
- Sum of $\Gamma(n+a) / \Gamma(n+b)$
- Prove that the group isomorphism $\mathbb{Z}^m \cong \mathbb{Z}^n$ implies that $m = n$
- if f(x) if differentiable and continuous, prove $\frac{af(a)-bf(b)}{a-b} = f(c) + cf'(c) $
- Proving $\int_{-\infty}^{+\infty}{\mathrm dx\over x^2}\cdot\left(2-{\sin x\over \sin\left({x\over 2}\right)}\right)^{n+1}={2n\choose n}\pi$
- Dedekind cuts for $\pi$ and $e$
- Unique line in $\mathbb{P}^3$ through a point $p$ and intersecting two disjoint lines
- Show $au_x+bu_y=f(x,y)$ gives $u(x,y)=(a^2+b^2)^{-\frac{1}{2}}\int_{L}fds +g(bx-ay)$ if $a\neq 0$.
- How find this integral limt
- Non-standard models of arithmetic for Dummies (2)
- $R = \mathbb{Z}\ /\ (1+3i)$ – Ring homomorphisms
- What is the center of a semidirect product?
- Can we have a matrix whose elements are other matrices as well as other things similar to sets?