How to resolve the algorithm Euler's sum of powers conjecture step by step in the C# programming language
How to resolve the algorithm Euler's sum of powers conjecture step by step in the C# programming language
Table of Contents
Problem Statement
There is a conjecture in mathematics that held for over two hundred years before it was disproved by the finding of a counterexample in 1966 by Lander and Parkin. This conjecture is called Euler's sum of powers conjecture and can be stated as such: In 1966, Leon J. Lander and Thomas R. Parkin used a brute-force search on a CDC 6600 computer restricting numbers to those less than 250. The task consists in writing a program to search for an integer solution of
x
0
5
x
1
5
x
2
5
x
3
5
=
y
5
{\displaystyle x_{0}^{5}+x_{1}^{5}+x_{2}^{5}+x_{3}^{5}=y^{5}}
where all
x
i
{\displaystyle x_{i}}
and
y
{\displaystyle y}
are distinct integers between 0 and 250 (exclusive). Show an answer here. Related tasks are:
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Euler's sum of powers conjecture step by step in the C# programming language
Source Code 1:
This code is written in C# and it solves a mathematical problem known as the "sum of powers problem." The problem is to find all sets of five positive integers (a, b, c, d, e) such that the sum of their fifth powers is equal to a fifth power of another positive integer.
The code uses a brute-force approach to solve the problem. It initializes an array called fifth
that contains the fifth powers of all numbers from 1 to 250. Then, it iterates over all possible combinations of five numbers from the array and checks if the sum of their fifth powers is equal to a fifth power. If it finds a solution, it prints it to the console.
Source Code 2:
This code is also written in C# and it solves the same problem as the first code. However, it uses a more efficient algorithm based on modular arithmetic.
The code initializes two arrays, p5
and sum2
, that contain the fifth powers of all numbers from 1 to 250 and a mapping from the sum of fifth powers modulo 30 to pairs of numbers that sum to that value.
The code then iterates over all possible combinations of four numbers from the p5
array and checks if the sum of their fifth powers modulo 30 is equal to the sum of the fifth powers of the remaining number and some other number in the p5
array. If it finds a solution, it prints it to the console.
The advantage of this algorithm is that it reduces the number of calculations that need to be performed by a factor of 30. This makes it much faster than the brute-force approach.
Source code in the csharp programming language
using System;
namespace EulerSumOfPowers {
class Program {
const int MAX_NUMBER = 250;
static void Main(string[] args) {
bool found = false;
long[] fifth = new long[MAX_NUMBER];
for (int i = 1; i <= MAX_NUMBER; i++) {
long i2 = i * i;
fifth[i - 1] = i2 * i2 * i;
}
for (int a = 0; a < MAX_NUMBER && !found; a++) {
for (int b = a; b < MAX_NUMBER && !found; b++) {
for (int c = b; c < MAX_NUMBER && !found; c++) {
for (int d = c; d < MAX_NUMBER && !found; d++) {
long sum = fifth[a] + fifth[b] + fifth[c] + fifth[d];
int e = Array.BinarySearch(fifth, sum);
found = e >= 0;
if (found) {
Console.WriteLine("{0}^5 + {1}^5 + {2}^5 + {3}^5 = {4}^5", a + 1, b + 1, c + 1, d + 1, e + 1);
}
}
}
}
}
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;
namespace Euler_cs
{
class Program
{
struct Pair
{
public int a, b;
public Pair(int x, int y)
{
a = x; b = y;
}
}
static int min = 1, max = 250;
static ulong[] p5;
static SortedDictionary<ulong, Pair>[] sum2 =
new SortedDictionary<ulong, Pair>[30];
static string Fmt(Pair p)
{
return string.Format("{0}^5 + {1}^5", p.a, p.b);
}
public static void InitM()
{
for (int i = 0; i <= 29; i++)
sum2[i] = new SortedDictionary<ulong, Pair>();
p5 = new ulong[max + 1];
p5[min] = Convert.ToUInt64(min) * Convert.ToUInt64(min);
p5[min] *= p5[min] * Convert.ToUInt64(min);
for (int i = min; i <= max - 1; i++)
{
for (int j = i + 1; j <= max; j++)
{
p5[j] = Convert.ToUInt64(j) * Convert.ToUInt64(j);
p5[j] *= p5[j] * Convert.ToUInt64(j);
if (j == max) continue;
ulong x = p5[i] + p5[j];
sum2[x % 30].Add(x, new Pair(i, j));
}
}
}
static List<string> CalcM(int m)
{
List<string> res = new List<string>();
for (int i = max; i >= min; i--)
{
ulong p = p5[i]; int pm = i % 30, mp = (pm - m + 30) % 30;
foreach (var s in sum2[m].Keys)
{
if (p <= s) break;
ulong t = p - s;
if (sum2[mp].Keys.Contains(t) && sum2[mp][t].a > sum2[m][s].b)
res.Add(string.Format(" {1} + {2} = {0}^5",
i, Fmt(sum2[m][s]), Fmt(sum2[mp][t])));
}
}
return res;
}
static int Snip(string s)
{
int p = s.IndexOf("=") + 1;
return Convert.ToInt32(s.Substring(p, s.IndexOf("^", p) - p));
}
static int CompareRes(string x, string y)
{
int res = Snip(x).CompareTo(Snip(y));
if (res == 0) res = x.CompareTo(y);
return res;
}
static int Validify(int def, string s)
{
int res = def, t = 0; int.TryParse(s, out t);
if (t >= 1 && t < Math.Pow((double)(ulong.MaxValue >> 1), 0.2))
res = t;
return res;
}
static void Switch(ref int a, ref int b)
{
int t = a; a = b; b = t;
}
static void Main(string[] args)
{
if (args.Count() > 1)
{
min = Validify(min, args[0]);
max = Validify(max, args[1]);
if (max < min) Switch(ref max, ref min);
}
else if (args.Count() == 1)
max = Validify(max, args[0]);
Console.WriteLine("Mod 30 shortcut with threading, checking from {0} to {1}...", min, max);
List<string> res = new List<string>();
DateTime st = DateTime.Now;
List<Task<List<string>>> taskList = new List<Task<List<string>>>();
InitM();
for (int j = 0; j <= 29; j++)
{
var jj = j;
taskList.Add(Task.Run(() => CalcM(jj)));
}
Task.WhenAll(taskList);
foreach (var item in taskList.Select(t => t.Result))
res.AddRange(item);
res.Sort(CompareRes);
foreach (var item in res)
Console.WriteLine(item);
Console.WriteLine(" Computation time to check entire space was {0} seconds",
(DateTime.Now - st).TotalSeconds);
if (System.Diagnostics.Debugger.IsAttached)
Console.ReadKey();
}
}
}
You may also check:How to resolve the algorithm Matrix transposition step by step in the Lua programming language
You may also check:How to resolve the algorithm Topswops step by step in the Eiffel programming language
You may also check:How to resolve the algorithm Semordnilap step by step in the REXX programming language
You may also check:How to resolve the algorithm Hello world/Text step by step in the PDP-1 Assembly programming language
You may also check:How to resolve the algorithm Active Directory/Search for a user step by step in the Eiffel programming language