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

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>();
        }
    }
}

So I found myself working on a small personal project in F# to gain more familiarity in the language when I decided the best way to solve my data storage needs would be a small local database file. So I went looking for ways to get sqlite into F# projects and couldn’t find a decent example. So I’ve started going through an example project in c# and trying to make it work in F#. I’ve got database creation and item insertion working so I figured what the heck I’ll post it here to make up for all of the posts I haven’t been writing lately.

I’m using the sqlite-net class from here compiled as a dll in a c# project. I’m then using that dll in my F# project. So if you’re looking for a pure f# implementation you at the wrong place. However its all il code at that level anyway. So armed with this dll I then create a f# type that looks a little something like this:

type Site (url:string) =
    let mutable id = new int()
    let mutable BD = ""
    let mutable site = url
    let mutable shown = false
    let mutable exemplarcontributor = false
    [<PrimaryKey>] [<AutoIncrement>]
    member x.ID with get() = id
                and set v = id <- v
    member x.ExemplarContributor with get() = exemplarcontributor
                                    and set v = exemplarcontributor <- v
    member x.Shown with get() = shown
                        and set v = shown <- v
    member x.BreakDown with get() = BD
                        and set v = BD <- v
    [<Indexed>]
    member x.Site with get() = site
                   and set v = site <- v
    member x.Url = url
    new() = Site "www.google.com"

now I should mention that this is directly from the test applet I’ve been using to get sqlite to work. as such it can probably be cleaned up quite a bit. Basically we have a URL and a few other details of a site and a few attributes. The ID is a primary key and auto incremented as shown above, note that this NEEDS to be put on the member declaration not the actual id. Also note that we need getter and setters on anything that we want to show up in the database, as such we need to make everything mutable. I’m still looking to see if there is another way to do that but this works for now. Anyways, armed with this type we can go to the next section, creating a database type that we’ll be adding custom stuff to in addition to inheriting from SQLiteConnection. And that looks like:

type Database (path) =
    inherit SQLiteConnection(path)
    member this.Setup = base.CreateTable<Site>()

Pretty basic right? All we’ve done is give the Database type a setup method that can be used to add the Site table to the database. If the database already has a Site table it’s not replaced but a safety check could easily be added to this method to make sure we don’t overwrite anything; however this is a throw away app and I’m not going to add it. Next we start doing stuff with these types. In fact we do this:

let D = new Database("test.sqlitedb")
D.Setup |> ignore

let s = new Site "www.google.com"

D.Insert(s) |> ignore

D.Commit|>ignore

Here we create a Database that we call D, call its setup method and pipe that to ignore (it returns an int to indicate errors, but I don’t want to catch it). Then we create a new instance of the Site type, do an insert again piping it to ignore and finally we commit everything and pipe that to ignore. And that’s it. We have a simple program that builds a useless database and adds a single entry to it. If you run this program multiple times it’ll just keep adding instances of Site to the database because it doesn’t overwrite the file.

So I was wandering the internet when I found an article about steganography, which is the art of hiding something in plain sight. Such as hiding a message inside a picture. Specifically the least significant bit method where you take the RGB color values of the pixel and set them based off a message in binary your encoding. So I figured I’d work something up and see if I could do that. This is a first attempt and it only encodes the message, right now it’ll truncate it if it doesn’t have enough pixels to work with or if the message length in binary isn’t divisible by three. Obviously this is a first attempt and a very simple one at that.

So basically you give it a picture and a text file and it reads the text file as a single string, converts it to binary then for each pixel it sets each of the RGB values based off the binary message value for that position. In this example if the binary message is odd for this position we set the color to an odd number (in effect setting the least significant bit to 1) else we make sure its an even number.

I have a few plans for expanding this project. It would be nice to decode the messages first of all, it would also be nice to have some options for encoding such as skipping a certain number of pixels between parts of the message, Only using certain color channels etc. But for now this is what I have.

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.IO;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace Steganography
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void btnBrowse_Click(object sender, EventArgs e)
        {
            OpenFileDialog op = new OpenFileDialog();
            op.CheckPathExists = true;
            op.CheckFileExists = true;
            op.Filter = "JPG image |*.jpg";
            op.ShowDialog();
            textBox1.Text = op.FileName;
        }

        private void textBox1_TextChanged(object sender, EventArgs e)
        {
            try
            {
                Preview.ImageLocation = textBox1.Text ;
            }
            catch
            {

            }
        }

        private void BrowseMessage_Click(object sender, EventArgs e)
        {
            OpenFileDialog op = new OpenFileDialog();
            op.CheckPathExists = true;
            op.CheckFileExists = true;
            op.ShowDialog();
            textBox2.Text = op.FileName;
        }

        private void button1_Click(object sender, EventArgs e)
        {
            MessageBox.Show("Your image will be saved as " + textBox1.Text +".new");
            //Get message as a binary string;
            string message = LoadMessage(textBox2.Text);
            string binmessage = "";
            foreach (char letter in message.ToCharArray())
            {
                binmessage += Convert.ToString(letter, 2);
            }
            //get bitmap of image.
            Bitmap bitm = (Bitmap)Preview.Image.Clone();
            int mPosition = 0;
            //Embed message
            #region embed
            for (int height = 0; height < bitm.Height; height++)
            {
                for (int width = 0; width < bitm.Width; width++)
                {
                    if (mPosition + 3 <= binmessage.Length)
                    {
                        Color pixelColor = bitm.GetPixel(width, height);
                        int R = int.Parse(pixelColor.R.ToString());
                        int G = int.Parse(pixelColor.G.ToString());
                        int B = int.Parse(pixelColor.B.ToString());
                        int m1 = int.Parse(binmessage[mPosition].ToString());
                        mPosition++;
                        int m2 = int.Parse(binmessage[mPosition].ToString());
                        mPosition++;
                        int m3 = int.Parse(binmessage[mPosition].ToString());
                        mPosition++;

                        if (m1 % 2 == 0)
                        {
                            if (R % 2 != 0 && R > 0)
                            {
                                R -= 1;
                            }
                            else
                            {
                                R += 1;
                            }
                        }
                        else
                        {
                            if (R % 2 != 1 && R > 0)
                            {
                                R -= 1;
                            }
                            else
                            {
                                R += 1;
                            }
                        }
                        if (m2 % 2 == 0)
                        {
                            if (G % 2 != 0 && G > 0)
                            {
                                G -= 1;
                            }
                            else
                            {
                                G += 1;
                            }
                        }
                        else
                        {
                            if (G % 2 != 1 && G > 0)
                            {
                                G -= 1;
                            }
                            else
                            {
                                G += 1;
                            }
                        }
                        if (m3 % 2 == 0)
                        {
                            if (B % 2 != 0 && B > 0)
                            {
                                B -= 1;
                            }
                            else
                            {
                                B += 1;
                            }
                        }
                        else
                        {
                            if (B % 2 != 1 && B > 0)
                            {
                                B -= 1;
                            }
                            else
                            {
                                B += 1;
                            }
                        }
                        Color pc = Color.FromArgb(R, G, B);
                        bitm.SetPixel(width, height, pc);

                    }
                    else
                    {
                    }
                }
            }
            #endregion embed

            bitm.Save(textBox1.Text + ".new");

        }

        private string LoadMessage(string p)
        {
            string RetValue = "";
            StreamReader sr;
            sr = File.OpenText(p);
            RetValue = sr.ReadToEnd();
            sr.Close();
            return RetValue;
        }
    }
}