Euler Problem 10

Find the sum of all the primes below two million

I’d say this is the first of the problems Greg and I have tackled that would really benefit from the kind of optimisations we’ve both added to our previous solutions. The Ruby solution below would take an age to complete:

range  = 1999999
sumofprimesbelowrange = 2
def isPrime(num)  
  i = 2
  while i<num
    if num%i == 0
        return false
    end
    i=i+1  
  end  
end
while range > 1
  if isPrime(range) != false
    sumofprimesbelowrange=sumofprimesbelowrange+range
  end
range=range-1
end
puts "Sum of all primes below #{range}"
puts "is #{sumofprimesbelowrange}"


improvements

If a number A (in our range) can be divided to a whole by number B, then it stands that the result of that division will also fail. The next example still takes a long time to return:

range  = 2000000
counter = 2
sumofprimesbelowrange = 2
def isPrime(num)  
  i = 2
  while 2*i<num
    if num%i == 0
         
        return false
    end
    i=i+1  
  end  
end
while counter < range
  if isPrime(counter) != false
    puts counter
    sumofprimesbelowrange=sumofprimesbelowrange+counter
  else
   
  end
counter=counter+1
end
puts "Sum of all primes below #{counter}"
puts "is #{sumofprimesbelowrange}"


Odds

We also know that the 2 is the only even prime number, so we can ignore all even numbers above 2 completely:

def isPrime(num)
  if num%2==0
  return false;
  end
  i = 2
  while 2*i<num
    if num%i == 0
         
        return false
    end
    i=i+1  
  end  
end

After a little reading into primes, the method I’m using is known as trial division. A further available optimisation allows us to only examine any division up to the square root of the number we’re checking. So our routine can be amended such:

def isPrime(num)
  if num%2==0
  return false;
  end
  i = 2
  while i*i<=num
    if num%i == 0
         
        return false
    end
    i=i+1  
  end  
end

This small change has a big effect, reducing the running time of the script to a matter of a few minutes.

This weeks challenge has been the most interesting yet, I now have lots of additional reading to do on the other possible solutions.

Day 33, Moo-cough and I

February 2nd

February 2nd


Only in discussion during today did I realise that yesterday’s ready-made was, when examined with or without prior knowledge of me, probably the most descriptive and personal work so far.

I’m happy that things are taking a turn, I’d hate to end the year with a majority output of still-looking sketches of varying quality. The range of media, and the developing themes I’m following are giving me lots to think about, much to enjoy and more to look forward to.

Continuing the slightly obscure theme, this is the first digital work of the project, Illustrator and a little Photoshop.

I do not smoke, I never have. I do own a pipe, and a plastic bull.

 

January draws to a close

Here’re the final self-portraits for January, representing a return to hasty.

Again, I’ve been very busy in other areas of life so time for portraiture has been slim.

Taking a line for a walk

January 23rd - 2

January 23rd

January 23rd was a good day, there’re two images here drawn using a single line, from the view in a mirror and with no glancing at the paper  – so features appear all over the place. They were then photographed in negative. I’m particularly happy with how expressive these two are.

There were too many quick sketches last week (even on café napkins), and again I’ve considered halting ‘one self-portrait a day‘ in favour of longer term projects.

However, I keep coming back to the ideas I’ve not yet explored, such as abstraction and typographic treatments that could be executed in a short time.

In the coming weeks I’m going to consider applying themes to a week’s output, as a means of ensuring I explore something new every day.

Project Euler, problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

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

This one needed some rambling thought before I settled down to an approach. I had thought that there should be a more effective method than simply counting upwards while testing each number in the range.

I settled on the simple approach when I realised that when checking the current highest number, you can skip all remaining items in the range should there be a single failure to evenly divide.

My brief, if inelegant solution – which I’ll hopefully refine in the next few days – is copied below (written in Ruby). I can’t help but think there are ways to:

  • cut down the number of division checks
  • increment the high number by greater degrees each time

So plenty still to examine with this one.

$greatestNumber = 1
def checkHigh()
  rangeLow = 1
  rangeHigh = 20
  i =  rangeHigh  
  singleNumbersNonRemainDivCount = 0
  while i >= rangeLow
    if ($greatestNumber % i)   > 0
        singleNumbersNonRemainDivCount=0
        $greatestNumber = $greatestNumber+1    
        i = rangeHigh      
    else
        singleNumbersNonRemainDivCount=singleNumbersNonRemainDivCount+1
        if singleNumbersNonRemainDivCount == rangeHigh
          puts "Highest number: #{$greatestNumber}"
          $greatestNumber   = $greatestNumber-1
        end
        i=i-1
    end
  end
end
checkHigh()

Only 344 days to go

Here’s the crop of self-portraits from the last week:

January 16th:

A frustrating start to the week – a small oil study that I had to abandon. I took a rag to the wet surface in the hope of resurrecting it at some point.

January 17th:

I returned to pencil & cartridge paper, looking at the shots I took of this showed me I need to watch my shading – I did some corrections before uploading the day’s final image.

January 18th:

Light blue letraset marker on watercolour paper, stood very close to the mirror.

January 19th:

Heavily sleep deprived in this one, so no smiles. Enjoyed the differences made by holding my head – fold’s around the eyes and more interesting shadows.

January 20th:

A quick follow up of the same themes on the next night – having had some sleep. Again some tonal adjustments made with an eraser before finalising.

January 21st:

A total departure – animal transformation for a start, and my first linocut print in more years than I care to recall.

Linocut is very rewarding – the design was drawn up in a sketchbook and applied in pencil then ink, but was being adapted during the cutting process. Cutting took about an hour to complete. I had hoped printing would have been more successful, so I’ll be working on the home pressing techniques.

