Project Euler Problem #159!

February 22nd, 2013

The function mdrs(n) gives the maximum Digital Root Sum of $n$. So $\text{mdrs}(24)=11$.
Find $\text{mdrs}(n)$ for $1\lt n\lt 1,000,000$.

First we need to know that the Digital root of a number is equal to

$$f(x) = \left\{ \begin{array}{lr} n \pmod{9} & : n \neq 0 \pmod{9}\\ 9 & : n = 0 \pmod{9} \end{array} \right.$$

We then need the simple relations that $\text{mdrs}(n) = n$ for prime $n$, otherwise we look at the list of divisors such that $a*b = n$ and apply $\text{mdrs}(n) = Max(\text{mdrs}(a) + \text{mdrs}(b), \text{drs}[n])$ for each pair a&b. setting this up can be done in two ways: 1) Factor the number and generate each MDRS individually which for the number range we’re looking at isn’t too bad or 2) a dynamic programming approach which avoids factoring and creates all the MDRS’s in one go so we just have to add them up. The solution below uses the second approach, runs in about 3 tenths of a second for the given Maximum.

using System;
using System.Diagnostics;
using System.Linq;

namespace Problem159
{
class Program
{
private const long Max = 1000000;

static void Main()
{
var drs = new long[Max];
var sw = new Stopwatch();
sw.Start();
for (long i = 2;i < Max; i++)
{
if (drs[i] == 0)
drs[i] = i%9 ==0? 9 : i%9;
else if (drs[i]<10)
{
long c = i % 9 == 0 ? 9 : i % 9;
drs[i] = Math.Max(c, drs[i]);
}
long cur = i;
for (long fac = 2; fac <=i; fac++)
{
cur += i;
if (cur >= Max)
break;
drs[cur] = Math.Max(drs[i] + drs[fac], drs[cur]);

}
}
sw.Stop();
var sum = drs.Sum();
Console.WriteLine(sum);
Console.WriteLine(sw.Elapsed);
}
}
}



Tags: , , ,
Posted in Project Euler | Comments (0)

Project Euler Problem #124!

August 12th, 2011

Problem #124 wants us to:

The radical of n, rad(n), is the product of distinct prime factors of n. For example, $504 = 2^3 × 3^2 × 7$, so rad(504) = 2 × 3 × 7 = 42.

Let E(k) be the kth element in the sorted n column; for example, E(4) = 8 and E(6) = 9.

If rad(n) is sorted for 1 ≤ n ≤ 100000, find E(10000).

This problem is exceedingly easy once we calculate the radicals for the numbers 1-100000. Just create a simple class to remember the n, and rad values and populate those fields and the problem is 9/10ths of the way solved. From here we can use the power of Linq, which I’m liking more and more as time goes on, and do an OrderBy on the rad values. Now this seems like it would be insufficient to solve the problem because if the radical values are the same we need to sort by the n value. Well Linq has us covered; simply add a ThenBy after the OrderBy and you can sort by a second value. This means that the overwhelming majority of the code in the solution is prime number generation, finding distinct factors, and calculation of the radicals.

A second solution without linq would be to sort by the radical value and get the radical value of the 10000th item. Then find the index of the first number with that radical and store it. Then get a list of only the numbers with that radical and sort this new list by the n value. Using the previously stored index you can then calculate what item in the new list should be the answer. But this is alot more complicated than a simple Linq expression.

A third method would be to write a custom IComparer for the class that holds the radical + n values. But this is a lot more work than is needed and would make the solution much less readable in my opinion. Besides an up to date .Net implementation (Microsoft.Net or Mono) should have Linq available.

Solution below written in c#/mono and requires Linq and .Net 4. Runs in ~5 seconds.

using System;
using System.Collections.Generic;
using System.Linq;

namespace Problem124
{
class MainClass
{
class N
{
public ulong n = 0;

public N (ulong num)
{
this.n = num;
}
}
public static ulong max = 100000;
public static List<ulong> primes = GeneratePrimes(max);

public static void Main (string[] args)
{
List<N> NCases = new List<N>();
for (ulong n = 1; n<=max;n++)
{
}
.ThenBy(x => x.n).ToList()[10000-1];

}
{
List<ulong> factors = DistinctFactors(n);
foreach(ulong f in factors)
}
public static List<ulong> DistinctFactors (ulong n)
{
List<ulong> factors = new List<ulong>();

if(primes.Contains(n))
{
return factors;
}
ulong sqrt = (ulong)Math.Sqrt((double)n);
foreach (ulong p in primes)
{
if (p > sqrt)
break;
if (n%p == 0)
{
while (n%p == 0)
n = n/p;
}
}
if (n!= 1ul)
return factors;
}
static List<ulong> GeneratePrimes(ulong num)
{
List<ulong> RetValue = new List<ulong>();
ulong Stepper = 5;
ulong Check = 1;
while (Stepper <= num)
{
foreach (ulong i in RetValue)
{
if (Stepper % i == 0)
{
Check = 0;
break;
}
if (Math.Sqrt(Stepper) <= i)
{
break;
}
}
if (Check == 1)
{
}
Check = 1;
Stepper++;
Stepper++;
}
return RetValue;
}
}
}



