- Commit
- 859cbc9ee4cabb7e64137965bf26f315d783996c
- Parent
- 416b7ca9325abe3c259646309fcb3e689abaff1f
- Author
- Gark Garcia <37553739+GarkGarcia@users.noreply.github.com>
- Date
Created Java and Go implementations.
Started working on an x86 implementation.
An exercise on polyglossy: the same problem solved on multiple languages
Created Java and Go implementations.
Started working on an x86 implementation.
7 files changed, 163 insertions, 11 deletions
Status | File Name | N° Changes | Insertions | Deletions |
Modified | .gitignore | 3 | 2 | 1 |
Added | Go/conjecture.go | 84 | 84 | 0 |
Modified | README.md | 3 | 2 | 1 |
Modified | Rust/src/main.rs | 14 | 7 | 7 |
Added | java.jar | 0 | 0 | 0 |
Modified | script.rb | 5 | 3 | 2 |
Added | x86/PROGRAM.ASM | 65 | 65 | 0 |
diff --git a/.gitignore b/.gitignore @@ -1,5 +1,6 @@ .vscode *.exe +*.img +*.IMG Statistics Latex -X86
diff --git a/Go/conjecture.go b/Go/conjecture.go @@ -0,0 +1,84 @@ +package main + +// This program is a simple test for the following conjecture: + +// Let S: N -> N be the sum of the digits of a positive integer. +// For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an interger. + +import ( + "bufio" + "fmt" + "math" + "os" + "strconv" + "strings" + "time" +) + +func main() { + fmt.Println("\nThis program is a simple test for the following conjecture:") + fmt.Println("\nLet S: N -> N be the sum of the digits of a positive integer.") + fmt.Println("For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an interger.") + fmt.Print("\nWhat value would you like to test the conjecture for? ") + + reader := bufio.NewReader(os.Stdin) + maxStr, _ := reader.ReadString('\n') + maxStr = strings.TrimSpace(maxStr) + + if max, err := strconv.ParseUint(maxStr, 10, 32); err == nil { + max := uint(max) + + fmt.Println("\nLOADING. . .") + tuple, found, elepsed := getCounterexample(max) + fmt.Printf("LOADED in %dms\n", elepsed.Nanoseconds()/int64(math.Pow10(6))) + + if !found { + fmt.Printf("\nThe conjecture is proved for all natural numbers smaller or equals to %d!\n", max) + } else { + fmt.Printf("\nThe conjecture is disproved! Here's a counterexample: (%d, %d)\n", tuple[0], tuple[1]) + } + } else { + fmt.Printf("\n'%s' isn't a natural number!\n", maxStr) + } +} + +func getCounterexample(max uint) (value [2]uint, found bool, elepsed time.Duration) { + start := time.Now() + + sums := getSums(max) + for a := uint(0); a <= max; a++ { + for b := a; b <= max; b++ { + diff := sums[a+b] - sums[a] - sums[b] + + if diff%9 != 0 { + return [2]uint{a, b}, true, time.Since(start) + } + } + } + + return [2]uint{0, 0}, false, time.Since(start) +} + +func getSums(max uint) []int { + maxRange := 2 * (max + 1) + sums := make([]int, maxRange, maxRange) + + for i := uint(0); i < maxRange; i++ { + sums[i] = sumDigits(i) + } + + return sums +} + +func sumDigits(n uint) int { + var sum uint + + for { + if n <= 0 { + return int(sum) + } + + sum += n % 10 + n /= 10 + } +}
diff --git a/README.md b/README.md @@ -11,7 +11,8 @@ The conjecture was [proved by exhaustion](https://en.wikipedia.org/wiki/Proof_by |Language |Milliseconds| |--------------|------------| -|**Rust** |80 | +|**Rust** |108 | +|**Go** |112 | |**C** |271 | |**JavaScript**|656 | |**Ruby** |9850 |
diff --git a/Rust/src/main.rs b/Rust/src/main.rs @@ -7,7 +7,7 @@ extern crate crossterm; extern crate num_cpus; extern crate rand; -use std::{env, thread, time::Instant, sync::mpsc, sync::mpsc::{Sender, Receiver}}; +use std::{env, thread, time::Instant, sync::{Arc, mpsc::{self, Sender, Receiver}}}; use crossterm::{terminal, input}; use rand::prelude::*; @@ -52,7 +52,7 @@ fn main() { } fn get_countrexpl(max: usize, n_threads: usize) -> Option<(usize, usize)> { - let sums = get_sums(max); + let sums = Arc::new(get_sums(max)); if max / n_threads > 0 && n_threads > 1 { @@ -92,7 +92,7 @@ fn get_countrexpl(max: usize, n_threads: usize) -> Option<(usize, usize)> { let thread_sums = sums.clone(); let child = thread::spawn(move || { - thread_countr_sd.send(get_range_countrexpl(thread_range, max, &thread_sums)) + thread_countr_sd.send(get_range_countrexpl(thread_range, thread_sums, max)) .expect(&format!("Thread n°{} was unable to sent a message trought the channel", i)); }); @@ -108,11 +108,11 @@ fn get_countrexpl(max: usize, n_threads: usize) -> Option<(usize, usize)> { None } else { - get_range_countrexpl((0..max).collect(), max, &sums) + get_range_countrexpl((0..max).collect(), sums, max) } } -fn get_range_countrexpl(range: Vec<usize>, max: usize, sums: &Vec<isize>) -> Option<(usize, usize)> { +fn get_range_countrexpl(range: Vec<usize>, sums: Arc<Vec<isize>>, max: usize) -> Option<(usize, usize)> { for a in range { for b in a..max { let difference = sums[a + b] - sums[a] - sums[b]; @@ -131,11 +131,11 @@ fn sum_digits(n: usize) -> isize { let mut part = n; while part != 0 { - sum += (part % 10) as isize; + sum += part % 10; part /= 10; } - sum + sum as isize } fn get_sums(max: usize) -> Vec<isize> {
diff --git a/script.rb b/script.rb @@ -9,8 +9,9 @@ class Integer sum = 0 while part > 0 - sum += part % 10 - part /= 10 + d, r = part.divmod(10) + sum += r + part = d end return sum
diff --git a/x86/PROGRAM.ASM b/x86/PROGRAM.ASM @@ -0,0 +1,64 @@ +.model tiny + +.code +org 100h + +start: + mov ax, 32 ; 1st + mov bx, 16 ; 2nd + + call test_pair + + ; Quit the program + mov ah, 4ch + int 21h + +test_pair: + ; Calculate the 1st + 2nd into cx + mov cx, ax + add cx, bx + + push cx ; Push 1st + 2nd to the stack + push bx ; Push 2nd to the stack + + call sum_digits ; Calculate S(1st) into bx + + pop ax ; Store the value of 2nd in ax + push bx ; Push S(1st) to the stack + call sum_digits ; Calculate S(2nd) into bx + + pop ax ; Store S(1st) in ax + add ax, bx ; Store S(1st) + S(2nd) in ax + pop bx ; Store 1st + 2nd in bx + push ax ; Push S(1st) + S(2nd) to the stack + + mov ax, bx ; Store 1st + 2nd in ax + call sum_digits ; Calculate S(1st + 2nd) into bx + + pop ax ; Store S(1st) + S(2nd) in ax + sub bx, ax ; Calculate S(1st + 2nd) - (S(1st) + S(2nd)) into bx + + + mov ax, bx ; Store S(1st + 2nd) - (S(1st) + S(2nd)) in ax + mov cx, 9 ; Set the devident to 9 + mov dx, 0 ; Clear the register where the rest will be stored + div cx + + cmp dx, 0 + ret + +sum_digits: + mov cx, 10 ; Store the devident in cx + mov bx, 0 ; Clear the register where the result will be stored +sum_loop: + mov dx, 0 ; Clear the rest of the division + + div cx ; Divide ax by cx + add bx, dx ; Add the rest of the division ax/cx to bx + + ; Loop until ax equals 0 + cmp ax, 0 + jg short sum_loop + ret + +end start+ \ No newline at end of file