January 222nd:

After last night’s lino print, I’d tried to get a monoprint from the remaining ink on the glass but was unsucessful. I rolled the ink evenly again and left it to dry so that today I could scratch into it directly and then backlight it, here’s the result of some swift scratching.

media

I’ve thought alot about media this week – particularly grounds and supports – with an anything-goes mindset.

I’ve tried painting on a (spare, unused) smoke alarm (pencil works well, but using an eraser was surprisingly problematic given the plastic surface) and I’m now considering what can be achieved with other materials as either a support or a sculptural / relief material.

Expect noodles.

How it’s going

I’ve been tempted this week to adapt (at best) or abandon the whole project – mainly because it’s already provided me with the intended results – I’m working creatively, regularly and in range of media.

I now have a list of painting, printing and other works I want to begin, so producing a daily portrait can seem like a burden.

Perhaps ‘one self-portrait a fortnight’ will be the way to go? For now I’m going to persevere. I’ve proved I can make the time so I’ll try to get some longer-term projects running in parallel.

Project Euler problem 8

The latest in a series of paired-up problem workings with Greg Bowie. This week we’re looking at Problem 8:

Discover the largest product of five consecutive digits in a the [provided] 1000-digit number

Here’s my response, longhand:

  1. I’ll need a variable to store the (current) value of the greatest product
  2. I’ll need to iterate through the 1000-digit number, reading 5 digits at a time working out the product of each sequence, stepping one digit on with every iteration.
  3. The routine will begin from the 1st digit. The process will stop 5 digits of the final digit
  4. Using variables to store the length of the 1000-digit number and the number of digits we’re deriving the product of would make the solution more adaptable for other numbers and sequences
  5. Each product retrieved from every sequence of 5 digits must be compared to the current greatest product. If this exceeds the current greatest product, we set this as the new greatest product

This should solve the problem, but why stop now?

Refinements

The presence of zeros in the 1000-digit number is notable – any zero encountered while examining the product of multiple digits will result in a zero product. So I’ll ignore them:

  1. Create an array of smaller numbers by splitting the 1000-digit number by any zero digit – handling sequences of zeros so as to prevent empty array items
  2. Iterate through each of these numbers, deriving the product of each set of 5 digits, and checking this against the current greatest product

Chances are this refinement will not improve the performance of this test on a single number, but as it reduces the number of product-derivation runs by 398 by it may scale well, depending on the language.

ratherLongNumber = 73167176531330624919225...
numDigits = ratherLongNumber.to_s.length
considerRange = 5
totalcomparisons = 0
$greatestProduct = 0
while totalcomparisons range = ratherLongNumber.to_s[totalcomparisons,5]
rangeproduct = range.split(//).map(&amp;:to_i).inject(:*)
$greatestProduct = $greatestProduct&gt;rangeproduct ? $greatestProduct:rangeproduct
totalcomparisons=totalcomparisons+1
end
puts "#{$greatestProduct}"

Refined version:

ratherLongNumber = 73167176531330624919225...
def getProductOfRange(inputNumber,considerRange)
# puts inputNumber
numberofcomparisons = 0
localGreatestRange = 0
while numberofcomparisons range = inputNumber.to_s[numberofcomparisons,5]
rangeproduct = range.split(//).map(&amp;:to_i).inject(:*)
numberofcomparisons=numberofcomparisons+1
localGreatestRange = localGreatestRange&gt;rangeproduct ? localGreatestRange:rangeproduct
end
return localGreatestRange ,numberofcomparisons
end
$greatestProduct = 0
arrayOfNumbers = ratherLongNumber.to_s.split(/0+/).map(&amp;:to_i)
arrayOfNumbers.each{
|a|
tmp2,comparisons = getProductOfRange(a,5)
$greatestProduct = $greatestProduct&gt;tmp2 ? $greatestProduct:tmp2
}
puts "#{$greatestProduct}"

here’s Greg’s response, posted simultaneously today.

update 23/01/2012:

Revisiting this afresh I realise there’re other ways to skip those pesky zeros, rather than drop them into an array, better to simply skip past any such sequence:

ratherLongNumber = 73167176531330624919225...
numDigits = ratherLongNumber.to_s.length
considerRange = 5
greatestProduct = 0
cursor = 0
skipped = 0
while cursor &lt;= numDigits-considerRange
range = ratherLongNumber.to_s[cursor,considerRange]
if range.index('0')
cursor=(cursor+range.index('0'))+1
skipped=skipped+1
else
rangeproduct = range.split(//).map(&amp;:to_i).inject(:*)
greatestProduct = greatestProduct&gt;rangeproduct ? greatestProduct:rangeproduct
cursor=cursor+1
end
end
puts "Greatest Product: #{greatestProduct}"
puts "#{skipped} sequences with zero in the #{considerRange}-digit range skipped"

A second week of self

Week two: surreal, desperate, but going in the right direction.

At the start of the week I found I could get a likeness without looking, just idly doodling in sketchbook. This is bad news, it’s the process of observation that’s important, not the ability to recall. So I’ve tried to take more time over the plain, representational ones this week.

I’ve thrown in some other approaches too – depicting my face upon a small matryoshka doll stood upon a notebook (‘that’s rather sinister’ was one response), and another looking out over the river but will odd, converging shadows.

I am still not producing the kind of work I would like to, but the journey’s begun and most importantly I’m thinking far more, and further ahead.

Available time remains a big factor. Thankfully at the weekend I had some time to run through various ideas and use some other media.