Problem 97

Projekt Euler w Ruby
1

The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 2^(6972593)−1; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2^§−1, have been found which contain more digits.

However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 28433×2^(7830457)+1.

Find the last ten digits of this prime number.

[code=ruby]digits = Array.new(10, 0)
digits[0] = 1

7830457.times do |i|
carry = 0
digits.each_with_index do |a, j|
product = digits[j] * 2
digits[j] = product % 10 + carry
carry = product / 10
end
end

number = (digits.join.reverse.to_i*28433+1).to_s.reverse[0…9].reverse
puts number[/code]

2

Można to też zrobić dużo szybciej mnożąć liczbę przez 2 modulo 10000000000

3

A to moje rozwiązanie z szybkim potęgowaniem:

[code=ruby]#!/usr/bin/env ruby

def pow_mod(x, n, rem)
y = 1
t = x
until n == 0
y = (yt)%rem unless (n&1) == 0
t = (tt)%rem
n >>= 1
end
y
end

p (28433*pow_mod(2, 7830457, 1010)+1)%(1010)[/code]

4

Podobne rozwiązanie

[code=ruby]class Fixnum

def pow_with_mod(k, p)
return 1 if k == 0

dane = self.pow_with_mod(k/2, p)

if (k % 2 == 0)
  (dane*dane) % p
else
  (self*(dane*dane)) % p
end

end

end

n = (28433*(2.pow_with_mod(7830457, 10**10))+1).to_s[-10, 10]
puts n[/code]

[code]:!time ruby E097.rb
8739992577

real 0m0.014s
user 0m0.012s
sys 0m0.000s[/code]