Project Euler #368 (Math Formula) [closed]

Question

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 9 years ago.

Improve this question

In Project Euler, a problem asks me to write a program to find the convergence value of 20 terms from the Harmonic sequence:

1/111, 1/222, 1/333, 1/444, 1/555, 1/666, 1/777, 1/888, 1/999, 1/1000, 1/1110, 1/1111, 1/1112, 1/1113, 1/1114, 1/1115, 1/1116, 1/1117, 1/1118, and 1/1119

I want to write the program myself to solve the problem, however, not having dealt with Calc II, I had to read up on Divergence/Convergence. All the explanations deal with series that can be represented by a formula. This series, as far as I can tell, cannot.

So, the question is:

Is there a formula to represent this series or is there a method for finding the convergence of this series without a formula?

Answer 1

If you read the problem carefully you will notice that there is in fact a formula. The sequence you're dealing with is a harmonic series, from which terms having 3 or more equal consecutive digits have been removed. Brute force approach here would be to sum all terms of harmonic series omitting those specified until required precision is reached. Ruby with its Rational class seems really fine candidate to that.

Answer 2

Just in case anybody considers brute-forcing it:

The brute force approach will here, as in most high-numbered Project Euler problems, not finish within reasonable time.

Suppose your computer could handle 10⁹ numbers per second (it can handle far fewer, actually). To sum the valid terms up to 10ⁿ for n > 9 would take about 10^n-9 seconds.

How far would you have to go to determine the sum to ten places after the decimal point?

Far enough that the sum of all larger valid terms is less than 10^-10. Will 10¹² be far enough? No. Consider the next thousand numbers from

1001001001001

The invalid numbers among them are

1001001001110
1001001001111
1001001001112
...
1001001001119
1001001001222
1001001001333
1001001001444
...
1001001001999
1001001002000

Those are 19, so there are 981 valid numbers and the corresponding sum is larger than 981/1001001002000, which is more than 9*10^-10. A bit of further reasoning along those lines shows that you would have to brute force much higher than 10¹⁵ - in fact, you would have to go beyond 10²⁰⁰⁰ before the sum of the remaining valid terms becomes less than 10^-10.

A brute force started at the beginning of the universe would not be even remotely near a reliable answer yet.

Answer 3

The naive and brute force approach for this problem would be to write a loop iterating over the denominator of the series and adding the inverse of the denominator to a overall sum given it is not excluded by the restrictions stated in the problem description.

The outline would be similar to this:

for i in (1..1200)
  if is_valid(i) then
    sum += 1.0 / i
  end
end

def is_valid(_i)
  # implement the check here. hint: use modulo operator ;-)
end