Problem #206 says:
Find the unique positive integer whose square has the form 1_2_3_4_5_6_7_8_9_0,
where each “_” is a single digit.
The range of number to check can be narrowed down with a calculator and some common sense. Then its just a square and check procedure. Solution is in c# and requires the .Net 4.0 framework for its parallel extensions.
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Linq.Parallel;
using System.Threading;
using System.Threading.Tasks;
using System.Diagnostics;
using System.Numerics;
using System.Text.RegularExpressions;
namespace Net4Test
{
class Program
{
static object LockHandle = new object();
static long Answer = 0;
static void Main(string[] args)
{
Stopwatch sw = new Stopwatch();
sw.Start();
Regex Test = new Regex(
"[1][0-9][2][0-9][3][0-9][4][0-9]" +
"[5][0-9][6][0-9][7][0-9][8][0-9][9][0-9][0]");
Parallel.For(1360000000, 1390000000, i =>
{
BigInteger biI = i;
if (Test.IsMatch((biI * biI).ToString()))
{
Answer = i;
}
});
Console.WriteLine(Answer);
sw.Stop();
Console.WriteLine(sw.Elapsed);
Console.ReadLine();
}
}
}
Tags: c#, csharp, project euler
Posted in Project Euler | Comments (0)
Problem #92 says:
A number chain is created by continuously adding
the square of the digits in a number to form a new
number until it has been seen before.
For example,
44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89
Therefore any chain that arrives at 1 or 89 will become
stuck in an endless loop. What is most amazing is that
EVERY starting number will eventually arrive at 1 or 89.
How many starting numbers below ten million will arrive at 89?
This is pretty simple. Start a chain and see if it hits one of the two terminating conditions given. So a little recursive function, and maybe some .net 4.0 goodness to go though the ten million numbers efficiently. The below solution runs in less than a minute. It could be made more efficient by creating a list of numbers that we know terminate in 89 so when we run the function we can see if we’ve already checked that part of the chain. but its fast enough. Solution provided below REQUIRES the .Net 4.0 frame work!
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Linq.Parallel;
using System.Threading;
using System.Threading.Tasks;
using System.Diagnostics;
namespace Net4Test
{
class Program
{
static object LockHandle = new object();
static long Count = 0;
static void Main(string[] args)
{
Stopwatch sw = new Stopwatch();
sw.Start();
Parallel.For(1, 10000000, i =>
{
CheckNumber(i);
});
Console.WriteLine(Count);
sw.Stop();
Console.WriteLine(sw.Elapsed);
Console.ReadLine();
}
static void CheckNumber(int i)
{
if (i == 1)
return;
if (i == 89)
{
Increment();
return;
}
int c = 0;
char[] nums = i.ToString().ToCharArray();
foreach (char s in nums)
{
c += Convert.ToInt32(s.ToString()) * Convert.ToInt32(s.ToString());
}
CheckNumber(c);
}
static void Increment()
{
lock (LockHandle)
{
Count++;
}
}
}
}
Posted in Project Euler | Comments (0)
Problem #188 says:
The hyperexponentiation or tetration of a number
a by a positive integer b, denoted by a↑↑b or ^(b)a,
is recursively defined by:
a↑↑1 = a,
a↑↑(k+1) = a^((a↑↑k)).
Thus we have e.g. 3↑↑2 = 3^(3) = 27,
hence 3↑↑3 = 3^(27) = 7625597484987
and 3↑↑4 is roughly 10^(3.6383346400240996*10^12).
Find the last 8 digits of 1777↑↑1855.
This problem rather basic when you think about it mathematically. And even simpler once you realize that python has a built in modulo parameter to its pow() function. Making this whole problem rather simple. And with a bit of poking around one realizes that you don’t have to go through the whole loop as the value we’re looking for appears in the first 20 loops through the program.
Anyway, Solution is in python (2.6).
def Tetrate(Base,Tetrate,Modulo):
Value = 1
while Tetrate:
Value = pow(Base,Value,10**Modulo)
Tetrate = Tetrate - 1
return Value
print "Answer : ", Tetrate(1777,1855,8)
Tags: Math, project euler, python
Posted in Project Euler | Comments (0)
(updates on the site. pagerank just hit 3 on google. hopefully this will increase traffic a bit. and this post is the first post on the site done in windows 7 (took 6 hours for my pc to update
)
Problem #50 says:
The prime 41, can be written as the sum of six consecutive primes:
41 = 2 + 3 + 5 + 7 + 11 + 13
This is the longest sum of consecutive primes that adds to a prime below one-hundred.
The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.
Which prime, below one-million, can be written as the sum of the most consecutive primes?
The solution below is pretty much brute force. We generate the primes and then add them together and subtract from the total items in the list of primes. then we get the total of all of the primes minus the first item in the primes list and do it over again. there’s lots of room for improvements and when I get the time I’ll post them. but for now this is what I used to get the solution. Solution provided in c#/mono.
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
namespace ProjectEuler
{
class Program
{
static void Main(string[] args)
{
Stopwatch sw = new Stopwatch();
sw.Start();
ArrayList primes = GeneratePrimes(1000000);
primes.Remove(1);
long result = 0;
long maxlength = 0;
Console.WriteLine("starting check");
for (int start = 0;start<primes.Count;start++)
{
long temp = 0;
for (int i = start; i < primes.Count; i++)
{
temp = temp + (long)primes[i];
}
for (int k = primes.Count - 1; k > start; k--)
{
if (temp < 1000000 && primes.Contains(temp) && k - start >= maxlength)
{
maxlength = k -start;
result = temp;
Console.WriteLine(result);
break;
}
temp = temp - (long)primes[k];
if (temp <= start)
break;
}
}
Console.WriteLine(result);
Console.WriteLine(maxlength);
Console.WriteLine(sw.Elapsed);
Console.ReadLine();
}
static ArrayList GeneratePrimes(long num)
{
ArrayList RetValue = new ArrayList();
RetValue.Add((long)2);
RetValue.Add((long)3);
long Stepper = 5;
long Check = 1;
while (Stepper <= num)
{
foreach (long i in RetValue)
{
if (Stepper % i == 0)
{
Check = 0;
break;
}
if (Math.Sqrt(Stepper) < i)
{
break;
}
}
if (Check == 1)
{
//Console.WriteLine(((float)Stepper / (float)num) * 100);
RetValue.Add(Stepper);
}
Check = 1;
Stepper++;
Stepper++;
}
return RetValue;
}
}
}
Tags: c#, csharp, mono, programming, project euler
Posted in Project Euler | Comments (0)