Finde alle

13

Einführung

In der Zahlentheorie sagen wir, dass eine Zahl k glatt ist, wenn ihre Primfaktoren alle höchstens k . Zum Beispiel ist 2940 7-glatt, weil 2940=223572 .

Hier definieren wir ein k glattes Paar als zwei aufeinanderfolgende ganze Zahlen, die beide k glatt sind. Ein Beispiel von 7-Paar glatter wird (4374,4375) , weil 4374=237 und 4375=547 . Lustige Tatsache: Dies ist tatsächlich das größte 7-Smooth-Paar .

Størmer bewies 1897, dass es für jedes k nur endlich viele k glatte Paare gibt , und diese Tatsache ist als Satz von Størmer bekannt .

Herausforderung

Ihre Aufgabe ist es, ein Programm oder eine Funktion zu schreiben, die bei gegebener Primzahleingabe k alle k glatten Paare ohne Duplikat (Reihenfolge innerhalb des Paares ist egal) in beliebiger Reihenfolge ausgibt oder zurückgibt .

Bitte beachten Sie, dass für die Primzahlen p und q unter der Annahme von p<q alle p glatten Paare auch q glatte Paare sind.

Beispiel-E / A

Input: 2
Output: (1, 2)

Input: 3
Output: (1, 2), (2, 3), (3, 4), (8, 9)

