k-Step m-Scale Fibonacci Numbers

Tags

,

Anyone reading this is surely familiar with the Fibonacci numbers, that very famous sequence defined by the recurrence:

\text{fib}(n) = \text{fib}(n-1) + \text{fib}(n-2)

with:

\text{fib}(0) = 1 \text{, and fib}(1) = 1.

And though it’s not typical, for our purposes here it will be convenient to redefine the sequence so that:

\text{fib}(0) = 1 \text{ and fib}(1) = 2.

Using this later definition, which is simply a shift by one place, it can be shown for n>0 that the nth Fibonacci number corresponds to the number of bit strings of length n that do not contain the sub-string “11”. Thus the number of bits strings of length n that do contain the sub-string “11” is:

2^n - \text{fib}(n).

We can also define a Fibonacci-like sequence with three terms as follows:

\text{fib}_3(n) = \text{fib}_3(n-1)+ \text{fib}_3(n-2) + \text{fib}_3(n-3)

with:

\text{fib}_3(0)=1, \text{fib}_3(1) =2 \text{,and fib}_3(2) = 4.

And in general this notion can be extended to a k-term, or rather k-step, sequence where:

\displaystyle \text{fib}_k(n) = \sum^k_{i=1} \text{fib}_k(n-i)

See Wolfram Math World’s great explanation for more about this, although they obviously do not shift the sequences as we have done here. Notice however, that when shifted, the k-step Fibonacci sequences presented at Math World begin with the sub-sequence:

(1,2,4,...)=(2^0, 2^1, ..., 2^{k-1})

To generalize our bit string example from before, it can be observed that the nth term of the k-step Fibonacci sequence corresponds to the number of bit strings of length n that do not contain a sub-string of length k that is composed of all ones.

The Fibonacci numbers can be further generalized by introducing a scaling factor m, where we define:

\displaystyle \text{fib}_{k,m}(n) = (m-1)\sum^k_{i=1} \text{fib}_{k,m}(n-i)

where the initial elements of the sequence fibk,m are:

(m^0, m^1, ..., m^{k-1})

And thus:

\text{fib}_{2,2}(n)

corresponds to the regular old Fibonacci numbers.

It turns out that the nth term of fibk,m corresponds to the number of strings of length n using an alphabet of size m that do not have a sub-string of k consecutive ones, assuming of course that the character “1” is part of the alphabet. Conversely, the number of strings that do contain such a sub-string is equal to:

m^n - \text{fib}_{k,m}(n)

For example see OEIS sequence A028859 and A119826, which correspond to fib2,3 and fib3,3 respectively.

Another interesting bit about all of this concerns the the limit of fibk,m(n+1)/fibk,m(n) as n goes to infinity. Here again fib2,2 has a special place as:

\displaystyle \lim_{n \rightarrow \inf} \frac{\text{fib}_{2,2}(n+1)}{\text{fib}_{2,2}(n)} = \varphi

where φ is the Golden Ratio, one of the more interesting irrational numbers. It is also a root of the polynomial:

f(x)=x^2-x-1

More generally:

\displaystyle \lim_{n \rightarrow \inf} \frac{\text{fib}_{k,m}(n+1)}{\text{fib}_{k,m}(n)}

is a root of the polynomial:

\displaystyle f(x)=x^k - (m-1) \sum^{k-1}_{i=0} x^i.

Here is some Python code for playing with all of this.

#!/usr/bin/python

import re
import itertools

def i2bs(i, l, m):
    """
    Convert an incoming number into a 'bitstring' representation
    of length 'l' using an alphabet of size 'm'. This behavior of
    this function is undefined if m>10.
    """
    i = int(i)
    out = ""
    while i:
        out = str(i%m) + out
        i /= m
    delta = l - len(out)
    if delta > 0:
        out = ("0" * delta) + out
    return out

def fib(n, k=2, m=2):
    """
    Generate the nth k-step, m-scale fibonacci number. 

    n specifies which index in the sequence to generate. (length of the over all string)
    k specifies how many terms the recurrence has (length of the subsequence we are searching)
    m is the factor that each term of the reccurrence is multiplied by plus 1 (size of alphabet)

    The output is the nth number in the sequence, which is also equal to the number of
    times the subsequence "1"*k appears in the permutations of length n over the alphabet.
    """
    f = [pow(m,i) for i in range(k)]
    if n < len(f):
        return f[n]
    i=k
    while i < n:
        f[i%k]=sum(f)*(m-1)
        i+=1
    return sum(f)*(m-1)

