PROG0557 - Erdõs-Straus conjecture
In science, an open problem or an open question is a known problem which can be accurately stated, and which is assumed to have an objective and verifiable solution, but which has not yet been solved (no solution for it is known). Important open problems exist in all scientific fields. For example, one of the most important open problems in biochemistry is the protein structure prediction problem — how to predict the structure of a protein from its sequence. Wikipedia has long lists of open problems in artificial intelligence, biology, chemistry, computer science, economics, geoscience, linguistics, mathematics, medicine, physics and statistics.
In mathematics, an open problem is often called a conjecture: a conclusion or proposition based on incomplete information, but for which no proof has been found yet. As soon as the conjecture is proven, it is called a theorem. Some theorems may have lived an earlier life as a conjecture for many years. Conjectures such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (now proven, but called Fermat's conjecture from 1637 until 1995) have shaped much of mathematical history as new areas of mathematics are developed in order to solve them.
One of these conjectures that is still unsolved is the Erdõs-Straus conjecture. This conjecture states that for all integers $n \geq 2$, there exists three positive integers $x, y, z \in \mathbb{N}_0$ such that $$\frac{4}{n} = \frac{1}{x} + \frac{1}{y} + \frac{1}{z}$$ or in other words that the rational number $\frac{4}{n}$ (for $n \geq 2$) can always be expressed as the sum of three unit fractions. For instance, for $n = 5$ there are two solutions: $$\frac{4}{5} = \frac{1}{2} + \frac{1}{4} + \frac{1}{20} = \frac{1}{2} + \frac{1}{5} + \frac{1}{10}$$ If both sides of the equation are multiplied by $nxyz$, the same equation can be rewritten as $$4xyz = n(xy + yz + xz)$$ This form has the advantage that it does not require any floating point divisions that might trick computers into rounding errors.
One very general problem-solving technique to prove or disprove mathematical conjectures consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's statement. This approach is called brute force. While a brute force search is simple to implement, and will always find a solution if it exists, its cost is proportional to the number of candidate solutions — which in many practical problems tends to grow very quickly as the size of the problem increases. Therefore, brute force search is typically used when the problem size is limited, or when there are problem-specific heuristics that can be used to reduce the set of candidate solutions to a manageable size. The method is also used when the simplicity of implementation is more important than speed.
Input
The input contains three integers $n, o, b \in \mathbb{N}_0$, each on a separate line.
Output
For each combination of three integers $x, y, z \in \mathbb{N}_0$ such that $o \leq x \leq y \leq z \leq b$ and such that $4xyz = n(yz + xz + xy)$, print a line that is formatted as 4/$n$ = 1/$x$ + 1/$y$ + 1/$z$. The combinations $x, y, z$ must be enumerated in increasing order, first with respect to $x$, that with respect to $y$ and finally with respect to $z$.
Tip: A brute force approach can be used to enumerate all possible combinations of $x, y, z$, so that you can test if the conditions hold for any of these combinations of $x, y, z$.
Example
Input:
3 1 12
Output:
4/3 = 1/1 + 1/4 + 1/12 4/3 = 1/1 + 1/6 + 1/6 4/3 = 1/2 + 1/2 + 1/3
Resources
- Elsholtz C (2001). Sum of k unit fractions. Transactions of the American Mathematical
Society 353(8),
3209–3227.
- Erdõs P (1950). Az $\frac{1}{x_1} +
\frac{1}{x_2} + \ldots + \frac{1}{x_n} = \frac{a}{b}$ egyenlet
egész számú megoldásairól (Hongarian: On a
Diophantine Equation). Mat. Lapok.
1, 192–210.
In de wetenschappen spreekt men van een open probleem of een open vraag als een probleem nauwkeurig kan omschreven worden, algemeen wordt aangenomen dat er een objectieve en makkelijk te controleren oplossing voor bestaat, zonder dat die oplossing tot op heden gekend is. In alle wetenschappelijke disciplines bestaan er belangrijke open problemen. Zo is het voorspellen van eiwitstructuur één van de belangrijkste open problemen in de biochemie — hoe kan je de structuur van eiwit voorspellen op basis van zijn aminozuursequentie. Op Wikipedia vind je lange lijsten van open problemen in de artificiële intelligentie, biologie, chemie, economie, fysica, geneeskunde, geowetenschappen, informatica, statistiek, taalkunde en de wiskunde.
Een open probleem in de wiskunde wordt in die context vaak ook een vermoeden genoemd. In dat gaat het om een wiskundige uitspraak waarvan wiskundigen denken dat deze waar is, terwijl er nog geen sluitend bewijs voor gevonden is. Wordt het bewijs geleverd, dan spreekt men van een stelling. Sommige stellingen kunnen jarenlang vermoedens blijven. Het bekendste geval en één van de extreemste, was de laatste stelling van Fermat die van 1637 tot 1995 onbewezen bleef.
Eén van die vermoedens dat nog altijd niet opgelost is, is het vermoeden van Erdõs-Straus. Dit vermoeden stelt dat er voor elke natuurlijk getal $n \geq 2$ drie natuurlijke getallen $x, y, z \in \mathbb{N}_0$ kunnen gevonden worden waarvoor geldt dat $$\frac{4}{n} = \frac{1}{x} + \frac{1}{y} + \frac{1}{z}$$ of met andere woorden dat je 4 gedeeld door elk natuurlijk getal (groter dan of gelijk aan twee) altijd kunt schrijven als de som van drie stambreuken. Voor $n = 5$ zijn er bijvoorbeeld twee oplossingen: $$\frac{4}{5} = \frac{1}{2} + \frac{1}{4} + \frac{1}{20} = \frac{1}{2} + \frac{1}{5} + \frac{1}{10}$$ Als je beide leden van de vergelijking vermenigvuldigt met $nxyz$ dan bekom je de vergelijking $$4xyz = n(xy + yz + xz)$$ Het voordeel van deze herschreven vergelijking is dat er geen reële delingen in voorkomen die bij computerberkeningen zorgen voor afrondingsfouten.
Een van de manieren om vermoedens uit de wiskunde te bewijzen of te ontkrachten, bestaat er botweg in om alle mogelijkheden uit te proberen totdat er een (tegen)voorbeeld gevonden wordt. Dit wordt de brute force (Engels voor "brute kracht") aanpak genoemd, die als laatste toevluchtsoord gebruikt wordt als er geen algoritme gekend is dat sneller of efficiënter tot een oplossing leidt. De brute force aanpak wordt bijvoorbeeld vaak gebruikt voor het kraken van wachtwoorden of het achterhalen van verloren gegane of vergeten wachtwoorden die versleuteld zijn met sterke encryptie. Hierbij worden alle mogelijke combinaties van beschikbare tekens geprobeerd. Dit is een zeer inefficiënte methode die extreem lang kan duren, maar ze is wel 100% trefzeker.
Invoer
De invoer bestaat uit drie getallen $n, o, b \in \mathbb{N}_0$, elk op een afzonderlijke regel.
Uitvoer
Voor elke combinatie van drie getallen $x, y, z \in \mathbb{N}_0$ waarvoor geldt dat $o \leq x \leq y \leq z \leq b$ en waarvoor geldt dat $4xyz = n(yz + xz + xy)$ moet er een regel uitgeschreven worden van de vorm 4/$n$ = 1/$x$ + 1/$y$ + 1/$z$. De combinaties $x, y, z$ moeten in oplopende volgorde uitgeschreven worden, eerst oplopend volgens $x$, dan oplopend volgens $y$ en tenslotte oplopend volgens $z$.
Tip: Om alle geldige combinaties van $x, y, z$ te vinden kan je de brute force aanpak gebruiken, waarbij je achtereenvolgens alle mogelijke combinaties van $x, y, z$ uitprobeert.
Voorbeeld
Invoer:
3 1 12
Uitvoer:
4/3 = 1/1 + 1/4 + 1/12 4/3 = 1/1 + 1/6 + 1/6 4/3 = 1/2 + 1/2 + 1/3
Bronnen
- Elsholtz C (2001). Sum of k unit fractions. Transactions of the American Mathematical
Society 353(8),
3209–3227.
- Erdõs P (1950). Az $\frac{1}{x_1} +
\frac{1}{x_2} + \ldots + \frac{1}{x_n} = \frac{a}{b}$ egyenlet
egész számú megoldásairól (Hongarian: On a
Diophantine Equation). Mat. Lapok.
1, 192–210.
| Added by: | Peter Dawyndt |
| Date: | 2015-09-28 |
| Time limit: | 10s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | PY_NBC |
RSS