Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal) numbers and are generated by the following formulae:
| Triangle | P 3,n=n(n+1)/2 | 1, 3, 6, 10, 15, ... | ||
| Square | P4,n=n2 | 1, 4, 9, 16, 25, ... | ||
| Pentagonal | P5,n=n(3n-1)/2 | 1, 5, 12, 22, 35, ... | ||
| Hexagonal | P6,n=n(2n-1) | 1, 6, 15, 28, 45, ... | ||
| Heptagonal | P7,n=n(5n-3)/2 | 1, 7, 18, 34, 55, ... | ||
| Octagonal | P8,n=n(3n-2) | 1, 8, 21, 40, 65, ... |
The ordered set of three 4-digit numbers: 8128, 2882, 8281, has three interesting properties.
- The set is cyclic, in that the last two digits of each number is the first two digits of the next number (including the last number with the first).
- Each polygonal type: triangle (P
- This is the only set of 4-digit numbers with this property.
Find the sum of the only ordered set of six cyclic 4-digit numbers for which each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.
using System;
using System.Collections.Generic;
namespace project_euler
{
class Program
{
static void Main()
{
//Problem 61
DateTime start = DateTime.Now;
bool finished = false;
var numbers = new Dictionary<string, string>();
for (int i = 45; i * (i + 1) / 2 < 10000; i++)
numbers.Add("tri" + i, (i * (i + 1) / 2).ToString());
for (int j = 32; j * j < 10000; j++)
numbers.Add("squ" + j, (j * j).ToString());
for (int k = 26; k * (3 * k - 1) < 10000; k++)
numbers.Add("pen" + k, (k * (3 * k - 1) / 2).ToString());
for (int l = 23; l * (2 * l - 1) < 10000; l++)
numbers.Add("hex" + l, (l * (2 * l - 1)).ToString());
for (int m = 21; m * (5 * m - 3) / 2 < 10000; m++)
numbers.Add("hep" + m, (m * (5 * m - 3) / 2).ToString());
for (int n = 19; n * (3 * n - 2) < 10000; n++)
numbers.Add("oct" + n, (n * (3 * n - 2)).ToString());
//pick a number, find its type and original int,
foreach (KeyValuePair<string, string> pair1 in numbers)
{
string s = pair1.Value;
string sk = pair1.Key;
string sn = sk.Substring(3, sk.Length - 3);
string sm = sk.Substring(0, 3);
foreach (KeyValuePair<string, string> pair2 in numbers)
if (!pair2.Key.StartsWith(sm) &&
pair2.Key.Substring(3, pair2.Key.Length - 3) != sn)
if (pair2.Value.StartsWith(s.Substring(2, 2)))
{
string t = pair2.Value;
string tk = pair2.Key;
string tn = tk.Substring(3, tk.Length - 3);
string tm = tk.Substring(0, 3);
foreach (KeyValuePair<string, string> pair3 in numbers)
if (!pair3.Key.StartsWith(sm) &&
!pair3.Key.StartsWith(tm) &&
pair3.Key.Substring(3, pair3.Key.Length - 3) != sn &&
pair3.Key.Substring(3, pair3.Key.Length - 3) != tn)
if (pair3.Value.StartsWith(t.Substring(2, 2)))
{
string u = pair3.Value;
string uk = pair3.Key;
string un = uk.Substring(3, uk.Length - 3);
string um = uk.Substring(0, 3);
foreach (KeyValuePair<string, string> pair4 in numbers)
if (!pair4.Key.StartsWith(sm) &&
!pair4.Key.StartsWith(tm) &&
!pair4.Key.StartsWith(um) &&
pair4.Key.Substring(3, pair4.Key.Length - 3) != sn &&
pair4.Key.Substring(3, pair4.Key.Length - 3) != tn &&
pair4.Key.Substring(3, pair4.Key.Length - 3) != un)
if (pair4.Value.StartsWith(u.Substring(2, 2)))
{
string v = pair4.Value;
string vk = pair4.Key;
string vn = vk.Substring(3, vk.Length - 3);
string vm = vk.Substring(0, 3);
foreach (KeyValuePair<string, string> pair5 in numbers)
if (!pair5.Key.StartsWith(sm) &&
!pair5.Key.StartsWith(tm) &&
!pair5.Key.StartsWith(um) &&
!pair5.Key.StartsWith(vm) &&
pair5.Key.Substring(3, pair5.Key.Length - 3) != sn &&
pair5.Key.Substring(3, pair5.Key.Length - 3) != tn &&
pair5.Key.Substring(3, pair5.Key.Length - 3) != un &&
pair5.Key.Substring(3, pair5.Key.Length - 3) != vn)
if (pair5.Value.StartsWith(v.Substring(2, 2)))
{
string w = pair5.Value;
string wk = pair5.Key;
string wn = wk.Substring(3, wk.Length - 3);
string wm = wk.Substring(0, 3);
foreach (KeyValuePair<string, string> pair6 in numbers)
if (!pair6.Key.StartsWith(sm) &&
!pair6.Key.StartsWith(tm) &&
!pair6.Key.StartsWith(um) &&
!pair6.Key.StartsWith(vm) &&
!pair6.Key.StartsWith(wm) &&
pair6.Key.Substring(3, pair6.Key.Length - 3) != sn &&
pair6.Key.Substring(3, pair6.Key.Length - 3) != tn &&
pair6.Key.Substring(3, pair6.Key.Length - 3) != un &&
pair6.Key.Substring(3, pair6.Key.Length - 3) != vn &&
pair6.Key.Substring(3, pair6.Key.Length - 3) != wn)
if (pair6.Value.StartsWith(w.Substring(2, 2)) &&
pair6.Value.Substring(2, 2) == s.Substring(0, 2))
{
string x = pair6.Value;
string xk = pair6.Key;
int sum = int.Parse(s) +
int.Parse(t) +
int.Parse(u) +
int.Parse(v) +
int.Parse(w) +
int.Parse(x);
Console.WriteLine(sum);
Console.WriteLine(sk + " " + tk + " " + uk + " " + vk + " " + wk + " " + xk);
Console.WriteLine(s + " " + t + " " + u + " " + v + " " + w + " " + x);
finished = true;
break;
}
if (finished) break;
}
if (finished) break;
}
if (finished) break;
}
if (finished) break;
}
if (finished) break;
}
TimeSpan time = DateTime.Now - start;
Console.WriteLine("This took {0}", time);
Console.ReadKey();
}
}
}
No comments:
Post a Comment