Introducción

En teoría de números, decimos que un número es $k$ suave cuando sus factores primos son como máximo . Por ejemplo, 2940 es 7-liso porque .$k$$2940=2^2\cdot3\cdot5\cdot7^2$

Aquí, definimos un par suave como dos enteros consecutivos que son suave. Un ejemplo de 7 pares suaves será porque 4374 = 2 \ cdot3 ^ 7 y 4375 = 5 ^ 4 \ cdot7 . Dato curioso: este es en realidad el mayor par de 7 suaves .$k$$k$$(4374,4375)$$4374=2\cdot3^7$$4375=5^4\cdot7$

Størmer demostró en 1897 que por cada , solo hay finitamente muchos pares suaves$k$$k$ , y este hecho se conoce como Teorema de Størmer .

Desafío

Su tarea es escribir un programa o función que, dado un número primo de entrada , emite o devuelve todos los pares suaves de sin duplicado (el orden dentro del par no importa) en el orden que desee.$k$$k$

Tenga en cuenta que para los números primos y q , suponiendo que p <q , todos los pares p- suaves también son pares q- suaves.$p$$q$$p<q$$p$$q$

Muestra de 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)

Restricción

El programa o función debería terminar teóricamente en tiempo finito para todas las entradas. Las lagunas estándar no están permitidas por defecto.

Criterios ganadores

Como se trata de un desafío de código de golf , gana la presentación válida más corta para cada idioma.

JavaScript (ES7),  234  232 bytes

Encuentra las soluciones resolviendo las ecuaciones de Pell de la forma $x^2-2qy^2=1$ , donde $q$ es un número libre de $P$ -cuadrado liso.

Esta es una implementación del procedimiento de Derrick Henry Lehmer , derivado del procedimiento original de Størmer.

Devuelve un objeto cuyas claves y valores describen los pares $P$ suaves.

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

Pruébalo en línea!

¿Cómo?

La función auxiliar $s$ prueba si un entero dado $n$ es un $P$ número suave cuando se llama con $i=0$ , o un número ¹ $P$ -smooth cuadrado libre cuando se llama con $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)

Buscamos todos los números lisos ¹ $P$ libres cuadrados en $[1..P^P-1]$ , donde$P^P$ se utiliza como límite superior para$P!$.

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

Para cada número $n$ encontrado anteriormente, buscamos la solución fundamental de la ecuación de Pell $x^2-ny^2=1$ :

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

(El código anterior es la versión no recursiva de mi respuesta a este otro desafío )

Una vez que se ha encontrado la solución fundamental $(x_1,y_1)$ , calculamos las soluciones $(x_k,y_k)$ con $k\le max(3,(P+1)/2)$ , utilizando las relaciones de recurrencia:

Para cada $x_k$ , probamos si $x_k$ es impar y ambos $(x_k-1)/2$ y $(x_k+1)/2$ son$P$ suaves. Si es así, los almacenamos en el objeto$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: Debido a que no prueba la primalidad de los divisores, la función $s$ realmente será verdadera para algunos números libres no cuadrados, incluso cuando se llama con $i=1$ . La idea es filtrar la mayoría de ellos para que no se resuelvan demasiadas ecuaciones de Pell inútiles.}

Jalea , 16 14 bytes

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

Pruébalo en línea!

Comprueba pares de hasta $4^k$ que es ineficiente para $k$ más grande, pero debe garantizar que no se pierda ninguno.

¡Gracias a @JonathanAllan por guardar 1 byte!

Explicación

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 bytes

°Lü‚ʒfà@

Pruébalo en línea!

Explicación:

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

Jalea , 123 bytes

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

Pruébalo en línea!

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

$k$

Haskell , 118107 bytes

-11 bytes gracias a 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)]

Pruébalo en línea!

• q n calcula una lista de todos los factores primos de n
• f k genera una lista de $k$-pares suaves para una k dada filtrando una lista de todos los pares

Jalea , 24 bytes

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

Pruébalo en línea!

Esto lleva mucho tiempo para 7, pero se calcula mucho más rápido si elimina la cuadratura del factorial: ¡ Pruébelo en línea!

Explicación:

³!²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 gracias a @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]

Pruébalo en línea!

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

Pruébalo en línea!

Dos variaciones en mi respuesta Jelly pero en Python 3. Ambas definen una función que acepta un argumento k. El primero devuelve una lista de tuplas de los pares que cumplen con los criterios. El segundo los imprime en stdout.

Wolfram Language (Mathematica) , 241 bytes

usa ecuaciones de 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@#&]])&

Pruébalo en línea!

Pyth , 15 bytes

f!>#QsPMTCtBS^4

Pruébalo en línea!

Utiliza la observación de Nick Kennedy de que ningún número de salida será mayor que 4^k.

05AB1E , 16 bytes

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

Pruébelo en línea (extremadamente ineficiente, así que agota el tiempo de espera para$n\gt3$..). Aquí una alternativa un poco más rápida , aunque todavía bastante lenta.

Explicación:

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

Ejecutar y depurarlo

Este no es el programa más corto posible, pero comienza a producir resultados tan pronto como se encuentran pares coincidentes. Finalmente termina , pero la salida se produce como se encuentra.

Ruby , 89 + 8 = 97 bytes

Usa la -rprimebandera. Para cada numero$i$ de 1 a $4^n$, mapear [i, i+1]si ambos son$n$-suave, de lo contrario mapearlo, falseluego podar todo falsede la lista.

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

Pruébalo en línea!