Archive for September, 2010

And now for something a little different.

September 25th, 2010


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

Tags: , ,
Posted in General, Software | Comments (0)

Project Euler Problem #187!

September 8th, 2010

Problem #187 says:

A composite is a number containing at least two prime factors. For example, 15 = 3 × 5; 9 = 3 × 3; 12 = 2 × 2 × 3.

There are ten composites below thirty containing precisely two, not necessarily distinct, prime factors: 4, 6, 9, 10, 14, 15, 21, 22, 25, 26.

How many composite integers, n < 10^(8), have precisely two, not necessarily distinct, prime factors?


This is a simple brute force attempt. It generates all primes up to the square root of 10^8 and then just goes through each number from 3 to 10^8 and factors it using the generated primes. This approach takes about 10 minuets to provide the answer. There are several methods for solving this problem that can reduce it to under 10 seconds that I might try to code later. Alternatively using parts from previous problems this problem could be done in parallel with f# without too much work using PSeq.filter.

Solution provided in c++ written using openSuse 11.3, geany, and gcc. I’m pretty rusty on writing code in c++ so excuse any glaring inefficiencies.

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>

using namespace std;

unsigned int newt_sqrt(unsigned int input)
{
	int nv, v = input>>1, c = 0;
	if (!v)
	return input;
	do
	{
		nv = (v + input/v)>>1;
		if (abs(v - nv) <= 1)
			return nv;
		v = nv;
	}
	while (c++ < 25);
	return nv;
}

vector<int> Primes (int max)
{
	vector<int> primes;
	primes.push_back(2);
	bool div = false;
	for(int i = 3; i <= max;i++)
	{
		int sqrp = newt_sqrt(i) + 1;
		for(unsigned int p = 0; p < primes.size(); p++)
		{
			int d = primes[p];
			if (d > sqrp)
				break;
			if (i % d == 0)
				div = true;
		}
		if (!div)
			primes.push_back(i);
		div = false;
	}
	return primes;
}
int Factors(int num, vector<int>  const  &primes, int factors)
{
	if (factors > 2)
		return 6000;
	bool divided = false;
	for (unsigned int i = 0; i < primes.size(); i++)
	{
		if (num % primes[i] == 0)
		{
			factors++;
			num = num / primes[i];
			divided = true;
			break;
		}
	}
	//if no divisions happen we've come across a prime larger than our
	//prime set. we just mark it as a factor and move along
	if (!divided)
	{
		num = 1;
		factors ++;
	}
	if (num != 1)
		return Factors(num,primes,factors);
	else
		return factors;
}
int SemiPrime (int max, vector<int> const &primes)
{
	int Answer = 0;
	for (int i = 3; i <= max; i++)
	{
		if (Factors(i,primes,0) == 2)
			Answer++;
	}
	return Answer;
}
int main(int argc, char** argv)
{
	vector<int> p = Primes(10000);
	int max = 100000000;
	int Answer= SemiPrime(max,p);

	cout << "Answer is :: " << Answer << endl;
	return 0;
}

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

Project Euler Problem #214: First Attempt.

September 2nd, 2010

Problem 214 says:

Let φ be Euler’s totient function, i.e. for a natural number n, φ(n) is the number of k, 1 ≤ k ≤ n, for which gcd(k,n) = 1.

By iterating φ, each positive integer generates a decreasing chain of numbers ending in 1.
E.g. if we start with 5 the sequence 5,4,2,1 is generated.
Here is a listing of all chains with length 4:
5,4,2,1
7,6,2,1
8,4,2,1
9,6,2,1
10,4,2,1
12,4,2,1
14,6,2,1
18,6,2,1

Only two of these chains start with a prime, their sum is 12.

What is the sum of all primes less than 40000000 which generate a chain of length 25?

My first approach is to build a list of primes less than 40000000, and keeps a hashtable of all the totients that the program solves for, as well as a hashtable for storing all of the previous chains the program has come across. It works but it takes an age to give the answer, even when using .net 4′s task parallel library. So I’ll be reworking this and posting a better version.

Until then, here is the code. (C# requires .net 4)

using System;
using System.Collections;
using System.Collections.Generic;
using System.Threading;
using System.Threading.Tasks;
namespace Problem214
{
	class MainClass
	{
        public static long[] primes = GetPrimesUpTo(40000000);
		public static Hashtable knownTotients = new Hashtable();
        public static Hashtable KnownChains = new Hashtable();
        private static object lockObject = new object();
        private static object lockObject2 = new object();

		public static void Main (string[] args)
		{
			long sum = 0L;
            Console.WriteLine("starting search");
            Parallel.ForEach(primes, p =>
            {
                //Console.WriteLine(p);
                if (Chain25((int)p))
                {
                    lock (lockObject)
                    {
                        sum = sum + p;
                        Console.WriteLine("Current Sum :: "+sum.ToString());
                    }
                }
            });
            Console.WriteLine(sum);
			Console.ReadLine();
		}
		static bool Chain25 (int num)
		{
			if (ChainLen(num) == 25)
				return true;
			else
				return false;
		}
		static int ChainLen (int num)
		{
			int c = chain(num,1);
            KnownChains.Add(num, c);
			return c;
		}
		static int chain(int num, int len)
		{
            if (KnownChains.Contains(num))
                return len + (int)KnownChains[num];
			if (len >= 25) return 60000;
            int phin = eulerTotientWrap(num);
			if (phin != 1) return chain(phin,len+1);
			else return len++;
		}
		static bool[] GetPrimeSieve(long upTo)
		{
		    long sieveSize = upTo + 1;
		    bool[] sieve = new bool[sieveSize];
		    Array.Clear(sieve, 0, (int)sieveSize);
		    sieve[0] = true;
		    sieve[1] = true;
		    long p, max = (long)Math.Sqrt(sieveSize) + 1;
		    for (long i = 2; i <= max; i++)
		    {
		        if (sieve[i]) continue;
		        p = i + i;
		        while (p < sieveSize) { sieve[p] = true; p += i; }
		    }
		    return sieve;
		}
		static long[] GetPrimesUpTo(long upTo)
		{
		    if (upTo < 2) return null;
		    bool[] sieve = GetPrimeSieve(upTo);
		    long[] primes = new long[upTo + 1];

		    long index = 0;
		    for (long i = 2; i <= upTo; i++) if (!sieve[i]) primes[index++] = i;

		    Array.Resize(ref primes, (int)index);
		    return primes;
		}
		static int GetLastIndex(int n)
		{
			for (int i = 0; i< primes.Length;i++)
			{
				if (primes[i] >= n)
					return i+1;
			}
			return primes.Length;
		}
        static int eulerTotientWrap(int n)
        {
            if (knownTotients.Contains(n))
                return (int)knownTotients[n];
            int t = eulerTotient(n);
            lock (lockObject2)
            {
                if (!knownTotients.Contains(n))
                    knownTotients.Add(n, t);
            }
            return t;

        }
		static int eulerTotient(int n)
		{
		    int numPrimes = GetLastIndex(n);

		    int totient = n;
		    int currentNum = n, temp, p, prevP = 0;
		    for (int i = 0; i < numPrimes; i++)
		    {
		        p = (int)primes[i];
		        if (p > currentNum) break;
		        temp = currentNum / p;
		        if (temp * p == currentNum)
		        {
		            currentNum = temp;
		            i--;
		            if (prevP != p) { prevP = p; totient -= (totient / p); }
		        }
		    }
		    return totient;
		}
	}
}

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