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.
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.
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:
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
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.
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
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.
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
I've been wanting to check out Rhino for a while, and I've been particularly interested in seeing how it compares to Ruby in terms of speed. The results have been a little varied, and it's a deeply flawed comparison. But it's something.
These scripts are just ports of my ruby solutions. There are a few places where I had to roll my own JavaScript functions instead of baked in Ruby methods, but other than that it was nearly line by line translation.
Add all the natural numbers below one thousand that are multiples of 3 or 5.
var total = 0;
for(var i = 0; i < 1000; i++) {
if(i % 3 == 0 || i % 5 == 0) {
total += i;
}
}
print(total);
Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.
function fib(stack, n) {
if(n == 0) {
return 1;
}
if(n == 1) {
return 2;
}
return stack[n - 1] + stack[n - 2];
}
var max = 4000000;
var total = 0;
var stack = [];
for(var i = 0; i < max; i++) {
stack[i] = fib(stack,i);
if(stack[i] > max) {
break;
}
if(stack[i] % 2 == 0) {
total += stack[i]
}
}
print(total);
Find the largest prime factor of a composite number.
function find_highest_prime_factor(n) {
var max = Math.round(Math.sqrt(n));
for(var i = max; i >= 2; i--) {
if(n % i == 0 && find_highest_prime_factor(i) == 1) {
return i;
}
}
return 1;
}
var target = 600851475143;
print(find_highest_prime_factor(target));
Find the largest palindrome made from the product of two 3-digit numbers.
function get_highest_palindrome(high, low) {
var highest = 0;
for(var i = high; i >= low; i--) {
for(var j = high; j >= low; j--) {
sum = i * j;
if(sum <= highest) {
break;
}
if(is_palindrome(sum.toString())) {
highest = max(highest, sum);
}
}
}
return highest;
}
function reverse(string) {
var array = string.split('').reverse();
var out = '';
for(key in array) {
out += array[key];
}
return out;
}
function max(a,b) {
if(a > b) {
return a;
}
return b;
}
function is_palindrome(string) {
return string == reverse(string);
}
print(get_highest_palindrome(999, 100));
What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?
function gcd(a,b) {
var x = a;
var y = b;
var result;
while (y != 0) {
result = x % y;
x = y;
y = result;
}
return x;
}
function lcm(a,b) {
return (a * b) / gcd(a, b);
}
var max = 20;
var min = 11;
var n = min;
for(var i = min; i <= max; i++) {
n = lcm(n,i);
}
print(n);
Tags: javascript, project euler, rhino