Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
Windmills of the Minds: A Hopping Algorithm for Fermat's Two Squares Theorem
View through CrossRef
Abstract
Fermat's two squares theorem asserts that a prime one more than a multiple of 4 is a sum of two squares. There are many proofs of this gem in number theory, including a remarkable one-sentence proof by Don Zagier based on two involutions on a finite set built from such a prime. Applying the two involutions alternatively leads to an iterative algorithm to find the two squares for the prime. Moreover, a detailed analysis of the computation reveals that it is possible to jump through the iteration nodes, leading to a better hopping algorithm. Here is a formalisation of Zagier's proof, deriving the involutions using windmill patterns. Theories developed for the formal proof are used to establish the correctness of both algorithms.
Title: Windmills of the Minds: A Hopping Algorithm for Fermat's Two Squares Theorem
Description:
Abstract
Fermat's two squares theorem asserts that a prime one more than a multiple of 4 is a sum of two squares.
There are many proofs of this gem in number theory, including a remarkable one-sentence proof by Don Zagier based on two involutions on a finite set built from such a prime.
Applying the two involutions alternatively leads to an iterative algorithm to find the two squares for the prime.
Moreover, a detailed analysis of the computation reveals that it is possible to jump through the iteration nodes, leading to a better hopping algorithm.
Here is a formalisation of Zagier's proof, deriving the involutions using windmill patterns.
Theories developed for the formal proof are used to establish the correctness of both algorithms.
Related Results
Fermat's Last Theorem: A Proof by Contradiction
Fermat's Last Theorem: A Proof by Contradiction
In this paper I offer an algebraic proof by contradiction of Fermat’s Last Theorem. Using an alternative to the standard binomial expansion, (a+b) n = a n + b Pn i=1 a n−i (a + b) ...
Fermat Polynomials and Extended Fermat’s Theorem
Fermat Polynomials and Extended Fermat’s Theorem
This study discusses the connection between Fermat perfect natural vectors and some specific Fermat polynomials, whose maximal root is a natural number forming part of the Fermat v...
Arithmetic properties of non-hyperelliptic genus 3 curves
Arithmetic properties of non-hyperelliptic genus 3 curves
This thesis explores the explicit computation of twists of curves. We develope an algorithm for computing the twists of a given curve assuming that its automorphism group is known....
Scaffold Hopping with Generative Reinforcement Learning
Scaffold Hopping with Generative Reinforcement Learning
Scaffold hopping – the design of novel scaffolds for existing lead candidates – is a multi-faceted and non-trivial task, for medicinal chemists and computational approaches alike. ...
Scaffold Hopping with Generative Reinforcement Learning
Scaffold Hopping with Generative Reinforcement Learning
Scaffold hopping – the design of novel scaffolds for existing lead candidates – is a multi-faceted and non-trivial task, for medicinal chemists and computational approaches alike. ...
PENGARUH JOB HOPPING TERHADAP PENGEMBANGAN KARIR GENERASI Z
PENGARUH JOB HOPPING TERHADAP PENGEMBANGAN KARIR GENERASI Z
Penelitian ini bertujuan untuk mengkaji secara komprehensif pengaruh job hopping terhadap pengembangan karir. Melalui pendekatan empiris, penelitian ini akan mengeksplorasi faktor-...
Goedel's Theorem and Mechanism
Goedel's Theorem and Mechanism
In “Minds, Machines, and Gödel”, J. R. Lucas claims that Goedel's incompleteness theorem constitutes a proof “that Mechanism is false, that is, that minds cannot be explained as ma...
A Note on the Beal Conjecture
A Note on the Beal Conjecture
Around $1637$, Pierre de Fermat famously scribbled, and claimed to have a proof for, his statement that equation $a^{n} + b^{n} = c^{n}$ has no positive integer solutions for expon...