The following code takes a number k and its distinct factors f and creates a SortedSet containing all of the divisors of that number. It does this by expanding the set of divisors but multiplying each member of the already known divisors by each prime factor and checking to make sure that the input number k mod the resulting number is 0. Doing this a few times gives a complete list of all of the divisors. There are other methods including recursion that could be used but for what I wrote this to do it should be efficient enough. This program was written to handle numbers of the form \( 10^{n} \) which have only two distinct factors (2,5). While it might be able to handle other numbers with a small set of distinct factors I believe that it would quickly become unwieldy when given a large number with a large prime factor list.

Also updates will be sporadic for a while because it’s my first semester at my new university and I’ve got a heavy course load.

#light

open System
open System.Collections
open System.Collections.Generic

let ExpandSet s f max=
    let s2 = new SortedSet<int64>()
    for i in s do
        for j in f do
            let n = i*j
            if (n <= max && max % n = 0L) then
                s2.Add(n) |> ignore
    s2.UnionWith(s)
    s2.UnionWith(f)
    s2

let fac =
    let t = new SortedSet<int64>()
    t.Add(2L)
    t.Add(5L)
    t

let DivisorsOf k f =
    let mutable divs = new SortedSet<int64>()
    divs.Add(1L) |> ignore
    let tries = int64(Math.Ceiling(Math.Log(float k)/Math.Log(2.)))
    for i in [1L .. tries] do
        Console.WriteLine(i) |> ignore
        divs <- ExpandSet divs f k
    divs

let PrintSet (s:SortedSet<int64>) =
    for i in s do
        Console.WriteLine(i)

let t = DivisorsOf 1000000000L fac

PrintSet t

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 #80 is stated as:

It is well known that if the square root of a natural number is not an integer, then it is irrational. The decimal expansion of such square roots is infinite without any repeating pattern at all.

The square root of two is 1.41421356237309504880…, and the digital sum of the first one hundred decimal digits is 475.

For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots.

This problem actually lead me to a new and interesting way of finding square roots described in a paper titled “Square roots by subtraction” by Frazer Jarvis. Frazer claims that it is an old math algorithm from Japan but it’s not the algorithms history that makes it useful. Instead it’s the fact that the algorithm allows us to get arbitrarily precise square roots using basic subtraction and multiplication (I felt the title was a little odd but oh well).

The algorithm works like this take your number \(n\) and make a new number \(a=5n\) and let \(b=5\). The you apply one of two rules depending on whether \(a\) is larger than \(b\). If \(a\) is larger then you apply Rule 1: which is to set \(a=a-b\) and set \(b=b+10\). If \(b\) is larger you apply Rule 2: set \(a= a*100\) and set \(b=((b-5)*10)+5)\). Just repeat those rules using the \((a,b)\) from the previous round until your answer (which is \(b\)) has the desired precision.

So for the square root of 2 we get (10,5) \(Rule 1\atop \longrightarrow\) (5,15) \(Rule 2\atop \longrightarrow\) (500,105)\(Rule 1\atop \longrightarrow\) (395,115) \(Rule 1\atop \longrightarrow\) (280,125) \(Rule 1\atop \longrightarrow\) (155,135) \(Rule 1\atop \longrightarrow\) (20,145) \(Rule 2\atop \longrightarrow\) (2000,1405) \(Rule 1\atop \longrightarrow\) (595,1415) and as we continue b gets closer and closer to the square root of 2. With this algorithm we are only limited by the size of the integer class we are using. As an added bonus this algorithm uses an integer class so we don’t have to worry about rounding errors. This means that with c# and .Net 4 we can using the BigInteger class from System.Numerics and generate the digits of the square root of 2 forever*.

So once we have this method all figured out what’s left to do? Well as it turns out not a whole lot; we just need a digital sum and a list of perfect squares to exclude and we’re golden. Solution provided in c#/mono and runs in 1 second or so. Could easily be made faster (at the very least one could add some parallelism).

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

namespace Problem80
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			List<int> squares = new List<int>();
			for (int i = 1; i <= 10; i++)
			{
				squares.Add(i*i);
			}
			uint sum = 0;
			for (int i = 1; i <=100; i++)
			{
				if (!squares.Contains(i))
					sum += DigitalSum(i);
			}
			Console.WriteLine(sum);

		}
		public static uint DigitalSum (int i)
		{
			BigInteger digits = BigInteger.Parse(SquareRoot(i).ToString().Substring(0,100));
			uint digitsum = 0;
			while (digits != BigInteger.Zero)
			{
				uint temp = (uint)(digits%10);
				digitsum += temp;
				digits = (digits -temp) / 10;
			}

			return digitsum;
		}
		public static BigInteger SquareRoot (int i)
		{
			BigInteger a = 5 * i;
			BigInteger b = 5;
			while (b.ToString().Length < 102)
			{
				if (a >= b)
				{
					a = a-b;
					b += 10;
				}
				else
				{
					a *= 100;
					b = ((b-5)*10)+5;
				}
			}
			return b;
		}
	}
}

* Memory limits and the physics of our universe prevent a person or computer from actually doing this.

Problem #68 boils down to:

… By concatenating each group it is possible to form 9-digit strings; the maximum string for a 3-gon ring is 432621513.

Using the numbers 1 to 10, and depending on arrangements, it is possible to form 16- and 17-digit strings. What is the maximum 16-digit string for a “magic” 5-gon ring?

Some rules apply. First all of the spars must add up to the same number and you need to pay close attention to how you build the final answer to put into the answer box or you’ll get told your correct polygon is wrong. (See the Project Euler page for details and an example)

This is a question that is easier solved on paper with a pencil than any program. Just a few simple assumptions will make solving this problem easier: 1) The outer ring has a higher place value compared to it’s inner ring counterparts. 2) You want a large number so it’s easy see you want the numbers 6-10 on the outer rings. 3) We want a 16 digit number which means that the 10 must be on the outer ring else it gets counted twice and you’ll end up with a 17 digit polygon.

There is no solution presented for this problem; however with the above hints it’s very easy to build the answer.