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 ulong rad = 0;

			public N (ulong num)
			{
				this.n = num;
				this.rad = rad(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++)
			{
				NCases.Add(new N(n));
			}
			N answer = NCases.OrderBy(x => x.rad)
				.ThenBy(x => x.n).ToList()[10000-1];

			Console.WriteLine(answer.n);
		}
		public static ulong rad(ulong n)
		{
			List<ulong> factors = DistinctFactors(n);
			ulong rad = 1;
			foreach(ulong f in factors)
				rad *= f;
			return rad;
		}
		public static List<ulong> DistinctFactors (ulong n)
		{
			List<ulong> factors = new List<ulong>();

			if(primes.Contains(n))
			{
				factors.Add(n);
				return factors;
			}
			ulong sqrt = (ulong)Math.Sqrt((double)n);
			foreach (ulong p in primes)
			{
				if (p > sqrt)
					break;
				if (n%p == 0)
				{
					factors.Add(p);
					while (n%p == 0)
						n = n/p;
				}
			}
			if (n!= 1ul)
				factors.Add(n);
			return factors;
		}
		static List<ulong> GeneratePrimes(ulong num)
		{
			List<ulong> RetValue = new List<ulong>();
			RetValue.Add((ulong)2);
			RetValue.Add((ulong)3);
			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)
				{
					RetValue.Add(Stepper);
				}
				Check = 1;
				Stepper++;
				Stepper++;
			}
			return RetValue;
		}
	}
}

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.Add(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;
		}
	}
}

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

Addition Chains are paths or little sections of an Addition Tree. To build the tree start with the number 1. To this root add a new node for each ancestor + itself such that the value of the new node is the parent node + ancestor. Thus for the node 1 the new children nodes would be a single node of value 2. The next level then becomes 3(2+1) and 4(2+2). If we then follow the node 3 down to the next level it’s children become 4 (3+1) 5(3+2) & 6(3+3) and we can construct the children of the node 4 with the same technique; we can follow this tree right into infinity if we so choose. To obtain an addition chain we choose a node and get all of its ancestors and that’s the chain. So for the node 6 in our example above we get 6(3+3),3(2+1),2(1+1),1 and this path makes the Addition chain. This algorithm creates duplicate nodes some with longer chains that previously occurring nodes with a give value and the problem of creating optimal addition chains is NP-complete. The below implementation uses this naïve algorithm rather than try and create a single optimal path.

It can be shown that creating a tree containing only optimal paths is impossible with the example triplet 43, 77 and 149; having the first two of these numbers with an optimal path makes it impossible to have an optimal path for the third. Thus a tree can contain many paths and duplicates or not contain optimal paths. In the code below if AllowDuplicates is defined the tree is much smaller but there is no longer a guarantee of an optimal path being found. The library below allows duplicates and when you ask for a node of a given value it gets all nodes of that value and looks for the node with the fewest ancestors which would make that node the optimal path; if there is multiple nodes with the same number of ancestors it defaults to the first path it found.

Now, what good are these things you ask? Well we can use them for Addition Chain exponentiation. Say we wish to calculate \(n^{8}\). Well, we could multiply \(n * n * n * n * n * n * n * n\) and get our answer; this requires 7 multiplications. However, we can create an addition chain for 8 which would look like \(n^{1}, n^{2} (1*1), n^{4} (2*2), n^{8} (4*4)\). This can be used for exponentiation because of the rules for exponents where if we multiply two exponents with a common base we just add the exponent values. This chain method allows us to calculate \(n^{8}\) with only 3 multiplications; which for a small value n isn’t that impressive. But for a larger value this can make quite a difference. However, there is a trade off with the Addition Chain method using more memory and being more complicated to write.

