Google Recruit
We will solve Google's recruitment problem that was asked in the past. The problem is as follows.
Google Recruit Problem
** Find the first prime number of 10 consecutive digits of e (base of natural logarithm) with ruby. ** However, e (base of natural logarithm) is limited to the following 200 digits.
2.71828182845904523536028747135266249775
7247093699959574966967627724076630353547
5945713821785251664274274663919320030599
2181741359662904357290033429526059563073
81323286279434907632338298807531952510190
Then we will actually solve it. First of all, it is necessary to decide the policy, so if you summarize the tasks
Let's implement these in order.
First, save the 200-digit e (base of natural logarithm) in exp.txt and read the file. When reading from standard input
exp = gets.to_s.chomp.delete(".")
In this case, at runtime
$ ruby google_recruit.rb < exp.txt
And redirect must specify exp.txt.
Since we will not change exp.txt this time, we will refer to the file in the program instead of the command. In ruby, you can read a file by using the read method of File class.
exp = File.read('exp.txt').delete(".")
When the variable exp that stores the read data is output
271828182845904523536028747135266249775
7247093699959574966967627724076630353547
5945713821785251664274274663919320030599
2181741359662904357290033429526059563073
81323286279434907632338298807531952510190
It is output with a line break. This is because the content of exp.txt itself is a line break, so the read one is also a line break.
To eliminate line breaks, specify the line feed code with the delete method.
exp = File.read('exp.txt').delete(".").delete("\n")
27182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251664274274663919320030599218174135966290435729003342952605956307381323286279434907632338298807531952510190
I was able to read the file without any problems.
I want to extract 10 consecutive digits from the beginning of the variable exp that stores the data read earlier. Since each digit can be specified by treating the variable exp as a character string, 10 digits are taken out by using each.
exp = File.read('exp.txt').delete("\n").delete(".")
[*0..exp.length-10].each do |i|
x_digits = exp[i..i+10-1].to_i
puts xdigit
end
When I run it
2718281828
7182818284
.
.
.
1952510190
We were able to extract 10 consecutive digits from the beginning without any problem.
Let's take a look at the main primality test this time. Implement the is \ _prime method that returns true if the argument is a prime number and false if it is not a prime number.
Since a prime number is a number that cannot be divided by anything other than its own number n and 1, divide n in order by 2 to n-1 and return false if it is divisible. The program is as follows.
def is_prime(num)
[*2..num-1].each do |i|
return false if num%i == 0
end
return true
end
However, when it is actually executed, the execution time of 200 digits of the base e of the natural logarithm is extremely long because it is honestly compared hundreds of thousands of times with one 10-digit number.
Is there any good way?
This can be solved by changing as follows.
def is_prime(num)
[*2..Math::sqrt(num).to_i+1].each do |i|
return false if num%i == 0
end
return true
end
All you have to do is rewrite num-1 to Math :: sqrt (num) .to_i + 1. This makes good use of the property of composite numbers, which are not prime numbers.
Its property is that composite number x has a prime factor p that satisfies p ≤ √x. To explain it in an easy-to-understand manner, if ** x is a composite number, it has a divisor of √x or less **. With this, he can only compare up to 1 million times, but only about 1000 times.
The combination of the above is as follows.
# coding: utf-8
def is_prime(num)
#When comparing one by one honestly
# [*2..num-1].each do |i|
#
[*2..Math::sqrt(num).to_i+1].each do |i|
return false if num%i == 0
end
return true
end
exp = File.read('exp.txt').delete("\n").delete(".")
[*0..exp.length-10].each do |i|
x_digits = exp[i..i+10-1].to_i
if is_prime(x_digits)
print("[", i,", ", x_digits,", true]")
break
end
end
When executed,
$ ruby google_recruit.rb
[99, 7427466391, true]
It was found that the 10-digit 7427466391 consecutive from the 99th digit is the first prime number.
In the comment, @ib \ _sis says From the viewpoint of speeding up processing, it may be better to skip if it is an even number. Thank you for pointing out .
I borrowed the code I received with me and measured the execution time. Using the Ruby standard library benchmark, the original completed program
# coding: utf-8
require 'benchmark'
result = Benchmark.realtime do
def is_prime(num)
#When comparing one by one honestly
# [*2..num-1].each do |i|
[*2..Math::sqrt(num).to_i+1].each do |i|
return false if num%i == 0
end
return true
end
exp = File.read('exp.txt').delete("\n").delete(".")
[*0..exp.length-10].each do |i|
x_digits = exp[i..i+10-1].to_i
if is_prime(x_digits)
print("[", i,", ", x_digits,", true]\n")
break
end
end
end
puts "Execution time: #{result}s"
If the number is even, skip it. The reorganized program
# coding: utf-8
require 'benchmark'
result = Benchmark.realtime do
def is_prime(num)
#When comparing one by one honestly
# [*2..num-1].each do |i|
[*2..Math::sqrt(num).to_i+1].each do |i|
return false if num%i == 0
end
return true
end
exp = File.read('exp.txt').delete("\n").delete(".")
[*0..exp.length-10].each do |i|
x_digits = exp[i..i+10-1].to_i
next if x_digits.even?
if is_prime(x_digits)
print("[", i,", ", x_digits,", true]\n")
break
end
end
end
puts "Execution time: #{result}s"
become that way.
As a result of execution
> ruby google_recruit-origin.rb
[99, 7427466391, true]
Execution time: 0.20240300009027123s
> ruby google_recruit-edit.rb
[99, 7427466391, true]
Execution time: 0.1098970000166446s
As expected, the execution time was cut in half. This saves a lot of time.
As a continuation of the previous problem,
f(1)=7182818284
f(2)=8182845904
f(3)=8747135266
f(4)=7427466391
f(5)=__________
The question is asked to find the number that fits in f (5). Let's consider this and execute it.
It doesn't seem to be a prime number or a perfect number. The common point is that they have 10 digits. Since it is a continuation of the Google Recruit Problem, I think that it is related to the number of Napier, and if you look at the decimal point of the number of Napier, you can see that f (1) = 7182818284 is the 1st to 10th decimal place of the decimal point. .. Looking at the continuation, f (2) is the 5th to 14th digits, f (3) is the 23rd to 32nd digits, and f (4) is the 99th to 108th digits. It was. It doesn't look like a sequence and has no clue.
When I was wondering if there were many 8s but it was related to even numbers or odd numbers, I discovered that the sum of 10 digits was 49.
To do this, create a method that finds 10 digits with the sum of each digit being 49, and incorporate it into the previous program. The created ones are as follows.
def is_49(num)
sum = 0
[*0..9].each do |i|
sum += num[i].to_i
end
return true if sum == 49
return false
end
exp = File.read('exp.txt').delete("\n").delete(".")
[*0..exp.length-10].each do |i|
x_digits = exp[i..i+10-1]
if is_49(x_digits)
print("[", i,"~", i+9,": ", x_digits,"]\n")
end
end
When executed
$ ruby google_recruit2.rb
[1~10: 7182818284]
[5~14: 8182845904]
[23~32: 8747135266]
[99~108: 7427466391]
[127~136: 5966290435]
[145~154: 2952605956]
It was found that there are 6 200-digit e (base of natural logarithm) in which the sum of 10 consecutive digits is 49, and ** f (5) = 5966290435 **.
Click here for the page I referred to this time.
Google recruit problem, exp and prime
[Ruby] File reading method summary
[Ruby] File reading process using frequently used File class
Thank you to @torifukukaiou for sending us an edit request for this post.
Also, it seems that he was challenged with the google recruitment problem in this post in a programming language called Elixir. You can jump to @ torifukukaiou's post below, so please have a look.
Try "Google Recruit" on Elixir
The first language I heard Elixir. Even if the description method is completely different, I'm really worried!