a-conjecture-of-mine

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

Diffstat

3 files changed, 334 insertions, 0 deletions

diff --git a/CPP/acom.vcxproj b/CPP/acom.vcxproj
@@ -0,0 +1,106 @@
+<?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
@@ -0,0 +1,70 @@
+#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
@@ -0,0 +1,155 @@
+#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