introduction

Dans la théorie des nombres, nous disons qu'un nombre est $k$ lisse lorsque ses facteurs premiers sont tous au plus $k$ . Par exemple, 2940 est 7-lisse car $2940=2^2\cdot3\cdot5\cdot7^2$ .

Ici, nous définissons une paire $k$ lisse comme deux entiers consécutifs qui sont tous deux $k$ lisse. Un exemple de paire à 7 lisses sera $(4374,4375)$ car $4374=2\cdot3^7$ et $4375=5^4\cdot7$ . Fait amusant: il s'agit en fait de la plus grande paire de 7 lisses .

Størmer a prouvé en 1897 que pour chaque $k$ , il n'y a qu'un nombre fini de paires $k$ lisses , et ce fait est connu sous le nom de théorème de Størmer .

Défi

Votre tâche consiste à écrire un programme ou une fonction qui, étant donné un nombre premier entré $k$ , génère ou renvoie tous$k$génère k paires lisses sans doublon (l'ordre dans la paire n'a pas d'importance) dans l'ordre que vous souhaitez.

Veuillez noter que pour les nombres premiers $p$ et $q$ , en supposant que $p<q$ , toutes les paires $p$ lisses sont également des paires $q$ lisses.

Exemple d'E / S

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)

Restriction

Le programme ou la fonction devrait théoriquement se terminer en temps fini pour toutes les entrées. Les failles standard sont interdites par défaut.

Critères gagnants

Comme il s'agit d'un défi de code-golf , la soumission valide la plus courte pour chaque langue gagne.

JavaScript (ES7),  234  232 octets

Trouve les solutions en résolvant les équations de Pell de la forme $x^2-2qy^2=1$ , où $q$ est un nombre libre carré $P$ lisse.

Il s'agit d'une implémentation de la procédure de Derrick Henry Lehmer , dérivée de la procédure originale de Størmer.

Renvoie un objet dont les clés et les valeurs décrivent les paires $P$ -mooth.

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

Essayez-le en ligne!

Comment?

La fonction d'assistance $s$ teste si un entier donné $n$ est un nombre lisse $P$ lorsqu'il est appelé avec $i=0$ , ou un nombre lisse ¹ $P$ carré lorsqu'il est appelé avec $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)

Nous recherchons tous les nombres sans carré ¹ $P$ libres dans $[1..P^P-1]$ , où $P^P$ est utilisé comme limite supérieure pour $P!$.

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

Pour chaque nombre $n$ trouvé ci-dessus, nous recherchons la solution fondamentale de l'équation de Pell $x^2-ny^2=1$ :

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

(le code ci-dessus est la version non récursive de ma réponse à cet autre défi )

Une fois la solution fondamentale $(x_1,y_1)$ trouvée, nous calculons les solutions $(x_k,y_k)$ avec $k\le max(3,(P+1)/2)$ , en utilisant les relations de récurrence:

Pour chaque $x_k$ , nous testons si $x_k$ est impair et les deux $(x_k-1)/2$ et $(x_k+1)/2$ sont $P$ lisses. Si c'est le cas, nous les stockons dans l'objet $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: Parce qu'elle ne teste pas la primauté des diviseurs, la fonction $s$ sera en fait vraie pour certains nombres libres non carrés, même lorsqu'elle est appelée avec $i=1$ . L'idée est de filtrer la plupart d'entre elles afin de ne pas résoudre trop d'équations de Pell inutiles.}

Gelée , 16 14 octets

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

Essayez-le en ligne!

Vérifie les paires jusqu'à $4^k$ ce qui est inefficace pour les k plus grands$k$ mais devrait s'assurer qu'aucune ne soit manquée.

Merci à @JonathanAllan d'avoir économisé 1 octet!

Explication

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 octets

°Lü‚ʒfà@

Essayez-le en ligne!

Explication:

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

Gelée , 123 octets

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

Essayez-le en ligne!

Ceci est une réponse Jelly relativement efficace mais longue qui utilise la méthode des fractions continues pour résoudre la solution fondamentale des équations de Pell pour $2×$ chaque nombre sans carré k-lisse, trouve $\max(3, \frac{k+1}{2})$ solutions pour chacun, puis vérifie si $\frac{x-1}{2}, \frac{x+1}{2}$ are smooth for each solution. This is Lehmer’s method, as described in the question’s Wikipedia link.

A full program that takes a single argument, $k$ and returns a list of lists of pairs. The code above doesn’t sort the final output, but the TIO link does.

Haskell, 118 107 bytes

-11 bytes thanks to 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)]

Try it online!

• q n calculates a list of all prime factors of n
• f k generates a list of $k$-smooth pairs for a given k by filtering a list of all pairs

Jelly, 24 bytes

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

Try it online!

This takes a long time for 7, but it computes much faster if you remove the squaring of the factorial: Try it online!

Explanation:

³!²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 thanks to @JonathanAllen

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]

Try it 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

Try it online!

Two variations on my Jelly answer but in Python 3. They both define a function which accepts an argument k. The first returns a list of tuples of the pairs that meet the criteria. The second prints them to stdout.

Wolfram Language (Mathematica), 241 bytes

uses Pell equations

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

Try it online!

Pyth, 15 bytes

f!>#QsPMTCtBS^4

Try it online!

Uses Nick Kennedy's observation that no output number will be larger than 4^k.

05AB1E, 16 bytes

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

Try it online (extremely inefficient, so times out for $n\gt3$..). Here a slightly faster alternative, although still pretty slow..

Explanation:

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

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

Run and debug it

This is not the shortest possible program, but it begins producing output as soon as matching pairs are found. It does terminate eventually, but output is produced as it's found.

Ruby, 89+8 = 97 bytes

Uses the -rprime flag. For each number $i$ from 1 to $4^n$, map it to [i, i+1] if both are $n$-smooth, otherwise map it to false, then prune all false from the list.

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

Try it online!