pengantar

Dalam teori bilangan, kita katakan bilangan adalah $k$ halus ketika faktor utamanya paling banyak $k$ . Misalnya, 2940 adalah 7-halus karena $2940=2^2\cdot3\cdot5\cdot7^2$ .

Di sini, kita mendefinisikan pasangan $k$ -smooth sebagai dua bilangan bulat berturut-turut yang keduanya $k$ -smooth. Contoh dari pasangan 7-halus akan $(4374,4375)$ karena $4374=2\cdot3^7$ dan $4375=5^4\cdot7$ . Fakta menyenangkan: Ini sebenarnya adalah pasangan 7-halus terbesar .

Størmer membuktikan pada tahun 1897 bahwa untuk setiap $k$ , hanya ada banyak pasangan $k$ -smooth , dan fakta ini dikenal sebagai Teorema Størmer. .

Tantangan

Tugas Anda adalah untuk menulis sebuah program atau fungsi yang, dengan memberikan bilangan prima input $k$ , mengeluarkan atau mengembalikan semua pasangan $k$ -mulus tanpa duplikat (urutan dalam pasangan tidak menjadi masalah) dalam urutan apa pun yang Anda inginkan.

Harap dicatat bahwa untuk bilangan prima $p$ dan $q$ , dengan asumsi $p<q$ , semua pasangan $p$ -smooth juga merupakan pasangan $q$ -smooth.

Contoh I / O

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)

Larangan

Program atau fungsi harus diakhiri secara teoritis dalam waktu yang terbatas untuk semua input. Celah standar tidak diizinkan secara default.

Kriteria Menang

Karena ini adalah tantangan kode-golf , pengiriman terpendek yang valid untuk setiap bahasa akan menang.

JavaScript (ES7),  234  232 byte

Temukan solusinya dengan menyelesaikan persamaan Pell dari bentuk $x^2-2qy^2=1$ , di mana $q$ adalah $P$ angka bebas persegi square.

Ini adalah implementasi dari prosedur Derrick Henry Lehmer , yang berasal dari prosedur asli Størmer.

Mengembalikan objek yang kunci dan nilainya menggambarkan pasangan $P$ -smooth.

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

Cobalah online!

Bagaimana?

Penolong fungsi $s$ tes apakah integer diberikan $n$ adalah $P$ sejumlah -smooth ketika itu disebut dengan $i=0$ , atau persegi gratis ¹ $P$ nomor -smooth ketika itu disebut dengan $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)

Kami mencari semua angka P- ¹ persegi bebas di [ 1 .. P P - 1$P$$[1..P^P-1]$ , di mana$P^P$ digunakan sebagai batas atas untuk$P!$.

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

Untuk setiap nomor $n$ ditemukan di atas, kami mencari solusi mendasar dari persamaan Pell $x^2-ny^2=1$ :

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

(kode di atas adalah versi non-rekursif dari jawaban saya untuk tantangan lain ini )

Setelah solusi mendasar $(x_1,y_1)$ ditemukan, kami menghitung solusi $(x_k,y_k)$ dengan $k\le max(3,(P+1)/2)$ , menggunakan relasi perulangan:

Untuk setiap $x_k$ , kita menguji apakah $x_k$ aneh dan kedua $(x_k-1)/2$ dan $(x_k+1)/2$ adalah $P$ -smooth. Jika demikian, kita menyimpannya di objek $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: Karena tidak menguji keutamaan pembagi, fungsi $s$ sebenarnya akan jujur ​​untuk beberapa nomor bebas non-persegi, bahkan ketika itu disebut dengan $i=1$ . Idenya adalah untuk menyaring sebagian besar dari mereka sehingga tidak banyak persamaan Pell yang tidak berguna diselesaikan.}

Jelly , 16 14 byte

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

Cobalah online!

Memeriksa pasangan hingga $4^k$ yang tidak efisien untuk k yang lebih besar$k$ tetapi harus memastikan tidak ada yang terlewatkan.

Terima kasih kepada @JonathanAllan karena telah menghemat 1 byte!

Penjelasan

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 byte

°Lü‚ʒfà@

Cobalah online!

Penjelasan:

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

Jelly , 123 byte

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

Cobalah online!

$2×$$\max(3, \frac{k+1}{2})$$\frac{x-1}{2}, \frac{x+1}{2}$halus untuk setiap solusi. Ini adalah metode Lehmer, seperti yang dijelaskan dalam tautan Wikipedia pertanyaan .

Program lengkap yang membutuhkan satu argumen, $k$dan mengembalikan daftar daftar pasangan. Kode di atas tidak mengurutkan hasil akhir, tetapi tautan TIO tidak.

Haskell , 118 107 byte

-11 byte terima kasih kepada 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)]

Cobalah online!

• q n menghitung daftar semua faktor utama n
• f k menghasilkan daftar $k$-pasangan halus untuk k yang diberikan dengan memfilter daftar semua pasangan

Jelly , 24 byte

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

Cobalah online!

Ini membutuhkan waktu lama untuk 7, tetapi menghitung jauh lebih cepat jika Anda menghapus kuadrat faktorial: Coba online!

Penjelasan:

³!²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 byte terima kasih kepada @JonathanAllen

Python 3 + sympy, 116 byte

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]

Cobalah online!

Python 3 + sympy, 111 byte

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

Cobalah online!

Dua variasi pada jawaban Jelly saya tetapi dalam Python 3. Keduanya mendefinisikan fungsi yang menerima argumen k. Yang pertama mengembalikan daftar tupel dari pasangan yang memenuhi kriteria. Yang kedua mencetaknya ke stdout.

Bahasa Wolfram (Mathematica) , 241 byte

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

Cobalah online!

Pyth , 15 byte

f!>#QsPMTCtBS^4

Cobalah online!

Menggunakan pengamatan Nick Kennedy bahwa tidak ada nomor output yang lebih besar dari 4^k.

05AB1E , 16 byte

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

Cobalah secara online (sangat tidak efisien, jadi waktunya habis$n\gt3$..) Di sini alternatif yang sedikit lebih cepat , meskipun masih cukup lambat ..

Penjelasan:

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

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

Jalankan dan debug itu

Ini bukan program yang sesingkat mungkin, tetapi mulai menghasilkan output segera setelah pasangan yang cocok ditemukan. Ini memang berakhir pada akhirnya , tetapi output dihasilkan saat ditemukan.

Ruby , 89 + 8 = 97 byte

Menggunakan -rprimebendera. Untuk setiap nomor$i$ dari 1 hingga $4^n$, petakan [i, i+1]jika keduanya$n$-smooth, kalau tidak petakan itu false, lalu pangkas semua falsedari daftar.

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

Cobalah online!