Input: 5
Output: (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (8, 9), (9, 10), (15, 16), (24, 25), (80, 81)

Input: 7
Output: (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9), (9, 10), (14, 15),
        (15, 16), (20, 21), (24, 25), (27, 28), (35, 36), (48, 49), (49, 50), (63, 64),
        (80, 81), (125, 126), (224, 225), (2400, 2401), (4374, 4375)

Beschränkung

Das Programm oder die Funktion sollte theoretisch für alle Eingaben in endlicher Zeit enden. Standardlücken sind standardmäßig nicht zulässig.

Gewinnkriterien

Da dies eine Herausforderung ist, gewinnt die kürzeste gültige Einsendung für jede Sprache.

Shieru Asakoto
quelle
2
Könnten Sie bitte Testfälle für 2, 3 und 5 hinzufügen?
Jonathan Allan
@ JonathanAllan 2-, 3- und 5-glatte Paare sind in den 7-glatten Paaren enthalten, aber ich werde die Fälle aus Gründen der Klarheit hinzufügen
Shieru Asakoto
1
Ist ein (1, 2)Teil der Ausgabe obligatorisch? ..
Kevin Cruijssen
@ KevinCruijssen Ja, alle Ausgänge sollten das (1, 2)Paar enthalten .
Shieru Asakoto

Antworten:

10

JavaScript (ES7),  234  232 Byte

Findet die Lösungen durch Lösen von Pell-Gleichungen der Form x22qy2=1 , wobei q eine P glatte quadratfreie Zahl ist.

Dies ist eine Implementierung des Verfahrens von Derrick Henry Lehmer , abgeleitet von Størmers ursprünglichem Verfahren.

Gibt ein Objekt zurück, dessen Schlüssel und Werte die P glatten Paare beschreiben.

P=>[...Array(P**P)].map((_,n)=>(s=(n,i=0,k=2)=>k>P?n<2:n%k?s(n,i,k+1):s(n/k,i,k+i))(n,1)&&(_=>{for(x=1;(y=((++x*x-1)/n)**.5)%1;);(h=(x,y)=>k--&&h(X*x+n*Y*y,X*y+Y*x,x&s(x=~-x/2)&s(x+1)?r[x]=x+1:0))(X=x,Y=y,k=P<5?3:-~P/2)})(),r={})&&r

Probieren Sie es online!

Wie?

Die Hilfsfunktion s testet, ob eine gegebene Ganzzahl n eine P glatte Zahl ist, wenn sie mit i=0 aufgerufen wird , oder eine quadratfreie 1 P glatte Zahl, wenn sie mit i=1 aufgerufen wird .

s = (
  n,
  i = 0,
  k = 2
) =>
  k > P ?
    n < 2
  :
    n % k ?
      s(n, i, k + 1)
    :
      s(n / k, i, k + i)

Wir suchen nach allen quadratfreien 1 P -glatten Zahlen in [1 ..PP-1] , wobei PP als Obergrenze für P!.

P=>[...Array(P ** P)].map((_, n) => s(n, 1) && (...))

Für jede oben gefundene Zahl n suchen wir nach der fundamentalen Lösung der Pell-Gleichung x2-ny2=1 :

(_ => {
  for(x = 1; (y = ((++x * x - 1) / n) ** .5) % 1;);
  ...
})()

(Der obige Code ist die nicht-rekursive Version meiner Antwort auf diese andere Herausforderung. )

Sobald die fundamentale Lösung (x1,y1) gefunden wurde, berechnen wir die Lösungen (xk,yk) mit kmax(3,(P+1)/2) unter Verwendung der Wiederholungsrelationen:

xk+1=x1xk+ny1ykyk+1=x1yk+y1xk

Für jedes xk testen wir , ob xk ungerade ist, und beide (xk1)/2 und (xk+1)/2 sind P -Glatte. Wenn ja, speichern wir sie im Objekt r .

( h = (x, y) =>
  k-- &&
  h(
    X * x + n * Y * y,
    X * y + Y * x,
    x &
    s(x = ~-x / 2) &
    s(x + 1) ?
      r[x] = x + 1
    :
      0
  )
)(X = x, Y = y, k = P < 5 ? 3 : -~P / 2)

1: Da die Primalität der Divisoren nicht getestet wird, ist die Funktion s für einige nicht-quadratische freie Zahlen sogar dann wahr, wenn sie mit i=1 aufgerufen wird . Die Idee ist, die meisten von ihnen herauszufiltern, damit nicht zu viele nutzlose Pell-Gleichungen gelöst werden.

Arnauld
quelle
Hallo Arnauld! Ich konnte einfach nicht meinen Kopf um diese beiden wickeln: x = ~-x / 2und ... -~P / 2Sind das eine Art Rundung ...
Rahul Verma
1
@ rv7 ~xist ein bitweises NOT, das rechnet -(x+1). Deshalb ~-xist -(-x+1)= x-1und -~xist -(-(x+1))= x+1. Wie bei allen bitweisen Operationen in JS wird nur der 32-Bit-Integer-Teil berücksichtigt. Sie können also tatsächlich zum Runden verwendet werden. Aber sowohl als auch P sind hier bereits ganze Zahlen. xP
Arnauld
4

Jelly , 16 bis 14 Bytes

4*ÆfṀ<ɗƇ‘rƝLÐṂ

Probieren Sie es online!

Prüft auf Paare bis zu 4k was für größere k ineffizient ist, aber sicherstellen sollte, dass keine übersehen werden.

Vielen Dank an @ JonathanAllan für das Speichern von 1 Byte!

Erläuterung

4*ÆfṀ<ɗƇ‘rƝLÐṂ  | Monadic link, input k

4*              | 4**k, call this n
      ɗƇ        | For each number from 1..n filter those where:
  Æf            |   - Prime factors
    Ṁ           |   - Maximum
     <  ‘       |   - Less than k+1
         rƝ     | Inclusive range between neighbouring values
           LÐṂ  | Keep only those of minimum length (i.e. adjacent values)
Nick Kennedy
quelle
1
4kk!24k
1
Danke für die schnelle Antwort. Ich dachte ähnlich, aber allgemeiner: "Fakultät wird ziemlich schnell hoch, es ist wahrscheinlich groß genug." (Es stellte sich heraus, dass es nicht war, es sei denn, ich habe es quadriert). Herzlichen Glückwunsch zum kürzeren und effizienteren Golf, Sie haben meine Zustimmung.
Genosse SparklePony
1
Anmerkung (von oeis.org/A002072 ) "a (n) <10 ^ n / n mit Ausnahme von n = 4. (Vermutlich aus experimentellen Daten.) - MF Hasler, 16. Januar 2015". Ich denke, wir müssen bei der schwachen Grenze von Lehmer in projecteuclid.org/download/pdf_1/euclid.ijm/1256067456 (Satz 7) bleiben, sofern wir nichts anderes beweisen können.
Jonathan Allan
2
... da ist eine offene Frage zu Mathematics SE , die genau das auch fragt!
Jonathan Allan
1
@ PeterTaylor, das ist für die Anzahl der Paare, nicht die maximale Anzahl. Das Problem ist, dass Sie nicht aufhören können, nach einer Grenze für die maximale Anzahl von Paaren zu suchen
Nick Kennedy,
3

05AB1E , 8 Bytes

°Lü‚ʒfà@

Probieren Sie es online!

Erläuterung:

°            # 10 ** the input
 Lü‚         # list of pairs up to that number
    ʒ        # filtered by...
     fà      # the greatest prime factor (of either element of the pair)...
       @     # is <= the input
Grimmig
quelle
2

Jelly , 123 Bytes

¹©Æ½Ø.;µU×_ƭ/;²®_$÷2ị$}ʋ¥⁸;+®Æ½W¤:/$$µƬṪ€F¹;Ḋ$LḂ$?ṭ@ṫ-ṚZæ.ʋ¥ƒØ.,U¤-ịWµ1ịżU×®W¤Ɗ$æ.0ị$ṭµ³’H»3¤¡
ÆRŒPP€ḟ2ḤÇ€ẎḢ€+€Ø-HÆfṀ€<ẠʋƇ‘

