Problem 26
Statement
A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:
1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1
Where 0.1(6) means 0.166666…, and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.
Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.
Solution
The code, in Ruby.
class Fraction
def initialize(num, denum)
@num = num.to_f
@denum = denum.to_f
@value = @num/@denum
end
# This function use the long division algorithm.
# During the division process, if at some time
# we have the same quotient and remainder than a
# previous step, that means we enter a cycle.
def pattern
pat = Array.new()
n = @num.to_i
while true
n*=10 while n<@denum.to_i
r = n%@denum.to_i
q = n/@denum.to_i
n = r
if r==0
return nil
elsif pat.include?([q,r])
return pat[(pat.index([q,r])..-1)]
else
pat << [q,r]
end
end
end
def to_s
"#@num/#@denum"
end
end
def longuest_pattern(d)
long = [0,0]
(2..d).each do |i|
f = Fraction.new(1,i)
if f.pattern
l = f.pattern.length
long[0],long[1] = i,l if l > long[1]
end
end
return long[0]
end
puts longuest_pattern(1000)
No tags for this post.
SPEAK / ADD YOUR COMMENT
Comments are moderated.
Posts