Tricky Aufgabe über geometrische Progression

Question

Gegeben zwei Zahlen l und r. Müssen die Länge der längsten geometrischen Progression finden, die aus einigen Zahlen zwischen l und r besteht - int-Zahlen im Intervall [l, r]. Beachten Sie, dass das Verhältnis der geometrischen Progression nicht ganzzahlig sein kann.

beispielsweise L = 11, r = 29. Die längste Sequenz 12 18 27 mit einem Verhältnis von 3/2 werden kann

Dank

Answer 1

r = q**(n - 1) * l Wir haben, das heißt r gleich das Verhältnis zu einer Potenz n - 1 mal l, wobei n die Anzahl der Begriffe in der Serie ist.

die Elemente der Progression Unter der Annahme, positive ganze Zahlen

Angenommen, wir haben eine feste l sein muss. Um Ganzzahlen zu erhalten, muss das Verhältnis eine rationale Zahl a/b (mit gcd(a, b) == 1) sein, so dass b ein Faktor von l ist.

Wenn b in l zu der Leistung k erscheint, dann kann die erforderliche Progression höchstens k Elemente haben. Die k+1 th wäre keine Ganzzahl, da sie keinen Faktor mehr von b hat.

Dann wählen wir a so minimal sein, dass a > b. Dies ist nur a = b+1. Das Verhältnis wird also immer (b + 1)/b sein.

Dies legt nahe, den folgenden Algorithmus für ein gegebenes l:

1. Die Teilern von l.

2. Für jede, d.

3. Finden Sie die Anzahl der möglichen Begriffe mit dem Verhältnis (d+1)/d. Da geometrische Progressionen schnell wachsen, können Sie wahrscheinlich mit einer einfachen Schleife while current <= r and term is integer davonkommen. Oder Sie können n wie so finden:

   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 
   

Aber bedenken Sie, dass Sie auch müssen berücksichtigen, wie viele Integer-Bedingungen dies generieren. Sie können dies tun, indem Sie die Stärke der einzelnen Primfaktoren in d verfolgen.

4. Wählen Sie diejenige aus, die die meisten Begriffe enthält.

Für 12 haben wir .

Für 2 haben wir das Verhältnis gleich (2+1)/2 = 3/2 und 3 Begriffe.

Für 3, haben wir Verhältnis gleich 4/3 und nur zwei Bedingungen: 12, 16 (nächste ganze Zahl würde nicht sein).

Für 4 haben wir das Verhältnis 5/4 und die Begriffe 12, 15.

Für 6 haben wir Verhältnis 7/6 und die Begriffe 12, 14.