幾何学的進行についての厄介な作業

Question

与えられた2つの数字lとr。区間[l、r]のlとr - int間のいくつかの数からなる最も長い幾何学的な進行の長さを見つける必要がある。 幾何学的な進行の比は非整数であってもよいことに注意してください。

例えば、L = 11、R = 29、最長シーケンスは比で12 18 27であることができるが3/2

おかげ

Answer 1

我々はr = q**(n - 1) * lを持って、それはrあるいくつかのパワーとの比に等しいです。 n - 1 times lここで、nはシリーズ内の用語の数です。正の整数

でなければならない進行の要素を仮定し

たちは、固定lを持っていると仮定します。整数を得るためには、比率はa/b（gcd(a, b) == 1）となるようにbがlのファクタでなければなりません。

bがkのlに表示される場合、必要なプログレスバーは最大でk個の要素を持つことができます。 k+1 thは整数ではなく、bの係数を持たないためです。

次に、a > bとなるようにaを最小にすることを選択します。これはちょうどa = b+1です。したがって、比率は常に(b + 1)/bになります。

1. がlの約数を探す：

   これは、与えられたlのための以下のアルゴリズムを提案しています。

2. それぞれについて、d。

3. (d+1)/dに等しい比率で可能な用語の数を求めます。幾何学的な進展が速くなるので、単純なループwhile current <= r and term is integerで逃げることができます。それとも、そのようなn見つけることができます：

   r = q**(n - 1) * l 
   r/l = q**(n - 1) 
   n - 1 = log base q of (r/l) 
   n = int(log base q of (r/l)) + 1 
   

をしかし、あなたはまた、これが生成されますどのように多くの整数条件を考慮しなければならないことに注意してください。それぞれの素因数が表示される力を、dに記録することで、これを行うことができます。

4. ほとんどの用語を示すものを選択します。

12については、12 = 2**2 * 3です。

2については、(2+1)/2 = 3/2と3という語句の比率があります。

3の場合、比率は4/3になり、2つの語句：12, 16（次は整数ではありません）があります。

4については、5/4の比率と12, 15の比率があります。

6の場合、私たちは7/6に等しい比率と12, 14という比率を持っています。