Probieren Sie es online!

Dies ist eine relativ effiziente, aber lange Gelee-Antwort, die die Methode der fortgesetzten Brüche verwendet, um die grundlegende Lösung für die Pell-Gleichungen für zu lösen 2× jede k-glatte quadratfreie Zahl findet max(3,k+12) lösungen für jeden und prüft dann ob x-12,x+12sind für jede Lösung glatt. Dies ist Lehmers Methode, wie im Wikipedia-Link der Frage beschrieben .

Ein vollständiges Programm, das ein einziges Argument benötigt, kund gibt eine Liste mit Listen von Paaren zurück. Der obige Code sortiert die endgültige Ausgabe nicht, der TIO-Link jedoch.

Nick Kennedy
quelle
2

Haskell , 118 107 Bytes

-11 bytes dank nimi

q 1=[1]
q n=(:)<*>q.div n$[x|x<-[2..n],mod n x==0]!!0
f k|let r=all(<=k).q=[(n,n+1)|n<-[1..4^k],r n,r(n+1)]

Probieren Sie es online!

  • q n berechnet eine Liste aller Primfaktoren von n
  • f k generiert eine Liste von k-glatte Paare für ein gegebenes k durch Filtern einer Liste aller Paare
Max Yekhlakov
quelle
1
Sie können eine Schleife durch [2..n]innerhalb pund Inline es in q. Probieren Sie es online!
nimi
1

Gelee , 24 Bytes

³!²R‘Ė
ÇÆFḢ€€€’<³FȦ$€Tị¢

Probieren Sie es online!

Für 7 dauert dies lange, aber es wird viel schneller berechnet, wenn Sie die Quadratur der Fakultät entfernen: Probieren Sie es online aus!

Erläuterung:

³!²R‘Ė                Generates a list like [[1,2],[2,3],...]
³!²                  Take the square of the factorial of the input
   R                 Range 1 through through the above number.
    ‘Ė               Decrement and enumerate, yielding desired list


ÇÆFḢ€€€’<³FȦ$€Tị¢  
Ç                    Get the list of pairs  
 ÆF                  Get the prime factors of each number
   Ḣ€€€              Get the base of each
       ’<³           Is each base less than or equal to the input?
          FȦ$€       Check that all bases of a pair fit the above.
              T      Get a list of the truthy indexes
               ị¢    Index into the original list of pairs
                     Implicit output

-3 Bytes dank @JonathanAllen

