Wprowadzenie

W teorii liczb mówimy, że liczba jest gładka, gdy wszystkie jej czynniki pierwsze wynoszą co najwyżej . Na przykład 2940 jest 7-gładki, ponieważ .$k$$k$$2940=2^2\cdot3\cdot5\cdot7^2$

Tutaj definiujemy parę smooth jako dwie kolejne liczby całkowite, z których obie są smooth. Przykładem 7-gładkiej pary będzie ponieważ i . Ciekawostka: to właściwie największa 7-gładka para .$k$$k$$(4374,4375)$$4374=2\cdot3^7$$4375=5^4\cdot7$

Størmer udowodnił w 1897 r., Że dla każdego istnieje tylko skończenie wiele par gładkich$k$$k$ , a fakt ten znany jest jako Twierdzenie Størmera .

Wyzwanie

Twoim zadaniem jest napisanie programu lub funkcji, która, biorąc pod uwagę liczbę podstawową , wypisuje lub zwraca wszystkie pary gładkich bez duplikowania (kolejność w parze nie ma znaczenia) w dowolnej kolejności.$k$$k$

Należy zauważyć, że dla liczb pierwszych i , przy założeniu, że , wszystkie pary gładkie są również parami gładkimi.$p$$q$$p<q$$p$$q$

Próbki we / wy

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)

Ograniczenie

Program lub funkcja powinny teoretycznie zakończyć się w skończonym czasie dla wszystkich danych wejściowych. Standardowe luki są domyślnie niedozwolone.

Zwycięskie kryteria

Ponieważ jest to wyzwanie związane z golfem , wygrywa najkrótszy ważny zgłoszenie dla każdego języka.

JavaScript (ES7),  234  232 bajty

Znajduje rozwiązania, rozwiązując równania Pell w postaci , gdzie jest liczbą gładką kwadratową.$x^2-2qy^2=1$$q$$P$

Jest to implementacja procedury Derricka Henry'ego Lehmera , wywodząca się z oryginalnej procedury Størmera.

Zwraca obiekt, którego klucze i wartości opisują pary gładkie.$P$

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

Wypróbuj online!

W jaki sposób?

W funkcji pomocnika sprawdza, czy dany całkowita jest liczba -smooth gdy jest wywołana , lub kwadratowy wolny ¹ liczba -smooth gdy jest wywoływana z .$s$$n$$P$$i=0$P i = 1 $P$$i=1$

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

Szukamy wszystkich wolnych od kwadratów liczb ¹ gładkich w , gdzie jest używane jako górna granica dla.$P$$[1..P^P-1]$$P^P$$P!$

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

Dla każdej liczby znalezionej powyżej szukamy podstawowego rozwiązania równania Pell :$n$$x^2-ny^2=1$

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

(powyższy kod jest nierekurencyjną wersją mojej odpowiedzi na to inne wyzwanie )

Po znalezieniu podstawowego rozwiązania obliczamy rozwiązania pomocą , używając relacji powtarzalności:$(x_1,y_1)$$(x_k,y_k)$$k\le max(3,(P+1)/2)$

Dla każdego sprawdzamy, czy jest nieparzyste i oba i są gładkie. Jeśli tak, przechowujemy je w obiekcie .$x_k$$x_k$$(x_k-1)/2$$(x_k+1)/2$$P$$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: Ponieważ nie testuje pierwotności dzielników, funkcja będzie faktycznie prawdziwa dla niektórych niekwadratowych liczb swobodnych, nawet jeśli zostanie wywołana z . Chodzi o to, aby odfiltrować większość z nich, aby rozwiązać zbyt wiele bezużytecznych równań Pell.$s$$i=1$}

Galaretka , 16 14 bajtów

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

Wypróbuj online!

Sprawdza pary do co jest nieefektywne dla większych ale powinno zapewnić, że żadna nie zostanie pominięta.$4^k$$k$

Dzięki @JonathanAllan za uratowanie 1 bajtu!

Wyjaśnienie

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)

05AB1E , 8 bajtów

°Lü‚ʒfà@

Wypróbuj online!

Wyjaśnienie:

°            # 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

Galaretka , 123 bajty

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

Wypróbuj online!

$2×$$\max(3, \frac{k+1}{2})$$\frac{x-1}{2}, \frac{x+1}{2}$

Pełny program, który pobiera pojedynczy argument, i zwraca listę list par. Powyższy kod nie sortuje ostatecznego wyniku, ale robi to łącze TIO.$k$

Haskell , 118 107 bajtów

-11 bajtów dzięki nim

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)]

Wypróbuj online!

• q n oblicza listę wszystkich czynników pierwszych n
• f kgeneruje listę par gładkich dla danego k, filtrując listę wszystkich par$k$

Galaretka , 24 bajty

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

Wypróbuj online!

Zajmuje to dużo czasu dla 7, ale oblicza się znacznie szybciej, jeśli usuniesz kwadrat silni: Wypróbuj online!

Wyjaśnienie:

³!²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 bajty dzięki @JonathanAllen

Python 3 + sympy, 116 bajtów

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]

Wypróbuj online!

Python 3 + sympy, 111 bajtów

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

Wypróbuj online!

Dwie odmiany mojej odpowiedzi na żelki, ale w Pythonie 3. Obie definiują funkcję, która przyjmuje argument k. Pierwszy zwraca listę krotek par, które spełniają kryteria. Drugi drukuje je na standardowe wyjście.

Wolfram Language (Mathematica) , 241 bajtów

używa równań Pell

(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@#&]])&

Wypróbuj online!

Pyth , 15 bajtów

f!>#QsPMTCtBS^4

Wypróbuj online!

Wykorzystuje obserwację Nicka Kennedy'ego, że żadna liczba wyjściowa nie będzie większa niż 4^k.

05AB1E , 16 bajtów

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

$n\gt3$

Wyjaśnienie:

°                # 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

Stax , 14 bajtów

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

Uruchom i debuguj

To nie jest najkrótszy możliwy program, ale zaczyna generować dane wyjściowe, gdy tylko zostaną znalezione pasujące pary. Kończy się ostatecznie , ale dane wyjściowe są wytwarzane w miarę ich znajdowania.

Rubinowy , 89 + 8 = 97 bajtów

-rprime$i$$4^n$[i, i+1]$n$falsefalse

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

Wypróbuj online!