a-conjecture-of-mine

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

main.go (2599B)

  1 package main
  2 
  3 // This program is a simple test for the following conjecture:
  4 
  5 // Let S: N -> N be the sum of the digits of a positive integer.
  6 // For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an interger.
  7 
  8 import (
  9     "os"
 10     "strconv"
 11 )
 12 
 13 type iter struct {
 14     Start uint
 15     End   uint
 16     Step  uint
 17 }
 18 
 19 const success = 0
 20 const fail = 1
 21 const invalidInput = 2
 22 
 23 func main() {
 24     if len(os.Args) > 1 {
 25         var nGoRoutines uint = 1
 26 
 27         if len(os.Args) > 2 {
 28             arg, err := strconv.ParseUint(os.Args[2], 10, 64)
 29             if err == nil && arg >= 1 {
 30                 nGoRoutines = uint(arg)
 31             }
 32         }
 33 
 34         max, err := strconv.ParseUint(os.Args[1], 10, 64)
 35         if err == nil {
 36             if counterexempl(uint(max), nGoRoutines) {
 37                 os.Exit(fail)
 38             } else {
 39                 os.Exit(success)
 40             }
 41         } else {
 42             os.Exit(invalidInput)
 43         }
 44     } else {
 45         os.Exit(invalidInput)
 46     }
 47 
 48 }
 49 
 50 func counterexempl(max uint, nGoRoutines uint) bool {
 51     sums := getSums(max)
 52 
 53     if nGoRoutines > 1 {
 54         channels := make([](chan bool), nGoRoutines)
 55 
 56         // Compute the result of each sub-range
 57         for i := uint(0); i < nGoRoutines; i++ {
 58             channels[i] = make(chan bool)
 59             it := iter{ uint(i), max, nGoRoutines }
 60 
 61             go counterexemplRange(it, &sums, channels[i])
 62         }
 63 
 64         // Listen for the computation to finish
 65         for _, c := range channels {
 66             if msg := <-c; msg {
 67                 return true
 68             }
 69         }
 70     } else {
 71         c := make(chan bool)
 72         it := iter{0, max, 1}
 73 
 74         go counterexemplRange(it, &sums, c)
 75 
 76         return <-c
 77     }
 78 
 79     return false
 80 }
 81 
 82 func counterexemplRange(it iter, sums *[]int, c chan bool) {
 83     for a := it.Start; a <= it.End; a += it.Step {
 84         for b := a; b <= it.End; b++ {
 85             diff := (*sums)[a+b] - (*sums)[a] - (*sums)[b]
 86 
 87             if diff%9 != 0 {
 88                 c <- true
 89                 close(c)
 90 
 91                 return
 92             }
 93         }
 94     }
 95 
 96     c <- false
 97     close(c)
 98 }
 99 
100 func getSums(max uint) []int {
101     maxRange := 2 * max + 1
102     sums := make([]int, maxRange)
103 
104     for i := range sums {
105         sums[i] = sumDigits(uint(i))
106     }
107 
108     return sums
109 }
110 
111 func sumDigits(n uint) int {
112     var sum uint
113 
114     for {
115         if n <= 0 {
116             return int(sum)
117         }
118 
119         sum += n % 10
120         n /= 10
121     }
122 }