Tags: , , , ,
Posted in Project Euler | Comments (0)

Project Euler Problem #119!

August 9th, 2011

Problem #119 is looking for:

The number 512 is interesting because it is equal to the sum of its digits raised to some power: 5 + 1 + 2 = 8, and 83 = 512. Another example of a number with this property is 614656 = 284.

We shall define an to be the nth term of this sequence and insist that a number must contain at least two digits to have a sum.

You are given that a2 = 512 and a10 = 614656.

Find a30.

This is another problem on Project Euler that is much easier if you turn it inside out. The problem wants you to calculate the digit sum $dsum$ of a number $n$ and do something like $log_{dsum}(n) = exp$ then check to see that $dsum^{exp} == n$ which is doable but really slow. The faster method is to loop through two sets of numbers $dbase$ and $dexp$ a base and an exponent and find the digit sum of the resulting number and compare it to the base or something like $DigitSum(dbase^{dexp}) == dbase$. This second method is much faster.

Solution written in c#/mono and uses the big integer library System.Numerics so requires .Net 4 . Calculates a bunch of extra numbers because of the loose boundaries but still runs in less than 4 seconds.

using System;
using System.Numerics;
using System.Collections.Generic;

namespace Problem119
{
class MainClass
{
public static void Main (string[] args)
{

List<BigInteger> An = new List<BigInteger>();
int Max = 30;
for (BigInteger dbase = 2; dbase <= 500;dbase++)
{
for (int dexp = 2; dexp <= 50;dexp++)
{
BigInteger n = BigInteger.Pow(dbase,dexp);
if (n.ToString().Length == 1)
continue;
if (DigitalSum(n) == dbase)
{
if (!An.Contains(n))
{

}
}
}
}
An.Sort();
Console.WriteLine(An[Max-1]);
}

public static BigInteger DigitalSum (BigInteger i)
{
BigInteger digits = (BigInteger) i;
BigInteger digitsum = 0;
while (digits != BigInteger.Zero)
{
BigInteger temp = (BigInteger)(digits%10);
digitsum += temp;
digits = (digits -temp) / 10;
}

return digitsum;
}
}
}


Tags: , , ,
Posted in Project Euler | Comments (0)

Project Euler Problem #133!

August 4th, 2011

Problem #133 says:

A number consisting entirely of ones is called a repunit. We shall define R(k) to be a repunit of length k; for example, R(6) = 111111.

Let us consider repunits of the form $R(10^{n})$.

Although R(10), R(100), or R(1000) are not divisible by 17, R(10000) is divisible by 17. Yet there is no value of n for which $R(10^{n})$ will divide by 19. In fact, it is remarkable that 11, 17, 41, and 73 are the only four primes below one-hundred that can be a factor of R(10n).

Find the sum of all the primes below one-hundred thousand that will never be a factor of R(10n).

This solution works based on the Multiplicative Order of 10 mod p; where p is a prime number (for this problem a prime under 100,000). For the number to never be a divisor of a RepUnit in the form $R(10^{n})$ then the above multiplicative order has to be something that can not be written in the form $2^{i} * 5^{i}$. This method expands to any repunit no matter how big the value of n in $R(10^{n})$ is.

The other method is to calculate a sufficiently large power of 10 such as $10^{20}$ and use that in pythons pow(10,$10^{20}$,p) which is faster but if you don’t choose a large enough power of ten you’ll get bad results after a certain point.

The second method is faster but I use the first in the below solution.

#!/usr/bin/python
from math import sqrt
#prime generator code aquired from
#http://code.activestate.com/recipes/366178-a-fast-prime-number-list-generator/
def Primes(n):
if n==2: return [2]
elif n<2: return []
s=range(3,n+1,2)
mroot = n ** 0.5
half=(n+1)/2-1
i=0
m=3
while m <= mroot:
if s[i]:
j=(m*m-3)/2
s[j]=0
while j<half:
s[j]=0
j+=m
i=i+1
m=2*i+3
return [2]+[x for x in s if x]

primes = Primes(100000)

def Factor(n):
global primes
pmax = int(sqrt(n))+1
factors = []
for prime in primes:
if prime > pmax:
break
if (n % prime ==0):
while (n% prime ==0):
factors = factors + [prime]
n = n/prime
if (n != 1):
factors += [n]
return factors

#n is the number to check
#form is the list of factors
#only true if n contains only factors found in form
def OfForm(n,form):
factors = Factor(n)
if (factors == []):
return False
for factor in factors:
if (factor not in form):
return False
return True

#a^k = 1 (mod n).
def MultiplicativeOrder (a,n):
k = 1
if (a%n ==0):
return 0
r = pow(a,k,n)
while (r != 1):
k= k+1
r = pow(a,k,n)
return k

