Related Experiment Video
Updated: Jul 18, 2025

Generating Strictly Controlled Stimuli for Figure Recognition Experiments
Published on: March 18, 2019
Bias in the number of steps in the Euclidean algorithm and a conjecture of Ito on Dedekind sums
Paolo Minelli1, Athanasios Sourmelidis1, Marc Technau1
1Institute for Analysis and Number Theory, Graz University of Technology, Kopernikusgasse 24/II, 8010 Graz, Austria.
Abstract:
We investigate the number of steps taken by three variants of the Euclidean algorithm on average over Farey fractions. We show asymptotic formulae for these averages restricted to the interval (0, 1/2), establishing that they behave differently on (0, 1/2) than they do on (1/2, 1). These results are tightly linked with the distribution of lengths of certain continued fraction expansions as well as the distribution of the involved partial quotients. As an application, we prove a conjecture of Ito on the distribution of values of Dedekind sums. The main argument is based on earlier work of Zhabitskaya, Ustinov, Bykovskiĭ and others, ultimately dating back to Lochs and Heilbronn, relating the quantities in question to counting solutions to a certain system of Diophantine inequalities. The above restriction to only half of the Farey fractions introduces additional complications.
More Related Videos
08:12A Psychophysics Paradigm for the Collection and Analysis of Similarity Judgments
Published on: March 1, 2022
09:01Gain-compensation Methodology for a Sinusoidal Scan of a Galvanometer Mirror in Proportional-Integral-Differential Control Using Pre-emphasis Techniques
Published on: April 4, 2017
Related Concept Videos
Theorems of Pappus and Guldinus: Problem Solving
Determination of Pi Terms
The theorem indicates that...
Bias
In statistics, a sampling bias is created when a sample is collected from a population, and some members of the population are not as likely to be chosen as others (remember, each member...
Euler's Formula for Pin-Ended Columns
To calculate the critical load,...
Divergence and Stokes' Theorems
Theorems of Pappus and Guldinus
For finding the surface area, consider a differential line element that generates a ring with surface area dA when revolved.