def matchbits(k,m):
    """
    This function allows us to play with the proposition that fib(n,k,m) is the number
    of substrings "1"*k in the permutations of length n over an alphabet of size m.

    k is the size of substring to match
    m is the size of the alphabet
    """
    print("***",k,m)
    ss=k*"1"

    for n in range(k,10):
        matches=0
        total=pow(m,n)
        for i in range(total):
            x = i2bs(i,n,m)
            if re.search(ss,x):
                matches += 1

        f =fib(n,k,m)
        print(("Subsequence=%s, Actual Matches=%d, Predicted Matches=%d, Okay=%s") %
              (ss, matches, total-f, ((total-f)== matches)))

def poly(k,m,x):
    """
    Evaluate the polynomial f(x) = x^k - (m-1)*x^(k-1) - ... - (m-1)
    """
    return x**k + sum([-(m-1)*x**i for i in range(k)])

def checkroots(n, coefficients):
    """
    Allows us to play with the polynomials of which fib(n+1, k, m)/fib(n, k, m)  is a root.
    """
    for (k,m) in itertools.product(coefficients, coefficients):
        fn = fib(n,k,m)
        fn1 = fib(n+1,k,m)
        x=float(fn1)/float(fn)
        print("k=%d, m=%d, x=%f, f(x)=%f") % (k, m, x, poly(k,m, x))

def main():
    print("Check Roots")
    checkroots(100, [2,3,4,5])

    print("\n")

    print("Match Bits:")
    matchbits(2,2)
    #matchbits(3,2)
    #matchbits(3,4)
    #matchbits(5,4)

if __name__ == "__main__":
    main();
Advertisements

Execute a Bash Command Taking Arguments From a File Line by Line

Tags

Suppose we have some file, say commands.txt, every line of which specifies the arguments to a particular command we would like to run.

For example, take the command cp -f and commands.txt as the following:

../../foo1.txt bar1.txt
../../foo2.txt bar2.txt

Then we would expect two commands to be executed.

cp -f ../../foo1.txt bar1.txt
cp -f ../../foo2.txt bar2.txt

The the following bash snippet performs this task.

OLDIFS=$IFS
export IFS="
"
for l in `cat commands.txt`
do
   eval "cp -f $l"
done
export IFS=$OLDIFS

Recursively Zip a Directory with Ruby

Tags

,

In order to run this code you’ll need to install the gem rubyzip.

Also be forewarned that I am just learning Ruby so this may not be the coolest Ruby code ever, but I believe it does work. Of course, YMMV.

require 'zip/zip'

# This is a simple example which uses rubyzip to
# recursively generate a zip file from the contents of
# a specified directory. The directory itself is not
# included in the archive, rather just its contents.
#
# Usage:
#   directoryToZip = "/tmp/input"
#   outputFile = "/tmp/out.zip"   
#   zf = ZipFileGenerator(directoryToZip, outputFile)
#   zf.write()
class ZipFileGenerator

  # Initialize with the directory to zip and the location of the output archive.
  def initialize(inputDir, outputFile)
    @inputDir = inputDir
    @outputFile = outputFile
  end

  # Zip the input directory.
  def write()
    entries = Dir.entries(@inputDir); entries.delete("."); entries.delete("..") 
    io = Zip::ZipFile.open(@outputFile, Zip::ZipFile::CREATE); 

    writeEntries(entries, "", io)
    io.close();
  end

  # A helper method to make the recursion work.
  private
  def writeEntries(entries, path, io)
    
    entries.each { |e|
      zipFilePath = path == "" ? e : File.join(path, e)
      diskFilePath = File.join(@inputDir, zipFilePath)
      puts "Deflating " + diskFilePath
      if  File.directory?(diskFilePath)
        io.mkdir(zipFilePath)
        subdir =Dir.entries(diskFilePath); subdir.delete("."); subdir.delete("..") 
        writeEntries(subdir, zipFilePath, io)
      else
        io.get_output_stream(zipFilePath) { |f| f.puts(File.open(diskFilePath, "rb").read())}
      end
    }
  end
    
end

This code has also been contributed to the rubyzip project as an example.

Enter Ruby on Rails

Tags

, ,

My environment consists of a desktop computer running Windows 7.

To get Ruby on Rails going I did the following.

Downloaded and installed Virtual Box.

Created a virtual machine with xubuntu.

The packages curl and git are needed to install rvm (Ruby Version Manager).

You can then follow the instructions for installing rvm, but before building Ruby make sure that the packages zlib1g-dev and libssl-dev are installed. If you don’t have this stuff installed before building Ruby, then Ruby is not built with support to run gems or rails.

