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

Problem #122 says:

We shall define m(k) to be the minimum number of multiplications to compute \(n^{k}\); for example m(15) = 5.

For 1 ≤ k ≤ 200, find ∑ m(k).

This is a problem about finding Addition Chains that lead to the desired number in the fewest steps. Using the library code I posted yesterday the solution can be written as 5 lines of code (not counting main() and other fluff). If you compile the Addition Chain library so that it doesn’t allow duplicates then the program will give the wrong answer; This is because duplicate paths are needed to ensure that an optimal chain can be found.

Other than that the solution runs in about 45 seconds an decent computer. Solution provided in c#/mono.

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

namespace Problem122
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			AdditionChain ac = new AdditionChain(1);
			int answer = 0;
			for (int i = 1; i<= 200; i++)
				answer += ac.NodeLevel(ac.GetNodeByValue(i));
			Console.WriteLine(answer);
		}
	}
}

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.

Problem #98 asks us:

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++)
			{
				squares.Add(i*i);
			}
			Max("rat","tar");
			while (words.Count > 0)
			{
				string primary = words[0];
				List<string> anagramset = new List<string>();
				anagramset.Add(primary);

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

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

			}
			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())]))
							map.Add(c,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);
		}
	}
}