15 Mar 10 Project Euler : Problem 29 in Ruby

I spent some time playing around with a way to reduce calculations by constructing something akin to a sieve, (2^16 is the same as 4^8 and 16^4), but it turns out that the brute force solutions runs in under a second on my machine so it seemed silly to spend any more time with it.

Ruby even minds the big numbers for me, so the solution is quite trivial:

Problem #29

How many distinct terms are in the sequence generated by a^(b) for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

MIN, MAX = 2,100
values = []

(MIN..MAX).each do |base|
  (MIN..MAX).each do |power|
    values << base**power
  end
end

puts values.uniq.length

Tags: project euler, ruby

11 Mar 10 Project Euler : Problem 27 in Ruby

I've taken ill for the last two days, so I've been working on a couple Project Euler problems in between trips to the bathroom.

Problem #27

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

Since you start with n = 0, you know that b always has to be prime in order to satisfy n = 0.

Next, if b must be prime, and all primes greater than 2 are odd, and we don't care about expressions resulting in less than 3 consecutive primes (example expression has 40), then we know that all values of a must be odd in order to satisfy n = 1!

I also suspect that for the number of consecutive primes we need to 'win', that we only need to look at negative values of a, but I'm having a heck of a time trying to prove it.

027.rb

require 'prime_generator'

# pre-calculate primes
MAX     = 1_000
primer  = Prime_Generator.new MAX
primes  = primer.stack
product = 0
highest = 0

# a must be odd
(0..MAX).each do |i|
  next if i & 1 == 0

  # b must be prime
  primes.each do |b|

    # a can be positive or negative
    [i,-i].each do |a|
      n = 0
      while n += 1 do
        break unless primer.is_prime?(n ** 2 + a * n + b)
      end

      if highest < n
        highest = n
        product = a * b
      end

    end
  end
end

puts product

And here's the prime generator I'm using:

prime_generator.rb

class Prime_Generator

  attr_reader :stack

  def initialize max = 3
    @stack  = [1,2,3]
    fill_to max
  end

  def fill_to max
    n = 1
    while true do
      n += 4
      return @stack if n > max
      @stack << n if is_prime? n

      n += 2
      return @stack if n > max
      @stack << n if is_prime? n
    end
  end

  def is_prime? n
    return false if n <= 0
    max = Math.sqrt(n).floor
    fill_to(max + 1) if max > @stack.last

    @stack.each do |i|
      next if i == 1
      return true if i > max
      return false if n % i == 0
    end

    true
  end

end

You can find more Project Euler solutions here: https://svn2.assembla.com/svn/joe-zack-personal/projects/euler/ruby/

Tags: project euler, ruby

22 Sep 09 Project Euler: Problem 30 in Ruby

I realize this isn't the fast solution, but the more I optimized, the uglier it got so I'm done playing with it. The hardest part was figuring out what the upper bound limit was.

Problem 30

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

power, total = 5, 0

(power * 9**power).times do |i|
  total += i if i == i.to_s.split('').inject(0) {
    |sum, n|
    sum + n.to_i**power
  }
end

puts total - 1

Tags: project euler, ruby

18 Aug 09 Project Euler: Problem 26 in Ruby

I knew I'd be implementing my own division algorithm for this problem, but I had a hard time figuring out a good way to detect the repeating sequence.

That's all I have to say about that.

Problem #26

Find the value of d 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

def divide n, d, repo = []
  return repo.size - repo.index(n) if repo.include? n
  divide 10 * (n - (n / d) * d), d, repo << n
end

highest = {"d" => 1, "count" => 1}

(1..499).each do |i|
  x     = i * 2 + 1
  count = divide 1, x
  if count > highest['count']
    highest = {"d" => x, "count" => count}
  end
end

puts highest["d"]

Tags: project euler, ruby

def nth_lexical_permutation values, key = "", chain = ""

  chain    = chain + key.to_s
  children = values.select { |i| i != key }

  $count -= 1 if children.size == 0
  return chain if $count == 0

  children.each do |i|
    result = nth_lexical_permutation children, i, chain
    return result if result.size > 0
  end
  ""
end

$count = 1_000_000
set    = (0..9).to_a

puts nth_lexical_permutation(set)