- Commit
- b30d26a8b07ebc076c5cde303cf97f9a75546be2
- Parent
- fbed5358ac751f679fafc0bfec4939d1deb09cce
- Author
- Gark Garcia <37553739+GarkGarcia@users.noreply.github.com>
- Date
Merged benchmarking.
a-conjecture-of-mine
An exercise on polyglossy: the same problem solved on multiple languages
Diffstat
29 files changed, 409 insertions, 843 deletions
diff --git a/.gitignore b/.gitignore @@ -1,6 +1,8 @@ +.idea .vscode *.exe *.img *.IMG Statistics Latex +Q#
diff --git a/C++/main.cpp b/C++/main.cpp @@ -0,0 +1,83 @@ +#include <chrono> +#include <iostream> +#include <string> +#include <thread> +#include <map> +#include <vector> +#include <charconv> + +#define SUCCESS 0 +#define FAIL 1 +#define INVALID_INPUT 2 + +std::map<unsigned int, unsigned int> sums_cache; + +inline unsigned int sum_digits(unsigned int n) +{ + unsigned int sum = 0; + while (n != 0) + { + sum += (n % 10); + n /= 10; + } + + return sum; +} + +void get_counterexpl_thread(unsigned int start, unsigned int max, unsigned int interval) +{ + for (auto a = start; a <= max; a += interval) + for (auto b = a; b <= max; b++) + { + auto diff = sums_cache[a + b] - (sums_cache[a] + sums_cache[b]); + + if (diff % 9 != 0) + exit(FAIL); + } +} + +bool read_first_arg(int argc, char *argv[], unsigned int *value) +{ + if (argc > 1) + { + std::string value_str = argv[1]; + + try + { + *value = std::stoul(value_str); + return true; + } + catch (...) + { + return false; + } + } + else return false; +} + +int main(int argc, char *argv[]) +{ + unsigned int max; + if (read_first_arg(argc, argv, &max)) + { + auto n_threads = std::thread::hardware_concurrency(); + std::vector<std::thread> threads; + + // Builds the sums cache + for (int i = 0; i != 2 * max; i++) + sums_cache[i] = sum_digits(i); + + // Distributes calculations across threads evenlly + for (int i = 0; i < n_threads; i++) + { + auto thread = std::thread(get_counterexpl_thread, i, max, n_threads); + thread.join(); + } + + return SUCCESS; + } + else + { + return INVALID_INPUT; + } +}+ \ No newline at end of file
diff --git a/C/main.c b/C/main.c @@ -1,6 +1,5 @@ #include <stdlib.h> #include <stdio.h> -#include <time.h> #include <pthread.h> // Imports to get system information @@ -13,13 +12,17 @@ #include <unistd.h> #endif +#define SUCCESS 0 +#define FAIL 1 +#define INVALID_INPUT 2 + // 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 integer. -int err = 0; // Global error condition -int *sums_cache; // Shared memory between threads +int err = SUCCESS; // Global error condition +int *sums_cache; // Shared memory between threads // Memory structure to pass arguments to threads using the pthreads library struct iter_info @@ -80,66 +83,59 @@ int get_counterexpl_iter(struct iter_info *iter) { if ((sums_cache[a + b] - (sums_cache[a] + sums_cache[b])) % 9 != 0) { - printf("\nThe conjecture is disproved! Here's a counterexample: (%u, %u)", a, b); err = 1; - return 1; + return FAIL; } } - return 0; + return SUCCESS; } -int main() +int main(int argc, char *argv[]) { + if (argc > 1) { - int i; - int num_threads = get_num_cores(); - pthread_t thread_ids[num_threads]; - struct iter_info thread_iters[num_threads]; - unsigned int MAX = 0; - - printf("\nThis program is a simple test for the following conjecture:\n"); - printf("Let S: N -> N be the sum of the digits of a positive integer.\n"); - printf("For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an integer.\n"); - printf("\nWhat value would you like to test the conjecture for? "); - - scanf_s("%u", &MAX); + // Get the length of argv[1] + int len; + for (len = 0; argv[len] != '\0'; len++); - printf("\nLOADING. . ."); - clock_t start = clock(), end; + // Check if argv[1] is numeric + for (int i = 0; i < len; i++) + if (argv[1][i] < '0' || argv[1][i] > '9') + return INVALID_INPUT; - // Create the sums cache - int sums_c = 2 * (MAX + 1); - sums_cache = malloc(sizeof(int) * sums_c * 2); //original (sizeof(int)* sums_c) causing seg faults in multi-threading - for (i = 0; i <= sums_c; i++) - sums_cache[i] = sum_digits(i); - + unsigned int max = strtoul(argv[1], NULL, 10); + int n_threads = get_num_cores(); + pthread_t thread_ids[n_threads]; + struct iter_info thread_iters[n_threads]; - // Create the threads, divide the task into number of threads equivalent to number - // of cores on the host machine + // Create the sums cache + int sums_c = 2 * max; + sums_cache = malloc(sizeof(int) * sums_c * 2); //original (sizeof(int)* sums_c) causing seg faults in multi-threading + for (int i = 0; i <= sums_c; i++) + sums_cache[i] = sum_digits(i); - for (i = 0; i < num_threads; i++) - { - thread_iters[i].start = i; - thread_iters[i].max = MAX; - thread_iters[i].interval = num_threads; - err = pthread_create(&thread_ids[i], NULL, get_counterexpl_iter, &thread_iters[i]); - - if (err) printf("Unable to create thread : %d", err); - } - for (i = 0; i < num_threads; i++) - { - err = pthread_join(thread_ids[i], NULL); - if (err) printf("Unable to join threads :%d\n", err); - } + // Create the threads, divide the task into number of threads equivalent to number + // of cores on the host machine + for (int i = 0; i < n_threads; i++) + { + thread_iters[i].start = i; + thread_iters[i].max = max; + thread_iters[i].interval = n_threads; + err = pthread_create(&thread_ids[i], NULL, get_counterexpl_iter, &thread_iters[i]); - if (err) - return 1; + if (err) printf("Unable to create thread : %d\n", err); + } - end = clock(); - printf("\nLOADED. . . in %ums [%d Threads]\n", (unsigned)((end - start) * 1000 / CLOCKS_PER_SEC), num_threads); - printf("\nThe conjecture is proved for all natural numbers smaller or equals to %u!", MAX); + for (int i = 0; i < n_threads; i++) + { + err = pthread_join(thread_ids[i], NULL); + if (err) printf("Unable to join threads : %d\n", err); + } - return 0; + return err; + } else { + return INVALID_INPUT; + } }
diff --git a/CPP/acom.vcxproj b/CPP/acom.vcxproj @@ -1,106 +0,0 @@ -<?xml version="1.0" encoding="utf-8"?> -<Project DefaultTargets="Build" ToolsVersion="15.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003"> - <ItemGroup Label="ProjectConfigurations"> - <ProjectConfiguration Include="Debug|Win32"> - <Configuration>Debug</Configuration> - <Platform>Win32</Platform> - </ProjectConfiguration> - <ProjectConfiguration Include="Release|Win32"> - <Configuration>Release</Configuration> - <Platform>Win32</Platform> - </ProjectConfiguration> - <ProjectConfiguration Include="Debug|x64"> - <Configuration>Debug</Configuration> - <Platform>x64</Platform> - </ProjectConfiguration> - <ProjectConfiguration Include="Release|x64"> - <Configuration>Release</Configuration> - <Platform>x64</Platform> - </ProjectConfiguration> - </ItemGroup> - <PropertyGroup Label="Globals"> - <VCProjectVersion>15.0</VCProjectVersion> - <ProjectGuid>{322CF2CD-B0A8-4D71-A60B-7755F8D5BECC}</ProjectGuid> - <Keyword>Win32Proj</Keyword> - <RootNamespace>CPP</RootNamespace> - <WindowsTargetPlatformVersion>10.0.17763.0</WindowsTargetPlatformVersion> - </PropertyGroup> - <Import Project="$(VCTargetsPath)\Microsoft.Cpp.Default.props" /> - <PropertyGroup Label="Configuration"> - <ConfigurationType>Application</ConfigurationType> - <UseDebugLibraries>false</UseDebugLibraries> - <PlatformToolset>v141</PlatformToolset> - <WholeProgramOptimization>true</WholeProgramOptimization> - <CharacterSet>Unicode</CharacterSet> - <OutDir>out/</OutDir> - </PropertyGroup> - <Import Project="$(VCTargetsPath)\Microsoft.Cpp.props" /> - <ImportGroup Label="ExtensionSettings"> - </ImportGroup> - <ImportGroup Label="Shared"> - </ImportGroup> - <ImportGroup Label="PropertySheets"> - <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" /> - </ImportGroup> - <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Debug|x64'"> - <CodeAnalysisRuleSet>MixedRecommendedRules.ruleset</CodeAnalysisRuleSet> - <RunCodeAnalysis>true</RunCodeAnalysis> - </PropertyGroup> - <ItemDefinitionGroup Condition="'$(Platform)'=='Win32'"> - <ClCompile> - <WarningLevel>Level3</WarningLevel> - <Optimization>MaxSpeed</Optimization> - <FunctionLevelLinking>true</FunctionLevelLinking> - <IntrinsicFunctions>true</IntrinsicFunctions> - <SDLCheck>true</SDLCheck> - <PreprocessorDefinitions>WIN32;NDEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions> - <ConformanceMode>false</ConformanceMode> - <AdditionalIncludeDirectories>$(ProjectDir)include;</AdditionalIncludeDirectories> - <RuntimeLibrary Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'">MultiThreadedDebugDLL</RuntimeLibrary> - </ClCompile> - <Link> - <EnableCOMDATFolding>true</EnableCOMDATFolding> - <OptimizeReferences>true</OptimizeReferences> - <GenerateDebugInformation>true</GenerateDebugInformation> - <SubSystem>Console</SubSystem> - <AdditionalDependencies>Ws2_32.lib;%(AdditionalDependencies)</AdditionalDependencies> - <AdditionalLibraryDirectories>%(AdditionalLibraryDirectories)</AdditionalLibraryDirectories> - </Link> - </ItemDefinitionGroup> - <ItemDefinitionGroup Condition="'$(Platform)'=='x64'"> - <ClCompile> - <WarningLevel>Level3</WarningLevel> - <Optimization>MaxSpeed</Optimization> - <FunctionLevelLinking>true</FunctionLevelLinking> - <IntrinsicFunctions>true</IntrinsicFunctions> - <SDLCheck>true</SDLCheck> - <PreprocessorDefinitions>NDEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions> - <ConformanceMode>false</ConformanceMode> - <AdditionalIncludeDirectories>$(ProjectDir)include;%(AdditionalIncludeDirectories)</AdditionalIncludeDirectories> - <FavorSizeOrSpeed Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">Speed</FavorSizeOrSpeed> - <InlineFunctionExpansion Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">AnySuitable</InlineFunctionExpansion> - <OmitFramePointers Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">true</OmitFramePointers> - <FloatingPointModel Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">Fast</FloatingPointModel> - <EnableParallelCodeGeneration Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">true</EnableParallelCodeGeneration> - <StringPooling Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">true</StringPooling> - <LanguageStandard Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">stdcpplatest</LanguageStandard> - <MultiProcessorCompilation Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">true</MultiProcessorCompilation> - <EnablePREfast Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">true</EnablePREfast> - <EnableFiberSafeOptimizations Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">true</EnableFiberSafeOptimizations> - <FloatingPointModel Condition="'$(Configuration)|$(Platform)'=='Release|x64'">Fast</FloatingPointModel> - </ClCompile> - <Link> - <EnableCOMDATFolding>true</EnableCOMDATFolding> - <OptimizeReferences>true</OptimizeReferences> - <GenerateDebugInformation>true</GenerateDebugInformation> - <SubSystem>Console</SubSystem> - </Link> - </ItemDefinitionGroup> - <Import Project="$(VCTargetsPath)\Microsoft.Cpp.targets" /> - <ItemGroup> - <ClCompile Include="main.cpp" /> - </ItemGroup> - <ItemGroup> - <None Include="main.cpp.old" /> - </ItemGroup> -</Project>- \ No newline at end of file
diff --git a/CPP/main.cpp b/CPP/main.cpp @@ -1,70 +0,0 @@ -#include <chrono> -#include <iostream> -#include <string> -#include <thread> -#include <map> -#include <vector> - -#define EXIT_FAILURE 1 -#define EXIT_SUCCESS 0 - -std::map<unsigned int, unsigned int> sum_cache; - -inline unsigned int sum_digits(unsigned int n) { - unsigned int sum = 0; - while (n != 0) { - sum += (n % 10); - n /= 10; - } - return sum; -} - -void get_ce(unsigned int a, unsigned int m) { - unsigned int ad; - for (; a != m; --a) { - ad = sum_cache[a]; - for (unsigned int b = a; b != 0; --b) { - unsigned int r = (ad + sum_cache[b] - sum_cache[a + b]); - switch (r) { - case 0: - case 9: - case 18: - case 27: - case 36: - case 45: - break; - default: - if (r % 9 == 0) break; - std::cout - << "The conjecture was disproved! Here is a counter example: " - << a << ", " << b << "\n"; - exit(EXIT_FAILURE); - break; - } - } - } -} - -int main(int argc, char** argv) { - if (argc <= 1) { - std::cerr << "Specify the interval as an argument"; - return EXIT_FAILURE; - } - int i = std::thread::hardware_concurrency() * 2; - unsigned int a = std::stoi(argv[1]) / i; - std::vector<std::thread> threads; - - for (int z = 0; z != 2 * (a + 1); z++) { - sum_cache[z] = sum_digits(z); - } - auto start = std::chrono::steady_clock::now(); - for (; i; i--) threads.push_back(std::thread(get_ce, (a * i), (a * (i - 1)))); - for (std::thread& thread : threads) thread.join(); - auto end = std::chrono::steady_clock::now(); - std::cout << "The conjecture is proved for all natural numbers smaller or " - "equals to " - << argv[1] << ". The following was done in " - << std::chrono::duration<double, std::milli>(end - start).count() - << " ms.\n"; - return EXIT_SUCCESS; -}- \ No newline at end of file
diff --git a/CPP/main.perdigit.cpp b/CPP/main.perdigit.cpp @@ -1,155 +0,0 @@ -#include <chrono> -#include <iostream> -#include <string> - -#define EXIT_FAILURE 1 -#define EXIT_SUCCESS 0 - -#define DEBUG 0 -#define DEBUG_F 0 - -static unsigned int pow10[10] = { - 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000}; - -class number { - private: - inline unsigned int getlen(unsigned long n) { - if (n < 100000) { - if (n < 100) { - if (n < 10) - return 1; - else - return 2; - } else { - if (n < 1000) - return 3; - else { - if (n < 10000) - return 4; - else - return 5; - } - } - } else { - if (n < 10000000) { - if (n < 1000000) - return 6; - else - return 7; - } else { - if (n < 100000000) - return 8; - else { - if (n < 1000000000) - return 9; - else - return 10; - } - } - } - } - - public: - unsigned short* state; - unsigned int len = 0; - unsigned int num = 0; - number(unsigned int n) { - if (DEBUG_F) std::cout << "CREATE: " << n << "\n"; - this->num = n; - this->len = this->getlen(n); - this->state = new unsigned short[this->len](); - for (unsigned short i = 0; i < this->len; ++i) { - this->state[i] = static_cast<unsigned short>(n % 10); - n /= 10; - } - } - ~number() { - if (DEBUG_F) std::cout << "DEL: " << this->get() << "\n"; - delete[] this->state; - } - void set(unsigned int n) { - if (DEBUG_F) std::cout << "SET: " << n << "\n"; - this->num = n; - for (unsigned short i = 0; i < this->len; ++i) { - this->state[i] = static_cast<unsigned short>(n % 10); - n /= 10; - } - } - bool zero() { - if (DEBUG_F) std::cout << "ZERO: " << this->get() << "\n"; - for (unsigned int i = 0; i < this->len; i++) { - if (this->state[i] != 0) return false; - } - return true; - } - unsigned int get() { - unsigned int n = 0; - for (unsigned int i = 0; i < this->len; i++) { - n += static_cast<unsigned int>(this->state[i] * pow10[i]); - } - - if (n != this->num) { - std::cerr << "UNEQUAL: " << n << ", " << this->num << "\n"; - exit(1); - } - return n; - } - unsigned int sum() { - if (DEBUG_F) std::cout << "SUM: " << this->get() << "\n"; - unsigned int n = 0; - for (unsigned int i = 0; i < this->len; i++) { - n += (this->state[i]); - } - return n; - } - void operator--() { - this->num--; - if (this->state[0] != 0) - this->state[0]--; - else { - for (unsigned int i = 1; i < this->len; i++) { - if (this->state[i] != 0) { - this->state[i]--; - for (unsigned int z = i - 1; 1; z--) { - this->state[z] = 9; - if (z == 0) return; - } - } - } - } - } - unsigned int operator+(number* b) { - if (DEBUG_F) std::cout << "SUM: " << this->get() + b->get() << "\n"; - return (this->get() + b->get()); - } -}; - -int main(int argc, char** argv) { - if (argc <= 1) { - std::cerr << "Specify the interval as an argument"; - return EXIT_FAILURE; - } - unsigned int arg = std::stoi(argv[1]); - number a = number(arg), b = number(arg), c = number(arg); - auto start = std::chrono::steady_clock::now(); - for (a = number(std::stoul(argv[1])); !a.zero(); --a) { - for (b.set(a.get()); !b.zero(); --b) { - if (DEBUG) - std::cout << "A: " << a.get() << ", B: " << b.get() - << ", A_SUM: " << a.sum() << ", B_SUM: " << b.sum() << "\n"; - c.set((a + &b)); - if (((a.sum() + b.sum()) - c.sum()) % 9 != 0) { - std::cout << "The conjecture was disproved! Here is a counter example: " - << a.get() << ", " << b.get() << "\n"; - return EXIT_FAILURE; - } - } - } - auto end = std::chrono::steady_clock::now(); - std::cout << "The conjecture is proved for all natural numbers smaller or " - "equals to " - << argv[1] << ". The following was done in " - << std::chrono::duration<double, std::milli>(end - start).count() - << " ms.\n"; - return EXIT_SUCCESS; -}- \ No newline at end of file
diff --git a/Go/conjecture.go b/Go/conjecture.go @@ -6,100 +6,84 @@ package main // 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" ) +type iter struct { + Start uint + Max uint + Interval uint +} + +const success = 0 +const fail = 1 +const invalidInput = 2 + func main() { - nThreads := uint(1) if len(os.Args) > 0 { - if arg, err := strconv.ParseUint(os.Args[0], 10, 32); err == nil { - if arg >= 1 { + nThreads := uint(1) + + if len(os.Args) > 1 { + if arg, err := strconv.ParseUint(os.Args[2], 10, 64); err == nil && arg >= 1 { nThreads = uint(arg) } } - } - - 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 integer.") - 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, nThreads) - fmt.Printf("LOADED in %dms [%d Go Routines]\n", elepsed.Nanoseconds()/int64(math.Pow10(6)), nThreads) - if !found { - fmt.Printf("\nThe conjecture is proved for all natural numbers smaller or equals to %d!\n", max) + if max, err := strconv.ParseUint(os.Args[0], 10, 64); err == nil { + if getCounterexample(uint(max), nThreads) { + os.Exit(fail) + } else { + os.Exit(success) + } } else { - fmt.Printf("\nThe conjecture is disproved! Here's a counterexample: (%d, %d)\n", tuple[0], tuple[1]) + os.Exit(invalidInput) } } else { - fmt.Printf("\n'%s' isn't a natural number!\n", maxStr) + os.Exit(invalidInput) } + } -func getCounterexample(max uint, nThreads uint) (value [2]uint, found bool, elepsed time.Duration) { - start := time.Now() +func getCounterexample(max uint, nThreads uint) bool { sums := getSums(max) - mRange := make([]uint, max+1) if nThreads > 1 { - channels := make([](chan [2]uint), nThreads) + channels := make([](chan bool), nThreads) // Compute the result of each sub-range for i := 0; i < int(nThreads); i++ { - iter := make(chan uint) - channels[i] = make(chan [2]uint) + channels[i] = make(chan bool) + it := iter{uint(i), max, nThreads} - go arithmeticProg(iter, uint(i), nThreads, max) - go getCounterRange(iter, max, &sums, channels[i]) + go getCounterIter(it, &sums, channels[i]) } // Listen for the computation to finish for _, c := range channels { - for msg := range c { - return msg, true, time.Since(start) + if msg := <-c; msg { + return true } } } else { - c := make(chan [2]uint) + c := make(chan bool) + it := iter{0, max, 1} - for i := range mRange { - mRange[i] = uint(i) - } + go getCounterIter(it, &sums, c) - iter := make(chan uint) - go arithmeticProg(iter, 0, nThreads, max) - go getCounterRange(iter, max, &sums, c) - - for msg := range c { - return msg, true, time.Since(start) - } + return <-c } - return [2]uint{0, 0}, false, time.Since(start) + return false } -func getCounterRange(rang chan uint, max uint, sums *[]int, c chan [2]uint) { - for a := range rang { - for b := a; b <= max; b++ { +func getCounterIter(it iter, sums *[]int, c chan bool) { + for a := it.Start; a <= it.Max; a += it.Interval { + for b := a; b <= it.Max; b++ { diff := (*sums)[a+b] - (*sums)[a] - (*sums)[b] if diff%9 != 0 { - c <- [2]uint{a, b} + c <- true close(c) return @@ -107,6 +91,7 @@ func getCounterRange(rang chan uint, max uint, sums *[]int, c chan [2]uint) { } } + c <- false close(c) } @@ -133,11 +118,3 @@ func sumDigits(n uint) int { n /= 10 } } - -func arithmeticProg(iter chan uint, start uint, delta uint, bound uint) { - for i := start; i <= bound; i += delta { - iter <- i - } - - close(iter) -}
diff --git a/Haskell/.gitignore b/Haskell/.gitignore @@ -1,3 +1,4 @@ .stack-work +.idea *.cabal stack.yaml \ No newline at end of file
diff --git a/Haskell/app/Main.hs b/Haskell/app/Main.hs @@ -1,58 +1,49 @@ -- The following 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. +-- For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an integer. module Main where import Numeric import Numeric.Natural -import System.Clock +import System.Environment +import System.Exit import Control.Monad(foldM) -main :: IO () +main :: IO Int main = do - putStrLn "\nThis program is a simple test for the following conjecture:\n" - putStrLn "Let S: N -> N be the sum of the digits of a positive integer." - putStrLn "For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an interger.\n" - putStrLn "What value would you like to test the conjecture for?" - maxStr <- getLine - - case readDec maxStr :: [(Natural, String)] of - [(max, "")] -> do - putStrLn "\nLOADING. . ." - start <- getTime Monotonic - case counter' max of - Nothing -> putEnd start ("\nThe conjecture is proved for all natural numbers smaller or equals to " ++ show max ++ "!") - Just c -> putEnd start ("\nThe conjecture is disproved! Here's a counterexample: (" ++ (show $ fst $ c) ++ ", " - ++ (show $ snd $ c) ++ ")") - - _ -> putStrLn $ "\n'" ++ maxStr ++ "' is not a natural number!" + args <- getArgs + + if length args > 0 + then case readDec (args !! 0) :: [(Natural, String)] of + [(max, "")] -> if counter' max then exitFailure else exitSuccess + + _ -> exitInvalidInput + + else exitInvalidInput sum' :: Natural -> Natural -sum' x = case x of - 0 -> 0 - x -> (x `mod` 10) + sum' (x `div` 10) +sum' n + | n < 10 = n + | otherwise = (n `mod` 10) + sum' (n `div` 10) test' :: Natural -> Natural -> Bool test' a b = let s(x) = fromEnum $ sum' x in (s(a + b) - s(a) - s(b)) `mod` 9 == 0 -counter' :: Natural -> Maybe (Natural, Natural) +counter' :: Natural -> Bool counter' max = case foldM f max [0..max] of - Left (a, b) -> Just (a, b) - Right _ -> Nothing + Left _ -> True + Right _ -> False where f a b = iter' b max -iter' :: Natural -> Natural -> Either (Natural, Natural) Natural +iter' :: Natural -> Natural -> Either () Natural iter' a max = case foldM f a [a..max] of - Left b -> Left (a, b) + Left _ -> Left () Right _ -> Right (a - 1) where f i b | test' a b = Right (i + 1) - | otherwise = Left b + | otherwise = Left () -putEnd :: TimeSpec -> String -> IO () -putEnd start msg = do - end <- getTime Monotonic - let t = end - start in putStrLn $ "LOADED. . . in " ++ show (sec t * 10^3 + nsec t `div` 10^6) ++ "ms [1 Thread]" - putStrLn $ msg- \ No newline at end of file +exitInvalidInput :: IO Int +exitInvalidInput = exitWith (ExitFailure 2)+ \ No newline at end of file
diff --git a/Haskell/package.yaml b/Haskell/package.yaml @@ -2,7 +2,7 @@ name: conjecture version: 1.0.0.0 license: BSD3 author: "GarkGarcia" -maintainer: "thiago.brevidelli.garcia@gmail.com" +maintainer: "thiago.brevidelli.garcia@protonmail.com" copyright: "2019 GarkGarcia" extra-source-files: [] @@ -18,7 +18,6 @@ description: This program is a simple test for a little conjecture of mine. dependencies: - base >= 4.7 && < 5 - - clock == 0.7.2 executables: haskell: @@ -29,5 +28,4 @@ executables: - -rtsopts - -with-rtsopts=-N - -O - dependencies: - - clock == 0.7.2- \ No newline at end of file + dependencies: []+ \ No newline at end of file
diff --git a/Java/.gitignore b/Java/.gitignore @@ -0,0 +1,4 @@ +.idea +out +src/META-INF +Java.iml
diff --git a/Java/src/conjecture/Main.java b/Java/src/conjecture/Main.java @@ -0,0 +1,64 @@ +package conjecture; + +// The following 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 integer. + +import java.util.InputMismatchException; + +public class Main { + private static final int SUCCESS = 0; + private static final int FAIL = 1; + private static final int INVALID_INPUT = 2; + + public static void main(String[] args) { + try { + int max = Integer.parseInt(args[0]); + + if (getCounterexample(max)) { + System.exit(FAIL); + } else { + System.exit(SUCCESS); + } + } catch (InputMismatchException error) { + System.exit(INVALID_INPUT); + } + + } + + private static Boolean getCounterexample(int max) { + int[] sum = getSums(max); + + for (int a = 0; a <= max; a++) + for (int b = a; b <= max; b++) { + int diff = sum[a + b] - (sum[a] + sum[b]); + + if (diff % 9 != 0) + return true; + } + + return false; + } + + private static int[] getSums(int max) { + int maxRange = 2 * (max + 1); + int[] sums = new int[maxRange]; + + for (int i = 0; i < maxRange; i++) + sums[i] = sumDigits(i); + + return sums; + } + + private static int sumDigits(int n) { + int num = Math.abs(n), sum = 0; + + while (num > 0) { + sum += num % 10; + num /= 10; + } + + return sum; + } +}+ \ No newline at end of file
diff --git a/Kotlin/.gitignore b/Kotlin/.gitignore @@ -0,0 +1,2 @@ +.idea +out+ \ No newline at end of file
diff --git a/Kotlin/.idea/vcs.xml b/Kotlin/.idea/vcs.xml @@ -1,6 +0,0 @@ -<?xml version="1.0" encoding="UTF-8"?> -<project version="4"> - <component name="VcsDirectoryMappings"> - <mapping directory="$PROJECT_DIR$/.." vcs="Git" /> - </component> -</project>- \ No newline at end of file
diff --git a/Kotlin/out/production/Kotlin/META-INF/Kotlin.kotlin_module b/Kotlin/out/production/Kotlin/META-INF/Kotlin.kotlin_module Binary files differ.
diff --git a/Kotlin/out/production/Kotlin/conjecture/MainKt.class b/Kotlin/out/production/Kotlin/conjecture/MainKt.class Binary files differ.
diff --git a/Kotlin/out/production/Kotlin/conjecture/Option$None.class b/Kotlin/out/production/Kotlin/conjecture/Option$None.class Binary files differ.
diff --git a/Kotlin/out/production/Kotlin/conjecture/Option$Some.class b/Kotlin/out/production/Kotlin/conjecture/Option$Some.class Binary files differ.
diff --git a/Kotlin/out/production/Kotlin/conjecture/Option.class b/Kotlin/out/production/Kotlin/conjecture/Option.class Binary files differ.
diff --git a/Kotlin/src/main.kt b/Kotlin/src/main.kt @@ -1,7 +1,7 @@ package conjecture import kotlin.math.absoluteValue -import kotlin.system.measureTimeMillis +import kotlin.system.exitProcess // The following program is a simple test for the following conjecture: @@ -9,49 +9,29 @@ import kotlin.system.measureTimeMillis // For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an integer. fun main(args: Array<String>) { - println("\nThe following program is a simple test for the following conjecture:\n") - println("Let S: N -> N be the sum of the digits of a positive integer.") - println("For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an integer.\n") - print("What value would you like to test the conjecture for? ") - - val maxStr = readLine().orEmpty() try { - val max = maxStr.toInt() - - println("\nLOADING. . .") + val max = args[0].toInt() - val (elapsed, counter) = counterexample(max) - println("LOADED. . . in ${elapsed}ms\n") - - when (counter) { - is Option.None -> println("The conjecture is proved for all natural numbers smaller or equals to $max!") - is Option.Some<Pair<Int, Int>> -> { - val (a, b) = counter.value - println("The conjecture is disproved! Here's a counterexample: ($a}, $b)") - } - } + if (counterexample(max)) exitProcess(1) + else exitProcess(0) - } catch (_: NumberFormatException) { - println("\n'$maxStr' is not a natural number!") + } catch (_: Exception) { + exitProcess(2) } - } -internal fun counterexample(max: Int): Pair<Long, Option<Pair<Int, Int>>> { - var result: Option<Pair<Int, Int>> = Option.None +internal fun counterexample(max: Int): Boolean { + val sum = sums(max) - return Pair( - measureTimeMillis { - val sum = sums(max) + for (a in 0..max) + for (b in a..max) { + val diff = sum[a + b] - sum[a] - sum[b] - for (a in 0..max) - for (b in a..max) { - val diff = sum[a + b] - sum[a] - sum[b] + if (diff % 9 != 0) + return true + } - if (diff % 9 != 0) - result = Option.Some(Pair(a, b)) - } - }, result) + return false } fun sums (max: Int): IntArray { @@ -59,25 +39,19 @@ fun sums (max: Int): IntArray { val sums = IntArray(maxRange) for (i in 0 until maxRange) - sums[i] = i.sum + sums[i] = sumDigits(i) return sums } -val Int.sum: Int - get() { - var sum = 0 - var num = this.absoluteValue - - while (num > 0) { - sum += num % 10 - num /= 10 - } +fun sumDigits(n: Int): Int { + var sum = 0 + var num = n.absoluteValue - return sum + while (num > 0) { + sum += num % 10 + num /= 10 } -sealed class Option<out T> { - object None : Option<Nothing>() - data class Some<out A>(val value: A) : Option<A>() + return sum } \ No newline at end of file
diff --git a/Rust/Cargo.lock b/Rust/Cargo.lock @@ -1,92 +1,7 @@ [[package]] -name = "crossterm" -version = "0.6.0" -source = "registry+https://github.com/rust-lang/crates.io-index" -dependencies = [ - "crossterm_cursor 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)", - "crossterm_input 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)", - "crossterm_screen 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)", - "crossterm_style 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)", - "crossterm_terminal 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)", - "crossterm_utils 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)", -] - -[[package]] -name = "crossterm_cursor" -version = "0.1.0" -source = "registry+https://github.com/rust-lang/crates.io-index" -dependencies = [ - "crossterm_utils 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)", - "crossterm_winapi 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)", - "winapi 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)", -] - -[[package]] -name = "crossterm_input" -version = "0.1.0" -source = "registry+https://github.com/rust-lang/crates.io-index" -dependencies = [ - "crossterm_utils 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)", - "crossterm_winapi 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)", - "libc 0.2.44 (registry+https://github.com/rust-lang/crates.io-index)", - "winapi 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)", -] - -[[package]] -name = "crossterm_screen" -version = "0.1.0" -source = "registry+https://github.com/rust-lang/crates.io-index" -dependencies = [ - "crossterm_utils 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)", - "crossterm_winapi 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)", - "winapi 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)", -] - -[[package]] -name = "crossterm_style" -version = "0.1.0" -source = "registry+https://github.com/rust-lang/crates.io-index" -dependencies = [ - "crossterm_utils 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)", - "crossterm_winapi 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)", - "winapi 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)", -] - -[[package]] -name = "crossterm_terminal" -version = "0.1.0" -source = "registry+https://github.com/rust-lang/crates.io-index" -dependencies = [ - "crossterm_cursor 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)", - "crossterm_utils 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)", - "crossterm_winapi 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)", - "libc 0.2.44 (registry+https://github.com/rust-lang/crates.io-index)", -] - -[[package]] -name = "crossterm_utils" -version = "0.1.0" -source = "registry+https://github.com/rust-lang/crates.io-index" -dependencies = [ - "crossterm_winapi 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)", - "libc 0.2.44 (registry+https://github.com/rust-lang/crates.io-index)", - "termios 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)", - "winapi 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)", -] - -[[package]] -name = "crossterm_winapi" -version = "0.1.1" -source = "registry+https://github.com/rust-lang/crates.io-index" -dependencies = [ - "winapi 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)", -] - -[[package]] name = "digital_sum" version = "0.1.0" dependencies = [ - "crossterm 0.6.0 (registry+https://github.com/rust-lang/crates.io-index)", "num_cpus 1.8.0 (registry+https://github.com/rust-lang/crates.io-index)", ] @@ -103,45 +18,6 @@ dependencies = [ "libc 0.2.44 (registry+https://github.com/rust-lang/crates.io-index)", ] -[[package]] -name = "termios" -version = "0.3.1" -source = "registry+https://github.com/rust-lang/crates.io-index" -dependencies = [ - "libc 0.2.44 (registry+https://github.com/rust-lang/crates.io-index)", -] - -[[package]] -name = "winapi" -version = "0.3.6" -source = "registry+https://github.com/rust-lang/crates.io-index" -dependencies = [ - "winapi-i686-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)", - "winapi-x86_64-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)", -] - -[[package]] -name = "winapi-i686-pc-windows-gnu" -version = "0.4.0" -source = "registry+https://github.com/rust-lang/crates.io-index" - -[[package]] -name = "winapi-x86_64-pc-windows-gnu" -version = "0.4.0" -source = "registry+https://github.com/rust-lang/crates.io-index" - [metadata] -"checksum crossterm 0.6.0 (registry+https://github.com/rust-lang/crates.io-index)" = "91f04a703cb52c7ea4f800cda4e6839fb61c33955703dea2a8252d81d87178b3" -"checksum crossterm_cursor 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "e91c25e521708bd85fbdbdc34a854d1582793ab36e9aff2cee58fc79d7728e82" -"checksum crossterm_input 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "937c314942c75a7893303e3fa1857cfbafdd8a7d8ee369389c79b55cc268c7a7" -"checksum crossterm_screen 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "48eb1d3e7c5fea9b5a15c8667cb18b8c8fdfb28e38cd8faa048b9b7490cd9f69" -"checksum crossterm_style 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "a2e4b4a13093fd9c0c16167b14a69ceb8166e079ccda904d41bbfc8ba2714b1b" -"checksum crossterm_terminal 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "f1b61af4ef3ed3624994e8af7ac87b6a483c2936e63eebe38d9a2810cd4a6d44" -"checksum crossterm_utils 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "d26f24386ea91f9c55a85531dd3ee3673e4c82729e64567928665aca3a47c741" -"checksum crossterm_winapi 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "f63b02344710452064687251b49cb0c275df10ea70dcd6038b1eec11665efc0a" "checksum libc 0.2.44 (registry+https://github.com/rust-lang/crates.io-index)" = "10923947f84a519a45c8fefb7dd1b3e8c08747993381adee176d7a82b4195311" "checksum num_cpus 1.8.0 (registry+https://github.com/rust-lang/crates.io-index)" = "c51a3322e4bca9d212ad9a158a02abc6934d005490c054a2778df73a70aa0a30" -"checksum termios 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)" = "72b620c5ea021d75a735c943269bb07d30c9b77d6ac6b236bc8b5c496ef05625" -"checksum winapi 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)" = "92c1eb33641e276cfa214a0522acad57be5c56b10cb348b3c5117db75f3ac4b0" -"checksum winapi-i686-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ac3b87c63620426dd9b991e5ce0329eff545bccbbb34f3be09ff6fb6ab51b7b6" -"checksum winapi-x86_64-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "712e227841d057c1ee1cd2fb22fa7e5a5461ae8e48fa2ca79ec42cfc1931183f"
diff --git a/Rust/Cargo.toml b/Rust/Cargo.toml @@ -4,5 +4,4 @@ version = "0.1.0" authors = ["Gark Garcia <37553739+GarkGarcia@users.noreply.github.com>"] [dependencies] -crossterm = "0.6" num_cpus = "1.0" \ No newline at end of file
diff --git a/Rust/src/main.rs b/Rust/src/main.rs @@ -3,59 +3,49 @@ // 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 integer. -extern crate crossterm; extern crate num_cpus; -use std::{env, thread, time::Instant, sync::{Arc, mpsc::{self, Sender, Receiver}}}; -use crossterm::{terminal, input}; +use std::{env, process, thread, sync::{Arc, mpsc::{self, Sender, Receiver}}}; + +const SUCCESS: i32 = 0; +const FAIL: i32 = 1; +const INVALID_INPUT: i32 = 2; fn main() { let args: Vec<String> = env::args().collect(); - let prompt = terminal(); - - // Assign the correct number of threads to run the application with - // The default is the number of cores in the machine - let n_cores = num_cpus::get_physical(); - let n_threads = if args.len() <= 1 { n_cores } else { - match args[1].trim().parse::<usize>() { - Ok(n_arg) => std::cmp::min(n_arg, n_cores), - Err(_) => n_cores - } - }; - - println!("\nThis program is a simple test for the following conjecture:\n"); - println!("Let S: N -> N be the sum of the digits of a positive integer."); - println!("For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an integer."); - - // Listen for user input - let _ = prompt.write("\nWhat value would you like to test the conjecture for? "); - let user_input = input().read_line().unwrap_or_default(); - - match user_input.trim().parse::<usize>() { - Ok(max) => { - println!("\nLOADING. . ."); - let start_time = Instant::now(); - let counterexpl = get_countrexpl(max, n_threads); - let duration = start_time.elapsed(); - - // Print the results - println!("LOADED. . . in {}ms [{} Threads]\n", duration.as_millis(), n_threads); - match counterexpl { - None => println!("The conjecture is proved for all natural numbers smaller or equals to {}!", max), - Some((a, b)) => println!("The conjecture is disproved! Here's a counterexample: ({}, {})", a, b) + + if args.len() > 1 { + let max_str = args[1].clone(); + + // Assign the correct number of threads to run the application with + // The default is the number of cores in the machine + let n_cores = num_cpus::get_physical(); + let n_threads = if args.len() <= 2 { n_cores } else { + match args[2].trim().parse::<usize>() { + Ok(n_arg) => std::cmp::min(n_arg, n_cores), + Err(_) => n_cores } - }, - Err(_) => println!("'{}' is not a natural number!", user_input.trim()) + }; + + match max_str.trim().parse::<usize>() { + Ok(max) => if get_countrexpl(max, n_threads) { + process::exit(FAIL); + } else { + process::exit(SUCCESS); + }, + Err(_) => process::exit(INVALID_INPUT) + } + } else { + process::exit(INVALID_INPUT); } } /// Distributes calculations across threads and collect the results -fn get_countrexpl(max: usize, n_threads: usize) -> Option<(usize, usize)> { +fn get_countrexpl(max: usize, n_threads: usize) -> bool { let sums_cache = Arc::new(get_sums(max)); - if max / n_threads > 0 && n_threads > 1 { - - let (coutexpl_sender, coutexpl_reciever): (Sender<Option<(usize, usize)>>, Receiver<Option<(usize, usize)>>) = mpsc::channel(); + if n_threads > 1 { + let (coutexpl_sender, coutexpl_reciever): (Sender<bool>, Receiver<bool>) = mpsc::channel(); let mut child_threads = Vec::with_capacity(n_threads); for i in 0..n_threads { @@ -70,8 +60,8 @@ fn get_countrexpl(max: usize, n_threads: usize) -> Option<(usize, usize)> { .expect(&format!("Thread n°{} was unable to sent a message trought the channel", i))); child_threads.push(child); - if let Ok(Some(c_expl)) = coutexpl_reciever.recv() { - return Some(c_expl); + if let Ok(true) = coutexpl_reciever.recv() { + return true; } } @@ -79,7 +69,7 @@ fn get_countrexpl(max: usize, n_threads: usize) -> Option<(usize, usize)> { child.join().expect("Child thread panicked"); } - None + false } else { get_iter_countrexpl(0..max, sums_cache, max) } @@ -90,18 +80,18 @@ fn get_iter_countrexpl<I: IntoIterator<Item = usize>>( iter: I, sums_cache: Arc<Vec<isize>>, max: usize -) -> Option<(usize, usize)> { +) -> bool { for a in iter { for b in a..max { let diff = sums_cache[a + b] - sums_cache[a] - sums_cache[b]; if diff % 9 != 0 { - return Some((a, b)); + return true; } } } - None + false } fn sum_digits(n: usize) -> isize {
diff --git a/script.js b/script.js @@ -3,9 +3,7 @@ // 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. -const readline = require("readline"); - -Number.prototype.sum = function() { +function sumDigits() { if (isNaN(this) || !isFinite(this) || !this) throw new TypeError @@ -19,56 +17,23 @@ Number.prototype.sum = function() { return sum; } -Number.sums = function getSums(max) { +function getSums(max) { const output = [], maxRange = 2 * (max + 1); for (let i = 0; i <= maxRange; i++) - output.push(i.sum()); + output.push(sumDigits(i)); return output; } -function ask(question) { - const rl = readline.createInterface({ - input: process.stdin, - output: process.stdout, - }); - - return new Promise(resolve => rl.question(question, ans => { - rl.close(); - resolve(ans); - })) -} - -function getCounterExp(max) { - const sums = Number.sums(max); +export function getCounterExp(max) { + const sums = getSums(max); for (let a = 1; a <= max; a++) for (let b = a; b <= max; b++) { - const diff = sums[a + b] - sums[a] - sums[b]; - if (diff % 9 !== 0) return [a, b]; + const diff = sums[a + b] - (sums[a] + sums[b]); + if (diff % 9 !== 0) return true; } - return null; -} - -console.log("\nThis script is a simple test for the following conjecture:\n"); -console.log("Let S: N -> N be the sum of the digits of a positive integer."); -console.log("For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an interger.\n"); - -ask("What value would you like to test the conjecture for? ").then(ans => { - if (!isNaN(Number(ans))) { - console.log("\nLOADING. . ."); - - const max = Math.round(Number(ans)) - , starTime = new Date - , counterexmpl = getCounterExp(max) - , elepsed = new Date().getTime() - starTime.getTime(); - - console.log(`LOADED. . . in ${elepsed}ms\n`); - - if (counterexmpl === null) console.log(`The conjecture is proved for all natural numbers smaller or equals to ${max}!`); - else console.log(`The conjecture is disproved! Here's a counterexample: (${counterexmpl[0]}, ${counterexmpl[1]})`); - - } else console.log(`\n'${ans}' is not a natural number!`); -});- \ No newline at end of file + return false; +}+ \ No newline at end of file
diff --git a/script.pl b/script.pl @@ -0,0 +1,34 @@ +% The following script 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 integer. + +sum_digits(X, X) :- X < 10. +sum_digits(X, Y) :- + X >= 10, + X1 is div(X, 10), + X2 is mod(X, 10), + sum_digits(X1, Y1), + Y is Y1 + X2. + +test_pair(A, B) :- + R is 0, + AB is A + B, + sum_digits(A, SA), + sum_digits(B, SB), + sum_digits(AB, SC), + SAB is SA + SB, + D is SC - SAB, + R is mod(D, 9). + +iter(A, 0) :- test_pair(A, 0). +iter(A, B) :- + test_pair(A, B), + C is B - 1, + iter(A, C). + +conjecture(0) :- test_pair(0, 0). +conjecture(M) :- + iter(M, M), + N is M - 1, + conjecture(N).+ \ No newline at end of file
diff --git a/script.py b/script.py @@ -3,8 +3,6 @@ # 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. -from time import time - def sum_digits(n: int) -> int: parc = abs(n) sum_d = 0 @@ -15,48 +13,22 @@ def sum_digits(n: int) -> int: return sum_d -def get_counterexmpl(max: int) -> (int, int): - sums = get_sums(max) - - for a in range(max + 1): - for b in range(a, max + 1): - diff = sums[a + b] - sums[a] - sums[b] - - if not diff % 9 == 0: - return (a, b) - - return None - def get_sums(max: int) -> list: output = [] - for i in range(2 * (max + 1) + 1): + for i in range(2 * max): output.append(sum_digits(i)) return output +def get_counterexmpl(max: int) -> bool: + sums = get_sums(max) -print("\nThis script is a simple test for the following conjecture:\n") -print("Let S: N -> N be the sum of the digits of a positive integer.") -print("For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an interger.\n") -max_str = input("What value would you like to test the conjecture for? ") -print("\nLOADING. . .") - -try: - max = int(max_str) - if max < 0: - raise ValueError - - start = time() - counterexmpl = get_counterexmpl(max) - elepsed = time() - start - - print("LOADED. . . in {:.0f}ms\n".format(elepsed * 10**3)) + for a in range(max + 1): + for b in range(a, max + 1): + diff = sums[a + b] - sums[a] - sums[b] - if counterexmpl == None: - print("The conjecture is proved for all natural numbers smaller or equals to {}!".format(max)) - else: - (a, b) = counterexmpl - print("The conjecture is disproved! Here's a counterexample: ({}, {})".format(a, b)) -except: - print("'{}' isn't a natural number!".format(max_str)) + if not diff % 9 == 0: + return True + + return False
diff --git a/script.rb b/script.rb @@ -3,68 +3,41 @@ # 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. -class Integer - def sum - part = self.abs() - sum = 0 - - while part > 0 - d, r = part.divmod(10) - sum += r - part = d - end - - return sum +def sumDigits(i) + part = i.abs() + sum = 0 + + while part > 0 + d, r = part.divmod(10) + sum += r + part = d end - def self.sums(max) - output = [] - - for i in 0..((max + 1) * 2) - output << i.sum() - end + return sum +end - return output +def getSums(max) + output = [] + + for i in 0..((max + 1) * 2) + output << sumDigits(i) end + + return output end def get_counterexpl(max) - sums = Integer.sums(max) + sums = getSums(max) for a in (0..max) for b in (a..max) diff = sums[a + b] - sums[a] - sums[b] if diff % 9 != 0 - return [a, b] + return true end end end - return nil -end - -puts "\nThis script is a simple test for the following conjecture:\n\n" -puts "Let S: N -> N be the sum of the digits of a positive integer." -puts "For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an integer.\n\n" -puts "What value would you like to test the conjecture for?" - -max_str = gets.chomp -puts "\nLOADING. . ." - -if /^\d+$/.match(max_str) - max = max_str.chomp.to_i - start = Time.now() - counterexpl = get_counterexpl(max) - - elepsed = Time.now() - start - puts "LOADED. . . in #{(elepsed * 1000).round()}ms\n\n" - - if counterexpl == nil - puts "The conjecture is proved for all natural numbers smaller or equals to #{max}!" - else - puts "The conjecture is disproved! Here's a counterexample: (#{counterexpl[0]}, #{counterexpl[1]})" - end -else - puts "'#{max_str}' isn't a natural number!" + return false end \ No newline at end of file