Later down the road Rails will need node.js.

AFAIK there may be more packages which I should have installed. WTFK?

Anyway, it’s probably best to do all of the installations with synaptic (or apt) before starting with rvm at all.

For rvm we run:

$ bash < <(curl -s https://rvm.beginrescueend.com/install/rvm)
$ rvm install 1.9.2

Let’s also make 1.9.2 our default.

$ rvm default 1.9.2

It’s probably also best to read the rvm basics guide.

Now we can install rails.

gem install rails

Finally, we can restart the VM and map a port from our host to the port rails will run on so that we can hit our new web application from Windows land if desired. You don’t have to use VBoxManage for this. Virtual Box has a GUI for setting up port forwarding: Settings->Network->Advanced->Port Forwarding.

Having the port mapping will be good for testing IE compatibility at some point.

Bash function for ‘cd’ aliases

Tags

,

Once upon a time I was playing with Windows Power Shell (WPSH) and discovered a very useful function for changing to commonly visited directories. The function, called “go”, which was written by Peter Provost, grew on me as I used WPSH — so much so that I decided to implement it in bash after my WPSH experiments ended.

The problem is simple. Users of command line interfaces tend to visit the same directories repeatedly over the course of their work, and having a way to get to these oft-visited places without a lot of typing is nice.

The solution entails maintaining a map of key-value pairs, where each key is an alias to a value, which is itself a commonly visited directory. The “go” function will, when given a string input, look that string up in the map, and if the key is found, move to the directory indicated by the value.

The map itself is just a specially formatted text file with one key-value entry per line, while each entry is separated into key-value components by the first encountered colon, with the left side being interpreted as the entry’s key and the right side as its value.

Keys are typically short easily typed strings, while values can be arbitrary path names, and even contain references to environment variables. The effect of this is that “go” can respond dynamically to the environment.

Finally, the “go” function finds the map file by referring to an environment variable called “GO_FILE”, which should have as its value the full path to the map.

Before I ran into this idea I had maintained a number of shell aliases, (i.e. alias dwork=’cd $WORK_DIR’), to achieve a similar end, but every time I wanted to add a new location I was forced to edit my .bashrc file. Then I would subsequently have to resource it or enter the alias again on the command line. Since I typically keep multiple shells open this is just a pain, and so I didn’t add new aliases very often. With this method, a new entry in the “go file” is immediately available to all open shells without any extra finagling.

This functionality is related to CDPATH, but they are not replacements for one another. Indeed CDPATH is the more appropriate solution when you want to be able to “cd” to all or most of the sub-directories of some parent. On the other hand, “go” works very well for getting to a single directory easily. For example you might not want “/usr/local” in your CDPATH and still want an abbreviated way of getting to “/usr/local/share”.

The code for the go function, as well as some brief documentation follows.

##############################################
# GO
#
# Inspired by some Windows Power Shell code
# from Peter Provost (peterprovost.org)
#
# Here are some examples entries:
# work:${WORK_DIR}
# source:${SOURCE_DIR}
# dev:/c/dev
# object:${USER_OBJECT_DIR}
# debug:${USER_OBJECT_DIR}/debug
###############################################
export GO_FILE=~/.go_locations
function go
{
   if [ -z "$GO_FILE" ]
   then
      echo "The variable GO_FILE is not set."
      return
   fi

   if [ ! -e "$GO_FILE" ]
   then
      echo "The 'go file': '$GO_FILE' does not exist."
      return
   fi

   dest=""
   oldIFS=${IFS}
   IFS=$'\n'
   for entry in `cat ${GO_FILE}`
   do
      if [ "$1" = ${entry%%:*} ]
      then
         #echo $entry
         dest=${entry##*:}
         break
      fi
   done

   if [ -n "$dest" ]
   then
      # Expand variables in the go file.
      #echo $dest
      cd `eval echo $dest`
   else
      echo "Invalid location, valid locations are:"
      cat $GO_FILE
   fi
   export IFS=${oldIFS}
}

Hello world!

The Art of Software is up and ready to go, and you’re reading the very first post.

If in fact you are reading this, then I’ve made enough progress over the last few months to convince myself that going public was a good idea. If not, well then, how could you be reading this?

The idea here is to publish my thoughts on software engineering, programming, and related topics.

Before that the first order of business is to migrate a set of posts from another blog and then to get going here. We’ll begin with one article per month, and with some luck and perseverance increase the frequency to once per week.

As I find items of interest around the web I will post them as well.

That’s it for now. Onward!