So where is this all going? Well I found them interesting and wanted to share some code to build them. But more practically there is a Project Euler problem (Problem #122) that asks us to find a group of optimal chains.

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

namespace AdditionChain
{
    class AdditionChain
    {
        public AdditionChainNode Root
        {
            get;
            set;
        }
        private List<int> _knownValues = new List<int>();
        private List<AdditionChainNode> _nodeListing = new List<AdditionChainNode>();
        public AdditionChain(int rootVal)
        {
            this.Root = new AdditionChainNode(rootVal);
            _nodeListing.Add(this.Root);
            _knownValues.Add(this.Root.Value);
        }
        public void AddChild(AdditionChainNode parent, int value)
        {
			#if AllowDuplicates
            if (_knownValues.Contains(value))
                return;
            else
            {
			#endif
                AdditionChainNode n = new AdditionChainNode(value);
                n.Parent = parent;
                _knownValues.Add(value);
                _nodeListing.Add(n);
                parent.Children.Add(n);
			#if AllowDuplicates
            //}
			#endif
        }
        public int NodeLevel(AdditionChainNode start)
        {
            if (start == null)
                return int.MaxValue;
            int Val = 0;
            while (start.Parent != null)
            {
                start = start.Parent;
                Val++;
            }
            return Val;
        }
        public AdditionChainNode GetNodeByValue(int val)
        {
            while (!_knownValues.Contains(val))
                CreateNextLevel();
            AdditionChainNode m = null;
            foreach(AdditionChainNode n in _nodeListing)
            {
                //do the cheap check first
                if (n.Value == val)
                {
                    if (NodeLevel(n) < NodeLevel(m))
                        m = n;
                }
            }

            return m;
        }
        public void CreateNextLevel()
        {
            List<AdditionChainNode> lowest = GetLowestLevelNodes();
            foreach (AdditionChainNode n in lowest)
            {
                List<int> ancestors = GetAncestorValues(n);
                foreach (int i in ancestors)
                {
					#if AllowDuplicates
                    //if (!_knownValues.Contains(n.Value + i))
                    //{
					#endif
                        AddChild(n, n.Value + i);
					#if AllowDuplicates
                    //}
					#endif
                }
            }
        }

        private List<AdditionChainNode> GetLowestLevelNodes()
        {
            if (Root.Children.Count == 0)
                return new List<AdditionChainNode>() { Root };
            else
            {
                List<AdditionChainNode> Vals = new List<AdditionChainNode>();

                foreach (AdditionChainNode n in _nodeListing)
                {
                    if (n.Children.Count == 0)
                        Vals.Add(n);
                }

                return Vals.OrderBy(i=> i.Parent.Value).ToList();
            }
        }
        public List<int> GetAncestorValues(AdditionChainNode start)
        {
            if (start.Parent == null)
                return new List<int>(){start.Value};
            List<int> Vals = new List<int>();

            AdditionChainNode p = start;
            Vals.Insert(0, p.Value);

            while (p.Parent != null)
            {
                p = p.Parent;
                Vals.Insert(0, p.Value);
            }

            return Vals;
        }
    }
    class AdditionChainNode
    {

        public List<AdditionChainNode> Children
        {
            get;
            set;
        }
        public AdditionChainNode Parent
        {
            get;
            set;
        }
        public int Value
        {
            get;
            set;
        }
        public override string ToString()
        {
            return this.Value.ToString();
        }
        public AdditionChainNode(int v)
        {
            this.Value = v;
            this.Children = new List<AdditionChainNode>();
        }
    }
}

Problem #23 says:

Let p(n) be the nth prime: 2, 3, 5, 7, 11, …, and let r be the remainder when \((p(n)-1)^{n}+(p(n)+1)^{n}\) is divided by p(n)2.

For example, when n = 3, p(3) = 5, and 43 + 63 = 280 ≡ 5 mod 25.

The least value of n for which the remainder first exceeds \(10^{9}\) is 7037.

Find the least value of n for which the remainder first exceeds \(10^{10}\).

This can be solved using a modified version of the solution for Problem #120. We don’t even need to keep track of all of the remainders because the problem only concerns itself with the first remainder to exceed \(10^{10}\). So using our maximum remainder from the previous Problem #120 which was \(2*n*a\) we can modify it to be \(2*p_{n}*n\). From this point we just need a collection of prime numbers large enough to get the Job done; I chose to use a list of primes going up to 300000 because this creates a list of 25998 prime numbers and \(25998 * 2 * p[25998] > 1.5 x 10^{10}\) which gives me all of the data I needed to find a solution exceeding \(10^{10}\).

Solution below in c#/mono. runs in about .113 seconds.

using System;
using System.Collections.Generic;

namespace Problem123
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			ulong upperbound = 10000000000ul;
			List<ulong> p = GeneratePrimes(300000);
			p.Insert(0,0UL);
			Console.WriteLine("primes done");
			for (uint n = 1; n < 300000ul; n++)
			{
				if (n%2 ==0ul)
					continue;
				ulong r = 2 * p[(int)n] * n;
				if (r > upperbound)
				{
					Console.WriteLine(n);
					Console.WriteLine(p[(int)n]);
					Console.WriteLine(r);
					break;
				}
			}

		}
		static List<ulong> GeneratePrimes(ulong num)
		{
			List<ulong> RetValue = new List<ulong>();
			RetValue.Add((ulong)2);
			RetValue.Add((ulong)3);
			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)
				{
					//Console.WriteLine(((float)Stepper / (float)num) * 100);
					RetValue.Add(Stepper);
				}
				Check = 1;
				Stepper++;
				Stepper++;
			}
			return RetValue;
		}
	}
}

Also just as a note I’ve moved from jsMath to MathJax to see if it solves any of the issues I’ve been having. If you see something that might be an equation but it’s all screwy please point it out in the comments.