primelist = Primes(100000)
summation = 0

for p in primelist:
if not OfForm(MultiplicativeOrder (10,p),[2,5]):
print p
summation += p

print summation


Tags: , , ,
Posted in Project Euler | Comments (0)

Project Euler Problem #98!

July 21st, 2011

By replacing each of the letters in the word CARE with 1, 2, 9, and 6 respectively, we form a square number: 1296 = $36^{2}$. What is remarkable is that, by using the same digital substitutions, the anagram, RACE, also forms a square number: 9216 = $96^{2}$. We shall call CARE (and RACE) a square anagram word pair and specify further that leading zeroes are not permitted, neither may a different letter have the same digital value as another letter.

Using a 16K text file containing nearly two-thousand common English words, find all the square anagram word pairs (a palindromic word is NOT considered to be an anagram of itself).

What is the largest square number formed by any member of such a pair?

NOTE: All anagrams formed must be contained in the given text file.

So we break this down into several parts. 1) Anagrams have to be the same length. 2) Remove words we’ve already paired up or failed to find an anagram for. 3) Each letter must have 1 numerical value assigned to it and used consistently. 4) Likewise each number can only be assigned to one letter.

With those four tips we can structure our solution like this. Build all of the anagram pairs and remove the words we’ve paired up from the main word list. Build a list of all of the square numbers from 2 – 1000000000. For each pair take the first word and find a square that is the same length. Assign each letter to a number without repeats of either letters or numbers (each pairing must be unique in both directions). Map the letter->number combination onto the second word. Parse the mapped second word to a ulong and make sure that it matches the length of the square assigned to word one. If they are the same length check (this will mean that there is not leading zero’s etc) then check the list of square numbers to see if the number created by mapping the second number appears in the list. If the mapped second word is a square then all we have to check is which is higher either the square assigned to the first word or the square we generated with the second. Take the highest one and go to the next anagram word pair.

This approach makes it so we don’t have to check to see if the square number assigned to word one and the generated square are the same because the only way that could happen is if word one and word two are the same words. There are no duplicates in the word list so we can eliminate all checking for that condition. Also the way we move through the list makes it impossible to compare a word to itself meaning we don’t have to waste time checking that either.

Despite the code being a mess it runs far faster than it looks like it should. Solution provided in c#/mono and runs in ~1.5 seconds.

* It’s left as an exercise to the reader to figure out how to get the word list into the words variable. I don’t want to screw up search engines by posting 1786 random words.

using System;
using System.Collections.Generic;

namespace Problem98
{
class MainClass
{
public static List<string> words = new List<string>();
public static List<List<string>> AnagramWordPairings = new List<List<string>>();
public static List<ulong> squares = new List<ulong>();
public static void Main (string[] args)
{

for (ulong i = 2; i <= 31700; i++)
{
}
Max("rat","tar");
while (words.Count > 0)
{
string primary = words[0];
List<string> anagramset = new List<string>();

for (int i = 1; i < words.Count;i++)
{
if (Anagrams(primary,words[i]))
}

if (anagramset.Count ==1)
words.Remove(primary);
else
{
foreach (string s in anagramset)
words.Remove(s);
}

}
ulong max = 0;
foreach(List<string> s in AnagramWordPairings)
{
ulong tmax = Max(s[0],s[1]);
if (tmax > max)
max = tmax;
}
Console.WriteLine(max);
}
public static ulong Max (string s1,string s2)
{
ulong max = 0;
foreach(ulong sq in squares)
{
if (sq.ToString().Length == s1.Length)
{
char[] premap = s1.ToCharArray();
int digits = sq.ToString().Length;
Dictionary<char,char> map = new Dictionary<char, char>();
foreach (char c in premap)
{
if (!map.ContainsKey(c) &&
!map.ContainsValue(sq.ToString()[s1.IndexOf(c.ToString())]))
}
string ts2 = (string)s2.Clone();
foreach (char c in map.Keys)
{
ts2 = ts2.Replace(c,map[c]);
}
try
{
ulong tp = ulong.Parse(ts2);
if (tp.ToString().Length != sq.ToString().Length)
continue;
if (squares.Contains(tp))
max = Math.Max(sq,tp);
}
catch{}
}
}
return max;
}

public static bool IsSquare (ulong i)
{
double sqrt = Math.Sqrt((double)i);
return Math.Ceiling(sqrt) == Math.Floor(sqrt);
}
public static bool Anagrams (string s1, string s2)
{
if (s1.Length != s2.Length)
return false;
char[] c1 = s1.ToUpper().ToCharArray();
char[] c2 = s2.ToUpper().ToCharArray();

Array.Sort(c1);
Array.Sort(c2);
string ns1 = new string(c1);
string ns2 = new string(c2);
return (ns1==ns2);
}
}
}


Tags: ,
Posted in Project Euler | Comments (0)