Genosse SparklePony
quelle
1
Ich lese kein Gelee, kannst du eine Erklärung geben, wie das funktioniert?
Verkörperung der Ignoranz
Ich glaube nicht, dass das funktioniert - (8,9)seitdem ist es kein 3-Smooth-Paar8=23 und 9=32?
Jonathan Allan
Ich bin mir aber nicht sicher, ob es so ist. Was lässt Sie denken, dass das halten wird?
Jonathan Allan
@ JonathanAllan Naiver Optimismus und die Tatsache, dass für alle Beispiele, die ich gesehen habe (zugegebenermaßen nicht viele), das größte Paar kleiner ist als k!(mit Ausnahme von 3, das eine kleine Fakultät hat, weil es eine kleine Zahl ist).
Genosse SparklePony
1
Die Obergrenze, die Sie verwenden, ist die maximale Anzahl, die in einem Paar verwendet wird, nicht die Anzahl der Paare (Sie können auf diese Weise keine Obergrenze für die Anzahl der Paare implementieren, da Sie nicht wissen, wann Sie aufhören müssen zu suchen!). Siehe Satz 7 für eine obere Schranke für das Produkt des größten Paares.
Jonathan Allan
1

Python 3 + Sympy, 116 Bytes

import sympy
def f(k):x=[i for i in range(2,4**k)if max(sympy.factorint(i))<=k];return[(y,y+1)for y in x if y+1in x]

Probieren Sie es online!

Python 3 + Sympy, 111 Bytes

from sympy import*
def f(k):
 b=1
 for i in range(2,4**k):
  x=max(factorint(i))<=k
  if x&b:print(i-1,i)
  b=x

Probieren Sie es online!

Zwei Variationen meiner Jelly-Antwort, aber in Python 3. Beide definieren eine Funktion, die ein Argument akzeptiert k. Die erste gibt eine Liste von Tupeln der Paare zurück, die die Kriterien erfüllen. Die Sekunde druckt sie zu stdout.

Nick Kennedy
quelle
1

Wolfram Language (Mathematica) , 241 Byte

verwendet Pell-Gleichungen

(s=#;v@a_:=Max[#&@@@#&/@FactorInteger@a]<=s;Select[{#-1,#+1}/2&/@(t={};k=y=1;While[k<=Max[3,(s+1)/2],If[IntegerQ[x=Sqrt[1+2y^2#]],t~AppendTo~x;k++];y++];t),v@#&]&/@Join[{1},Select[Range[3,Times@@Prime@Range@PrimePi@s],SquareFreeQ@#&&v@#&]])&

Probieren Sie es online!

J42161217
quelle
1

05AB1E , 16 Bytes

°LʒfàI>‹}Xšü‚ʒ¥`

Probieren Sie es online aus (extrem ineffizient, also zögern Sie nichtn>3..). Hier eine etwas schnellere Alternative , wenn auch noch ziemlich langsam.

Erläuterung:

°                # Take 10 to the power of the (implicit) input
 L               # Create a list in the range [1, 10^input]
  ʒ              # Filter this list by:
   fà            #  Get the maximum prime factor
     I>‹         #  And check if it's smaller than or equal to the input
        }Xš      # After the filter: prepend 1 again
           ü‚    # Create pairs
             ʒ   # And filter these pairs by:
              ¥` #  Where the forward difference / delta is 1
Kevin Cruijssen
quelle
0

Stax , 14 Bytes

Θ",²aÇu,á‼⌐çLB

Führen Sie es aus, und debuggen Sie es

Dies ist nicht das kürzestmögliche Programm, es wird jedoch ausgegeben, sobald passende Paare gefunden wurden. Es wird schließlich beendet , aber die Ausgabe wird so erstellt, wie sie gefunden wurde.

rekursiv
quelle
0

Ruby , 89 + 8 = 97 Bytes

Verwendet die -rprimeFlagge. Für jede Nummerich von 1 bis 4n, ordnen Sie es zu, [i, i+1]wenn beide sindn-smooth, ordne es ansonsten zu falseund entferne dann alle falseaus der Liste.

->n{g=->x{x.prime_division.all?{|b,_|b<=n}};(1..4**n).map{|i|g[i]&&g[i+1]&&[i,i+1]}-[!1]}

Probieren Sie es online!

Wert Tinte
quelle