Questions tagged [farey-sequences]

The Farey sequence of order $n$ is the sequence of all lowest-terms fractions between 0 and 1 whose denominators do not exceed $n$, in increasing order.

Filter by
Sorted by
Tagged with
0
votes
0answers
16 views

Diophantine approximation and Farey sequences

I am self studying Apostol Dirichlet Series and Modular Functions in Number Theory and could not solve this question given in Chapter 7. Please help. Question is – Let $ \Theta $ be an irrational ...
0
votes
0answers
9 views

Regarding properties of Farey sequences related to lattice points.

I am self studying Apostol's Dirichlet series and Modular Functions in Number Theory and need help in this question. Question is – let $n \ge 1$ and $T_n$ denotes the set of lattice points $(x, y)$ ...
0
votes
1answer
14 views

Regarding property of Farey sequence

I am studying apostol Dirichlet series and modular functions book and struck upon this question. Question is - Two reduced fractions $a/ b$ and $c/d$ are called similarly ordered if $(c-a)(d-b) \ge 0$...
0
votes
0answers
21 views

Determine if a number is the length of a farey sequence

Given a number $j$, is there a way to determine that it is the length of a valid Farey sequence. The length is given by: $$|F_n| = \frac{1}{2}(n+3)n - \sum_{d=2}^n |F_\frac{n}{d}|$$ For example, 2,...
0
votes
0answers
31 views

Find the Farey triple given the base vertex of any isosceles triangle in Farey diagram.

There is a visualization of the circular Farey diagram where all triangles are isosceles. Observe that any rational $\frac{a}{b}$ distinct from $\frac{0}{1}$ and $\frac{1}{0}$ is always the vertex ...
1
vote
0answers
31 views

What is sum of squared elements of Farey sequence?

Let's consider a Farey sequence: $$F_{n}=\{a_{1},...,a_{k}\}$$; Where given elements satisfy definition of $n$-th Farey sequence. My problem: Find the formula for the following sum: $$\sum_{l=1}^{k}...
3
votes
0answers
39 views

Is there an elegant Stern Brocot like way to generate all coprime triples?

As one might know, the Stern Brocot tree elegantly and compactly models all rational numbers. I am now left wondering if a process like this tree modeling could be done not only for pairs but for ...
0
votes
1answer
285 views

farey sequences proof

Definitions: $v_{h,k}=\frac{1}{k(k+k_1)}$ and $w_{h,k}=\frac{1}{k(k+k_2)}$ where $\frac{h_1}{k_1}\lt\frac{h}{k} \lt\frac{h_2}{k_2}$ are sucessive farey fractions. Proof that: $\frac{h_1}{k_1}-\...
0
votes
1answer
107 views

If $ \displaystyle \frac{h}{k} $ and $ \displaystyle \frac{h'}{k'} $ are two consecutive terms of a Farey series, then $ h'k - hk' = 1 $

I am learning about Farey series from Hardy and Wright Intro to Number Theory and they give the following theorem whose proof I currently have trouble understanding. $ \textbf{Theorem 28} $: If $ \...
7
votes
1answer
122 views

Is the link between Stern's diatomic sequence and binary subsequences genuine or a coincidence with exceptions?

In a sister stack, Martin Ender raised a question about the following function: Let's define a function $f(N)$ on the integers via the following algorithm. We'll use $N = 38$ as an example: ...
0
votes
2answers
205 views

Mediant and arithmetic mean of several fractions

