Skip to main content

Venturing into Number Theory

In attempt to solve a maths problem with Ruby, I discovered the benefits of going beyond simple arithmetic. Perhaps surprisingly, many seemingly complex mathematical problems can be solved using basic arithmetic and raw computing power. Most of the time this doesn't pose a problem. However, as the values involved grow larger, the demands on the computer's memory reaches a critical point beyond which you risk crashing your computer. 

The problem I was trying to solve was the following:


   What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

After causing my computer to hang for several minutes, I realized I had to rewrite the program I was working on. The program had to take shortcuts, so that instead of testing every single value between 1 and 1 million, it only tested likely values. With the help of my lovely wife (a Maths teacher) I rewrote the program using prime numbers.  

class SmallestProduct

require 'prime'

  def initialize(target)
    @target = target
    @primes=[]
    @divisors = []
  end

  def primes_finder
    Prime.each(@target) {|prime| @primes<<prime}
    @primes
  end

  def divisor_finder

    power_max = (@target ** 0.5).floor
    @primes.each do |prime|
      identified=false
      n = power_max
      until identified
        if prime**n < @target
          @divisors << prime ** n
          identified = true
        end
        n-=1
      end
    end
    @divisors
  end

  def product_finder
    smallest = 1
    @divisors.collect {|divisor| smallest *= divisor}
    puts "The smallest number divisible by all numbers from 1 to         your test value is:
     #{smallest}"
  end
end

  def user_input
    puts
    puts "This program finds the smallest number that is evenly         divisible by all numbers between 1 and a value of your choice."
    puts
    puts "What value are you interested in testing: "
    choice = STDIN.gets.to_i
    search = SmallestProduct.new(choice)
    search.primes_finder
    search.divisor_finder
    search.product_finder
  end


  user_input

The 'workhorse' of this program is the divisor_finder method. 
  1. It starts with the array of primes created by the prime_finder. (e.g. primes under 10 = [2,3,5,7])
  2. It then creates a variable called power_max which is the nearest integer square root of the target value. (e.g. if your target is 10, power_max would be 3.)
  3. It then raises each of the primes from prime_finder to power_max. If the result is under the target, the result is stored in the divisors array. (e.g. 2^3 = 8, therefore 8 becomes a divisor). If the prime raised to power_max is above the target, power_max is reduced by 1 and a new test is made.  (e.g. prime = 3; 3^3 =27, which is above 10. So 3^2 tested which equals 9 which is below 10. Therefore 9 becomes a  divisor.) 
  4. Why do we do this? If a number is divisible by 8, then it is divisible by 4 and by 2. So if we're trying to find a number divisible by all values from 1 to 10, we don't need to go through and test 1 to 10 every time. If the number is evenly divisible by 8, we skip 4 and 2. If it's divisible by 9 we skip 3 and so on. Still working with 10, the divisors we would be left with are [5,7,8,9]
  5. Once all divisors have been identified, the magic happens. If you multiply the identified divisors by each other, you get the smallest product divisible by all numbers from 1 to your target.So 5 x 7 x 8 x 9 = 2520. 2520 is the smallest number divisible by all numbers from 1 to 10.
     
Magic!

Comments

Popular posts from this blog

Einstein's Logic Puzzle (SPOILER ALERT!)

On Monday I began working through a Discrete Math textbook in preparation for some courses I'll be taking in January. There was a beautiful logic problem in Chapter 1, apparently created by Einstein. This is one version of it: Five men with  different nationalities and with different jobs live in  con secutive houses on a street. These houses are painted  dif ferent colors. The men have different pets and have   dif ferent favorite drinks.  Determine who owns a zebra and  whose favorite drink is mineral water (which is one of the  favorite drinks) given these clues:  The Englishman lives  in the red house.  The Spaniard owns a dog.  The Japanese  man is a painter.  The Italian drinks tea.  The Norwegian  lives in the first house on the left.  The green house is  immediately to the right of the white one. The photogra pher  breeds snails.  The diplomat lives in the yellow house. ...

Job as Entry Level Developer

After 4 months of work, sometimes focused, sometimes not, I accepted a job as an Entry Level Ruby on Rails Developer yesterday. This is after starting with zero knowledge on November 1, last year. Beyond knowing a little about coding (but getting the definitions of  REST and AJAX wrong), what were the reasons for the job offer?  I think it was the meetup group I started in January that made me stand out from the rest. The motivation for the meetup group was to help me become a better coder and to indulge my teacher instincts. After some initial meetings at the library and my home, an IT hub in town offered to host us. This meant extra advertising and prestige for the group. After announcing the meetup group at an Agile meetup group for developers, I got some volunteers to give talks. The first volunteer offered a talk on Ruby. As I was comfortable with Ruby I prepared a coding tutorial .  After the tutorial, which was attended by some beginners and some a...

Algorithm Analysis - 1

Currently, I'm learning to perform algorithm analysis using Big-O notation. In one resource I found the following problem: You just dropped a box of glass toys and  n  toys in the box broke in half. You'd like to match the halves of the toys so that you could glue them together, but the only way to tell whether two halves belonged to one toy is to physically pick up the two pieces and try to fit them together. Express how long this matching process will take in terms of  n . The answer given is n^2 (n squared) with the following explanation:  You have to compare every piece with every other piece. If you have 1 toy and it breaks in half, you have 1 comparison to make. If you have 2 toys and they both break in half there are 4 pieces and you have to do 6 comparisons. If you have 3 toys, there are 6 pieces and you have to do 15 comparisons. If you have  N/2  toys, you have  N  pieces and you have to do N-1 + N-2 + N-3 + ... + 1 =(N)(N-1)/2...