# a-conjecture-of-mine

An exercise on polyglossy: the same problem solved on multiple languages

commitf14206ab3fb8a764b7125c2613b2cf5687011d74parentcdfc38f2a95be7bc519ca2506102e77990ea3f77Author:Pablo Escobar Gaviria <gark.garcia@protonmail.com>Date:Sat, 11 Jan 2020 19:28:56 -0200 Started further documenting the implementations.Diffstat:

M | README.md | | | 66 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++---- |

diff --git a/README.md b/README.md@@ -1,19 +1,18 @@ # A Conjecture of Mine An exercise on _polyglossy_. The same problem solved on multiple languages. -## The Problem - Mathematicians Version +# The Problem - Mathematicians Version Let <img src="https://latex.codecogs.com/svg.latex?S:&space;\mathbb{N}\rightarrow&space;\mathbb{N}"/> be the sum of the digits of a positive integer in a _[base 10 positional number system](https://en.wikipedia.org/wiki/Positional_notation)_. We have: <img src="https://latex.codecogs.com/svg.latex?\forall&space;a,&space;b&space;\in&space;\mathbb{N},&space;S_{a&space;+&space;b}&space;\equiv&space;S_a&space;+&space;S_b&space;\;\(\textup{mod}\;&space;9&space;\)"/> -### Addendum This conjecture can be generalized for any _positional number system_. Check out `proof.pdf` for more information. -## The Problem - Programmers Verison +# The Problem - Programmers Verison Let `S(n: uint) -> uint` be the sum of the digits of `n` in _[base 10](https://en.wikipedia.org/wiki/Decimal)_. Then, for all `a` and `b` of type `uint`, `S(a + b) - ( S(a) + S(b) ) % 9 == 0`. -## Performance +# Performance The conjecture was [proved by exhaustion](https://en.wikipedia.org/wiki/Proof_by_exhaustion) for the interval <img src="https://latex.codecogs.com/svg.latex?[0,&space;10^4]"/> in multiple language implementations. The performance of each language was then avaliated as the following _(*)_: |Language |Milliseconds| @@ -28,3 +27,62 @@ The conjecture was [proved by exhaustion](https://en.wikipedia.org/wiki/Proof_by |**Haskell** |28365 | _* out of date_ + +# Contributing +Contributions are welcomed! If you want to create a solution in a different language or improve the work on an existing implementation, feel free to help out. + +However, there are some guidelines. + +## The Algorithm + +The program should test the conjecture **for all pairs `(a, b)` where `0 <= a <= MAX`** +**and `0 <= b <= a`**, as this is sufficient to proof the conjecture +**for all pairs `(a, b)` between `0` and `MAX`**. The value of `MAX` should be provided in +the first command-line argument. + +The following algorithm should be used: + +``` +for a between 0 and MAX: + for b between 0 and a: + check if the conjecture holds for the pair (a, b) + if it fails, exit the process with exit code 1 + +exit the process with exit code 0 +``` + +Alternativelly, one could iterate `b` between `a` and `MAX`. + +### Concurency + +The use of concurrency is encoraged for implementations on languages that provide good +support for it. In the case concurrency is used, an additional, optional parameter `NPROCESSES` +should be passed to the application in the seccond command-line argument. + +The default value of `NPROCESSES` should be `1`. The algorithm should then be addapted to the +following: + +``` +for i between 0 and NPROCESSES: + lauch a process running counterexample(start=i) + +for i between 0 and NPROCESSES: + wait for the i-th process to signal it's results + if the process signals a counterexample was found, exit the main process with exit code 1 + +exit the main process with exit code 0 +``` + +The algorith for the `counterexample` routine should be the following: + +``` +for a between 0 and MAX by steps of NPROCESSES: + for b between 0 and a: + check if the conjecture holds for the pair (a, b) + if it fails, signal to the main process that a counterexample was found + +signal to the main process that no counterexample was found +``` + +The routine should only signal wheter or not a counterexample was found. +