Suppose there are several fractions $\frac{a_1}{b_1}, \ldots, \frac{a_n}{b_n}$ and $0 < \frac{a_i}{b_i} \leq 1$ for $1 \leq i \leq n$ Define the Mediant of the above fractions $M = \frac{a_1 + \...
2
votes
1answer
177 views

List of fractions $\dfrac{a}{b}$ with $ab < 1988$

All irreducible positive rational numbers such that the product of the numerator and the denominator is less than $1988$ are written in increasing order. Prove that any two adjacent fractions $\dfrac{...
1
vote
1answer
158 views

How does this proof concerning the farey sequence work exacty?

In Hardy and Wright, sixth edition we have theorem 28 which states that if $\dfrac{h}{k}$ and $\dfrac{h'}{k'}$ are two consecutive terms in a Farey sequence: $$kh'-hk'=1$$ and theorem 29 states that, ...
2
votes
1answer
145 views

Stern-Brocot Tree and sum of coefficients of continued fraction

Suppose we are given a continued fraction $$\frac{p}{q}=a_{1}+\frac{1}{a_{2}+\frac{1}{a_{3}+\frac{1}{a_{4}+\cdots}}}$$ I am trying to find an expression, possibly asymptotic, for the sum of the $a_i$'...
-2
votes
1answer
78 views

the shape of $x - \frac{\lfloor q x\rfloor}{q}$ when $q \to \infty$

given an irrational $x > 0$, approximate it by a rational : $$x = \frac{p}{q} + \epsilon$$ the residual can be seen as a function of $q \in \mathbb{N}$ : $$\epsilon(q) = x - \frac{\lfloor q x\...
4
votes
0answers
68 views

Is there a heuristic reason behind this numerical coincidence?

Write $N(m, n; c)$ for the number of $m\times n$ zero-one matrices where each zero is adjacent to precisely $c$ others, where by "adjacent" I mean up/down/left/right but not diagonally. (Notice that ...
3
votes
1answer
265 views

Interesting approximation of distribution of numbers in a Farey sequence

I was investigating the distribution of the numbers in a Farey sequence and found some pattern. It is known that the number of elements in Farey sequence can be found using Euler totient function. So ...
0
votes
2answers
235 views

How can I approximate a decimal with two fractions where denominator is less or equal to $d$

I was looking for a way to approximate a decimal number with a fraction, whose denominator is less or equal to $d$. Basically, having a decimal $X$, I want to find two fractions such that $$\frac{a_1}...
0
votes
1answer
90 views

Farey Sequence implemenatation

I'm trying to use the Farey sequence to get the next lowest reduced fraction in a list. For example, for $n = 8$, we have $\dots, \frac13, \frac38, \frac25, \frac37, \frac12, \dots$ So let's take $\...
10
votes
3answers
188 views

Minimal $ab$ for Rational Number $a/b$ in an Interval

Given rational numbers $L$ and $U$, $0<L<U<1$, find rational number $M=a/b$ such that $L \le M<U$ and $(a\times b)$ is as small as possible---$a$ and $b$ are integers. For example, If $L=...
0
votes
3answers
68 views

Find a sequence (Sn) that for any a between [0,1] there is a subsequence of Sn that converges to a.

Find a sequence (Sn) that for any a between [0,1] there is a subsequence of Sn that converges to a. I've been stumped for days, my guess is that it is an addition of sequences each expressing its ...
0
votes
1answer
106 views

Farey sequence problem with irrational numbers

If an irrational number $\theta$ lies between two consecutive terms $a/b$ and $c/d$ of the Farey sequence of order n, prove that at least one of the following holds: $|\theta- a/b| < 1/2b^2$ or $|\...
3
votes
0answers
136 views

Unitary Farey Sequence Matrices

Take the Farey sequence $\mathcal{F}_n$ with values $a_m\in \mathcal{F}_n$ and put them into a vector $$ \vec v_k=\frac1{\sqrt{|\mathcal{F}_n|}}\biggr(\exp(2\pi i k a_m)\biggr)_m $$ The dimension of ...
1
vote
1answer
114 views

Farey Sequence Vector Orthogonality Relation Question

Take the Farey sequence $\mathcal{F}_n$ for $n=39$ with values $a_m\in \mathcal{F}_n$ and put them into a vector $$ \vec v_k=\biggr(\exp(2\pi i k a_m)\biggr)_m $$ Since Merten's function for $n=39$ ...
4
votes
0answers
189 views

Alternative Proof for “Roots of Mertens Function-Farey Sequence-Cosines Relations”

You can write Merten's function as $$ M(n)= \sum_{a\in \mathcal{F}_n} e^{2\pi i a} , $$ where $\mathcal{F}_n$ is the Farey sequence of order $n$. The sum may be split into imaginary and real ...
2
votes
0answers
91 views

Farey Sequences and how evenly is the sequence distributed

Given any $\alpha,\beta\in (0, 1)$, $k\in Z^+, n > 1$ is this true ($\mathcal{F}_n$ denotes the $n$th Farey sequence, and $\mathcal{F_n}^{\prime} = \{q:q = a + b, a\in\mathbb{Z}, b\in\mathcal{F_n}\...
7
votes
0answers
166 views

Product of the first n cyclotomic polynomials.

Let $$F_n(\alpha) = \prod_{k = 1}^n \Phi_k(e(\alpha))$$ where $e(\alpha) = e^{2\pi i\alpha}$ It is clear that $F_n(\alpha) = 0$ iff $\alpha = \frac{a}{q}$ for relatively prime $a, q$ s.t. $q \le n$. ...
2
votes
1answer
160 views

Find $x, y$ such that $\left | \frac ab -\frac xy \right |$ is minimal

Given positive integers $a, b, D$. How to find $x, y \in \mathbb{Z^+}$ such that $$M =\left | \frac ab -\frac xy \right |$$ is minimal and $x + y \le D$? For a solution, I can get it by brute-force ...
3
votes
1answer
242 views

Computational Complexity of Finding Adjacent Terms in Farey Sequence

The Farey sequence $\mathcal{F}_n$ is the list of all fractions in increasing order (in lowest terms) from $0$ to $1$, having denominator at most $n$. My question is, given some $a/b\in\mathcal{F}_n$ ...
5
votes
2answers
1k views

How to prove that construction of Farey sequence by mediant is coverage?

Farey sequence of order $n+1$ ($F_{n+1}$) can be construct by adding mediant value (${a+c \over b+d}$) into $F_{n}$, where ${a \over b}$ and ${c \over d}$ are consecutive term in $F_{n}$, and $b+d = ...
3
votes
1answer
199 views

Farey sequences for polynomials?

Does a notion of Farey sequence (or something equivalent) exist for polynomials over finite fields?
4
votes
3answers
936 views

Constructing Farey sequences inductively

Objective: I'd like to prove that $F_{n+1}$ (the Farey sequence of order $n+1$) is obtained form the Farey sequence $F_n$ of order $n$ by adding all fractions of the form $\frac{a+c}{b+d}$ when $\...
13
votes
1answer
270 views

What is the sum of the squares of the differences of consecutive element of a Farey Sequence

A Farey sequence of order $n$ is a list of the rational numbers between 0 and 1 inclusive whose denominator is less than or equal to $n$. For example $F_6= \{0,1/6,1/5,1/4,1/3,2/5,1/2,3/5,2/3,3/4,4/...
5
votes
5answers
1k views

How to compute next/previous representable rational number?

An (approximate) non-negative rational number representation is a pair of natural numbers each not greater than some fixed limit M (and of course denominator being non-zero). With this condition ...