Introdução

Na teoria dos números, dizemos que um número é $k$ suave quando seus fatores primos são todos no máximo $k$ . Por exemplo, 2940 é 7 suave porque $2940=2^2\cdot3\cdot5\cdot7^2$ .

Aqui, definimos um par $k$ smooth como dois números inteiros consecutivos que são $k$ smooth. Um exemplo de par suave de 7 será $(4374,4375)$ porque $4374=2\cdot3^7$ e $4375=5^4\cdot7$ . Curiosidade: Este é realmente o maior par de 7 pares .

Størmer provou em 1897 que, para cada $k$ , existem apenas finitos pares $k$ suaves , e esse fato é conhecido como Teorema de Størmer .

Desafio

Sua tarefa é escrever um programa ou função que, dado um número primo, insira $k$ , produza ou retorne todos os pares $k$ smooth sem duplicação (a ordem dentro do par não importa) na ordem que você desejar.

Observe que, para os números primos $p$ e $q$ , assumindo $p<q$ , todos os pares $p$ suave são também pares $q$ suaves.

E / S de amostra

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)

Restrição

O programa ou função deve terminar teoricamente em tempo finito para todas as entradas. As brechas padrão não são permitidas por padrão.

Critérios Vencedores

Como se trata de um desafio de código-golfe , o menor envio válido para cada idioma vence.

JavaScript (ES7),  234  232 bytes

Encontre as soluções resolvendo as equações de Pell da forma $x^2-2qy^2=1$ , onde $q$ é um número livre de quadrados $P$ liso.

Esta é uma implementação do procedimento de Derrick Henry Lehmer , derivado do procedimento original de Størmer.

Retorna um objeto cujas chaves e valores descrevem os 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

Experimente online!

Quão?

A função auxiliar $s$ testa se um número inteiro $n$ é um número $P$ suave quando é chamado com $i=0$ ou um número ¹ $P$ suave sem quadrados quando é chamado com $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)

Procuramos todos os números quadrados suaves de ¹ $P$ livres em $[1..P^P-1]$ , onde $P^P$ é usado como limite superior para $P!$.

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

Para cada número $n$ encontrado acima, procuramos a solução fundamental da equação de Pell $x^2-ny^2=1$ :

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

(o código acima é a versão não recursiva da minha resposta para esse outro desafio )

Uma vez encontrada a solução fundamental $(x_1,y_1)$ , calculamos as soluções $(x_k,y_k)$ com $k\le max(3,(P+1)/2)$ , usando as relações de recorrência:

Para cada $x_k$ , testamos se $x_k$ é ímpar e ambos $(x_k-1)/2$ e $(x_k+1)/2$ são $P$ suaves. Nesse caso, nós os armazenamos no 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: Como ela não testa a primalidade dos divisores, a função $s$ será verdadeira para alguns números livres não quadrados, mesmo quando for chamada com $i=1$ . A idéia é filtrar a maioria deles para que não sejam resolvidas muitas equações inúteis de Pell.}

Geléia , 16 14 bytes

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

Experimente online!

Verifica pares de até $4^k$ que é ineficiente para $k$ maior, mas deve garantir que nada seja perdido.

Obrigado a @ Jonathanon Allan por economizar 1 byte!

Explicação

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à@

Experimente online!

Explicação:

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

Gelatina , 123 bytes

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

Experimente online!

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

$k$

Haskell , 118 107 bytes

-11 bytes graças 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)]

Experimente online!

• q n calcula uma lista de todos os principais fatores de n
• f k$k$

Gelatina , 24 bytes

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

Experimente online!

Isso leva muito tempo para 7, mas computa muito mais rápido se você remover o quadrado do fatorial: Experimente online!

Explicação:

³!²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 graças 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]

Experimente 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

Experimente online!

Duas variações na minha resposta Jelly, mas no Python 3. Ambas definem uma função que aceita um argumento k. O primeiro retorna uma lista de tuplas dos pares que atendem aos critérios. O segundo os imprime em stdout.

Wolfram Language (Mathematica) , 241 bytes

usa equações 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@#&]])&

Experimente online!

Pitão , 15 bytes

f!>#QsPMTCtBS^4

Experimente online!

Usa a observação de Nick Kennedy de que nenhum número de saída será maior que 4^k.

05AB1E , 16 bytes

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

$n\gt3$ , embora ainda muito lenta ..

Explicação:

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

Execute e depure

Este não é o programa mais curto possível, mas começa a produzir resultados assim que os pares correspondentes são encontrados. Ele termina eventualmente , mas a saída é produzida como encontrada.

Ruby , 89 + 8 = 97 bytes

Usa a -rprimebandeira. Para cada número$i$ de 1 a $4^n$, mapeie-o para [i, i+1]se ambos estiverem$n$-smooth, caso contrário mapeie-o e false, em seguida, remova tudo falseda 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]}

Experimente online!