Apakah kode ini berhenti?

92

Ini adalah tantangan golf kode yang saya pikir dengan bengkok matematika. Tantangannya adalah untuk menulis kode sesingkat mungkin sehingga merupakan pertanyaan terbuka apakah kode tersebut berakhir atau tidak. Sebuah contoh dari apa yang saya maksud bisa menjadi potongan kode berikut python, diadaptasi dari sebuah anwser ke ini cs pertanyaan stackexchange.

def is_perfect(n):
    return sum(i for i in range(1, n) if n % i == 0) == n

n = 3
while not is_perfect(n):
    n = n + 2

Matematikawan mengira bahwa tidak ada angka sempurna yang ganjil, tetapi belum pernah terbukti, jadi tidak ada yang tahu jika kode ini akan berakhir. Bisakah Anda membuat potongan kode lain (mungkin mengandalkan masalah terbuka lainnya seperti dugaan Collatz, atau dugaan kembar prima) yang lebih pendek, tetapi yang tidak diketahui apakah mereka berakhir atau tidak?

Sunting: Beberapa orang telah mengemukakan aturan tambahan yang bagus - Solusi untuk pertanyaan harus bersifat deterministik. Meskipun mungkin lebih menarik jika Anda dapat menemukan solusi yang lebih pendek menggunakan nondeterminisme. Dalam hal ini, aturannya adalah menemukan cuplikan yang kemungkinan pemutusannya tidak diketahui.

Bolton Bailey
sumber
2
Selamat datang di PPCG!
Luis Mendo
3
Kode Anda dapat golfed ke 50 byte: n=3 while sum(k*(n%k<1)for k in range(1,n))-n:n+=2.
xnor
13
Ini benar-benar konsep yang hebat. Sangat menyenangkan melihat ide orisinal seperti ini.
Nathan Merrill
7
@Mego Saya pikir tantangan ini hanya berfungsi jika Anda menganggap tipe data yang tak terbatas apa yang secara otomatis akan mengasumsikan memori yang tak terbatas.
Martin Rosenau
52
Ketika saya membaca judulnya, saya pikir Anda ingin kami memecahkan masalah yang terputus-putus DAN golf solusinya.
MrPaulch

Jawaban:

29

Jelly , 7 byte

!‘Ʋµ4#

Cobalah online!

Latar Belakang

Ini akan berakhir setelah ia menemukan solusi keempat untuk masalah Brocard , yaitu solusi n! +1 = m² dengan (n, m) ≠ (4, 5), (5, 11), (7, 71) di atas bilangan bulat positif. Implementasinya tidak menggunakan aritmatika floating point, jadi itu hanya akan berakhir jika tidak menemukan solusi keempat atau jika n! tidak dapat lagi direpresentasikan dalam memori.

Masalah Brocard pertama kali digunakan dalam jawaban ini oleh @xnor.

Bagaimana itu bekerja

!‘Ʋµ4#  Main link. No arguments. Implicit argument: 0

    µ4#  Convert the links to the left into a monadic chain and call it with
         arguments k = 0, 1, 2, ... until 4 of them return 1.
!        Factorial; yield k!.
 ‘       Increment; yield k! + 1.
  Ʋ     Squareness; return 1 if k! + 1 is a perfect square, 0 if not.
Dennis
sumber
3
Saya perlu belajar jelly ...
no 23zɐɹƆ
19

Jelly , 11 9 byte

ÆẸ⁺‘ÆPµ6#

Ini akan berakhir setelah perdana Fermat keenam ditemukan.

Cobalah online!

Bagaimana itu bekerja

ÆẸ⁺‘ÆPµ6#  Main link. No arguments. Implicit argument: 0

      µ6#  Convert the links to the left into a monadic chain and call it with
           arguments k = 0, 1, 2, ... until 6 of them return 1.
ÆẸ         Convert [k] to the integer with that prime exponent factorization, i.e.,
           into 2 ** k.
  ⁺        Repeat.
   ‘       Increment.
           We've now calculated 2 ** 2 ** k + 1.
    ÆP     Test the result for primality.
Dennis
sumber
16

Pyth, 10 byte

fP_h^2^2T5

Menggunakan dugaan bahwa semua nomor Fermat 2^(2^n)+1 merupakan gabungan untuk n>4.

f        5   Find the first number T>=5 for which
   h^2^2T    2^(2^T)+1
 P_          is prime                   
Tidak
sumber
11

Python, 36 byte

k=n=1
while(n+1)**.5%1+7/k:k+=1;n*=k

Menggunakan masalah Brocard :

Apakah n! +1 kuadrat sempurna untuk n≥8?

Hitung faktorial yang berurutan dan periksa apakah ada kuadrat dan miliki k>7. Terima kasih kepada Dennis untuk 2 byte!

Ini mengasumsikan Python terus memiliki aritmatika yang akurat untuk jumlah besar yang sewenang-wenang. Dalam implementasi aktual, ia berakhir.

Tidak
sumber
1
Tidak akan -~n**.5bekerja di tempat (n+1)**.5?
ETHproduksi
@ ETHproductions Diutamakan dari eksponen lebih tinggi daripada diutamakan ~, sehingga hanya akan meningkatkan TypeError untuk mencoba meniadakan float bitwise.
Dennis
11

Perl, 50 38 36 34 33 byte

$_=196;$_+=$%while($%=reverse)-$_

Penjelasan: 196 adalah nomor Lychrel yang mungkin - angka yang tidak membentuk palindrom dengan berulang kali menambahkan kebalikannya ke dirinya sendiri. Loop berlanjut hingga $ n sama dengan kebalikannya, yang belum diketahui untuk nilai awal 196.

25 + 52 = 77

yang tidak valid

96 + 69 = 165
165 + 561 = 726
726 + 627 = 1353
1353 + 3531 = 4884

jadi tidak ada angka dalam urutan ini yang valid.

Sunting: Dipotong dengan menggunakan loop sampai alih-alih for loop (entah bagaimana). Juga, saya memiliki byte lebih sedikit dari yang saya kira (saya mungkin harus melihat bytecount saya lebih hati-hati di masa depan).

Sunting: Diganti $ndengan $_untuk menyimpan 2 byte untuk argumen tersirat di reverse. Saya pikir ini sama golfnya dengan implementasi ini.

Sunting: Saya salah. Alih-alih menggunakan until($%=reverse)==$_aku bisa pergi sementara perbedaannya adalah nol (yaitu benar): while($%=reverse)-$_.

Gabriel Benamy
sumber
3
Karena ada sejumlah terbatas dari angka perl yang mungkin, saya sebenarnya dapat menentukan apakah program ini berakhir atau tidak. Anda perlu memuat paket bigint untuk membuat pekerjaan ini (atau mengimplementasikannya)
Ton Hospel
Lakukan. Saya menantang Anda. :-)
Veky
11

MATL, 11 byte

`@QEtZq&+=z

Mengakhiri jika dugaan Goldbach salah. Yaitu, program berhenti jika menemukan bilangan genap lebih besar dari 2itu tidak dapat dinyatakan sebagai jumlah dari dua bilangan prima.

`        % Do...while
  @      %   Push iteration index k. Gives 1, 2, 3, ...
  QE     %   Add 1 and multiply by 2. Gives 4, 6, 8, ...
  tZq    %   Duplicate. Push all primes up to current k
  &+     %   Matrix with all pairwise additions of those primes
  =z     %   Number of entries of that matrix that equal k. This is used as loop
         %   condition. That is, the loop continues if this number is nonzero
         % Implicit end
Luis Mendo
sumber
8

05AB1E , 8 byte

Akan berakhir ketika perdana Fermat ke-6 ditemukan.

5µNoo>p½

Penjelasan

5µ          # loop over increasing N (starting at 1) until counter reaches 5
  Noo       # 2^2^N
     >      # + 1
      p½    # if prime, increase counter
Emigna
sumber
8

Python, 30 28 byte

n=2
while 2**~-n%n**3-1:n+=1

Program ini akan berhenti jika dan hanya jika ada bilangan bulat n lebih besar dari 1 sehingga 2 ^ (n-1) -1 dapat dibagi dengan n ^ 3. Sepengetahuan saya, tidak diketahui apakah ada nomor dengan properti ini (jika nomor yang memuaskan properti ini prima, itu disebut prima Wieferich pesanan 3 ke basis 2, dan terbuka apakah ada perdana semacam itu).

Julian Rosen
sumber
Apakah Anda yakin tanda kurung ditempatkan dengan benar? Sepertinya Anda sedang menguji untuk melihat apakah 2 ^ (n-1)! ≡ 1 (mod n ^ 3), bukan 2 ^ n ≡ 1 (mod n ^ 3). Memang, saya tidak tahu operator Python diutamakan semua dengan baik.
Gabriel Benamy
Aduh, kodenya benar, tetapi penjelasan saya tidak. Saya akan memperbaikinya.
Julian Rosen
2
Anda dapat menggantinya (n-1)dengan~-n
Wheat Wizard
7

Haskell, 47 byte

[n|n<-[1..],2*n==sum[d|d<-[2..n],n`mod`d<1]]!!0

Mencari angka kuasi sempurna pertama , yang merupakan angka ndengan jumlah pembagi 2*n+1. Alih-alih menambahkan 1, saya mengecualikan 1 dari daftar pembagi.

Sievers Kristen
sumber
6

Brain-Flak, 212 208 204 byte

Program ini menggunakan algoritma multiplikasi yang ditulis oleh MegaTom dan non-square checker yang ditulis oleh 1000000000

Cobalah secara Online

(((()()()()){})){{}((({}()))<{(({})[()])}{}>[()]){({}<({}<>)({<({}[()])><>({})<>}{}<><{}>)>[()])}{}(({}())){(({}[()]<>)<>)(({({})({}[()])}{}[({})]<>)){{}{}({}<>)(<([()])>)}{}({}()){(((<{}{}<>{}>)))}{}}{}}

Program ini dimulai pukul 8 dan menguji setiap angka untuk melihat apakah n! +1 adalah angka kuadrat. Keluar ketika menemukan satu. Ini dikenal sebagai Masalah Brocard dan ini merupakan masalah terbuka dalam matematika.

Wisaya Gandum
sumber
6

Brachylog (v2), 3 byte dalam penyandian Brachylog

⟦cṗ

Cobalah online! (akan keluar tanpa melakukan sesuatu yang terlihat, untuk alasan yang jelas)

Program lengkap; jika dijalankan tanpa input, cari perdana Smarandache pertama , dan hasilkan true.jika dan ketika ditemukan. Ini pertanyaan terbuka, apakah ada bilangan prima Smarandache. (Perhatikan bahwa algoritme pengujian-utama Brachylog, meskipun bekerja secara teori dalam jumlah besar yang sewenang-wenang, cenderung berjalan lambat pada mereka; dengan demikian, jika Anda tertarik untuk menemukan sendiri Smarandache membanggakan, saya sarankan menggunakan bahasa yang berbeda.)

Penjelasan

⟦cṗ
⟦     Form an increasing range from 0 to {the smallest number with no assertion failure} 
 c    Concatenate all the numbers that make up that range, in decimal
  ṗ   Assert that the result is prime

Brachylog beroperasi pada angka desimal angka setiap kali Anda mencoba memperlakukannya seperti daftar, jadi "rentang" diikuti oleh "concatenate" adalah cara yang sangat singkat untuk menghasilkan urutan angka Smarandache (dan kemudian kami memfilternya berdasarkan primality; Brachylog's perilaku program penuh default kemudian akan memaksa elemen pertama dari generator yang dihasilkan). Rentang memiliki nol di depan, tetapi untungnya, dengan pola aliran ini, Brachylog menghapus nol daripada gagal.

Berikut adalah contoh yang menemukan nomor Smarandache pertama yang sama dengan 6 (mod 11), sebagai demonstrasi dari program serupa yang berakhir dalam 60 detik daripada memiliki status penghentian yang tidak diketahui:

⟦c{-₆~×₁₁&}

Cobalah online!

Ini akan dicetak true.sebagai program penuh, tapi saya melemparkan Zargumen baris perintah untuk benar-benar mencetak nomor yang bersangkutan, memberikan demonstrasi yang lebih baik bahwa pendekatan umum ini berfungsi.

ais523
sumber
5

Python 2, 88 byte

p=lambda n:all(n%x for x in range(2,n))
s=lambda n:0if p((10223*2**n)+1)else s(n+1)
s(0)

Kode ini akan berakhir jika 10223 adalah nomor Sierpiński. 10223 saat ini adalah kandidat terkecil yang mungkin atau mungkin bukan nomor Sierpiński, pada Desember 2013.

Angka Sierpiński adalah angka kdi mana semua angka dari formulir tersebut (k * 2^n) + 1adalah gabungan.

Qwerp-Derp
sumber
Saya harap masalah ini dan masalah Sierpinski diselesaikan dalam waktu dekat, hanya dengan lebih banyak perhitungan.
qwr
4
Kode ini pasti berakhir, karena Anda hanya menyebutkan dua lambda, Anda sebenarnya tidak memanggil apa pun. :-P
Veky
4
Sebenarnya kamu tidak. Kode Anda masih selalu berakhir, karena semantik Python2 dibekukan (PEP 404), dan itu termasuk batas keras pada panggilan rekursif oleh fiat BDFL ( neopythonic.blogspot.hr/2009/04/final-words-on-tail-calls.html ). ;-P
Veky
2
@Veky Harus mengubah komentar Anda.
Qwerp-Derp
1
Tidak beberapa hari setelah ini ditulis, perdana 10223*2^31172165 + 1 ditemukan . Sejak saat itu, 21181menjadi angka terkecil yang tidak diketahui apakah itu Sierpiński atau bukan.
Jeppe Stig Nielsen
4

Pyth, 16 byte

f!}1.u@,/G2h*3GG

Mengembalikan nilai pertama yang tidak dimiliki oleh dugaan Collatz. Karena tidak diketahui apakah dugaan berlaku untuk semua angka, tidak diketahui apakah kode ini akan berakhir.

Steven H.
sumber
3
Tanpa bisa membacanya, saya ragu kode Anda melakukan apa yang Anda klaim. Apakah Anda mencari angka pertama yang berbeda dari 4-2-1? Saya kira Anda tidak akan menemukannya jika ada angka yang lebih kecil yang tidak berakhir dalam loop apa pun. Bagaimanapun, jika itu yang dilakukan oleh kode Anda, itu cukup baik untuk tidak mengetahui apakah itu akan berakhir.
Christian Sievers
1
Saya mencari integer pertama> = 1 yang menuju ke loop dan tidak ada di mana dalam traversal ke loop yang berisi 1.
Steven H.
3
Itu yang saya harapkan. Tapi itu bukan satu-satunya cara yang mungkin untuk nomor untuk tidak memenuhi dugaan collatz.
Christian Sievers
Sebenarnya, telah terbukti bahwa setiap angka baik menyimpang hingga tak terbatas atau menutupi ke 1-2-4 di bawah peta Collatz. Kode Anda tidak akan pernah berakhir. Idenya adalah bahwa urutan langkah-langkah yang membentuk lingkaran mengatur persamaan, yang solusinya hanya 1-2-4, nilai negatif dan rasional non-integer.
John Dvorak
3
@ JanDvorak Saya tidak percaya itu benar. Bisakah Anda mengutip sumber?
KSFT
4

Sebenarnya , 16 byte

1`;;pY)▒@D÷íu*`╓

Cobalah online!

Kode ini berakhir jika ada beberapa nomor komposit nyang totient(n)membagi n-1( masalah total Lehmer ).

Penjelasan:

1`;;pY)▒@D÷íu*`╓
1`            `╓  first integer, starting with 0, where the following function leaves a truthy value on top of the stack:
    pY       *      composite (not prime) and
   ;  )▒            totient(n)
  ;     @D֒u       is in the list of divisors of n-1
Mego
sumber
4

Jelly , 9 8 byte

-1 byte terima kasih kepada @Dennis! (gunakan eksponensial alih-alih multiplikasi untuk menghindari Æṣ(0))

*ḂÆṣ=µ2#

Akan mengembalikan daftar nol dan angka sempurna ganjil terkecil , jika ada.

Bagaimana?

*ḂÆṣ=µ2# - Main link: no arguments
     µ   - monadic chain separation
      2# - count up from implicit `n=0` and return the first 2 truthy results of
 Ḃ       -     mod 2        -> n%2
*        -     exponentiate -> n**(n%2)  (1 when n is even, n when n is odd)
  Æṣ     -     sum of proper divisors of n**(n%2)
    =    -     equals n?    -> 1 if n is zero or both perfect and odd, else 0
Jonathan Allan
sumber
4

Haskell, 46 byte

[n|m<-[1..],n<-[1..m],product[1..n]+1==m^2]!!3

Hentikan jika menemukan solusi ke-4 untuk masalah brocard .

BlackCap
sumber
3

Python, 92 byte

Ini bukan memenangkan kompetisi golf kode apa pun, dan ini membutuhkan memori tak terbatas dan kedalaman rekursi, tetapi ini adalah kesempatan yang hampir sempurna untuk memasukkan masalah menarik yang saya tanyakan pada matematika stackexchange dua tahun lalu, bahwa tidak ada angka Fibonacci lebih besar dari 8 yang merupakan jumlah dua kubus positif . Cukup lucu, itu dimulai sebagai ide kode tantangan golf, jadi saya kira saya sudah datang lingkaran penuh.

def f(i,j):
 r=range(i)
 for a in r:
  for b in r:
   if a**3+b**3==i:1/0
 f(j,i+j)
f(13,21)
qwr
sumber
3

Python 2, 123 98 92 byte

p=lambda n,k=2:n<=k or n%k*p(n,k+1)
g=lambda n:[p(b)*p(n-b)for b in range(n)]and g(n+2)
g(4)

Kode ini akan berakhir jika dugaan Goldbach tidak berlaku untuk semua bilangan genap (yaitu jika semua bilangan genap dapat dinyatakan sebagai jumlah dari dua bilangan prima). Saat ini telah diuji untuk angka hingga 4 * 10 ^ 18.

Terima kasih banyak kepada @ Pietu1998 yang telah mempersingkat kode saya!

EDIT: Terima kasih kepada @JonathanAllan karena telah mencukur 6 byte dari kode saya!

Qwerp-Derp
sumber
Saya pikir Anda dapat menyimpan 6 byte dengan g=lambda n:[p(b)*p(n-b)for b in range(n)]and g(n+2). Saya juga berpikir ini harus dibaca "akan berakhir jika dugaan Goldbach tidak berlaku".
Jonathan Allan
2

JavaScript (ES6), 104 101 byte

for(n=[6,9,p=1];!p;n=n.map((x,i)=>(q=n[n.length+~i],p|=x^q,c=q+x+c/10|0)%10).concat(c/10|0||[]))c=p=0

Menggunakan metode yang sama dengan jawaban Perl: set n ke 196, lalu berulang kali menambahkan n ke basis 10 terbalik sampai menjadi palindrom di basis 10. Ini akan lebih pendek jika JS mendukung angka presisi sewenang-wenang, tetapi oh well.

Produksi ETH
sumber
Meskipun ini panjang, pandai golf, jadi +1.
wizzwizz4
2

Python, 80 byte

Berakhir jika dugaan Collatz terbukti salah. Lihat pertanyaan ini .

n=2
while 1:
 L=[];x=n
 while~-n:1/(n not in L);L+=[n];n=(n/2,n*3+1)[n%2]
 n=x+1
mbomb007
sumber
Itu menjijikkan, tetapi juga indah.
James Murphy
1

Python 2, 64 byte

Bilangan Lychrel adalah bilangan alami yang tidak dapat membentuk palindrom melalui proses berulang berulang kali digitnya dan menambahkan angka yang dihasilkan.

Tidak ada angka Lychrel yang terbukti ada di basis sepuluh. 196 adalah kandidat nomor sepuluh basis Lychrel terkecil. Telah ditunjukkan bahwa jika palindrom ada (membuat 196 bukan angka Lychrel), itu akan memiliki setidaknya satu miliar (10 ^ 9) digit, karena orang telah menjalankan algoritma yang lama.

n=196
while 1:
    x=str(n);r=x[::-1]
    if x!=r:n=n+int(r)
    else:1/0
mbomb007
sumber
@trichoplax Ah, tab / spasi "fitur" menyerang lagi ...
wizzwizz4
1
Jika orang lain juga mendapati konversi tab tidak membantu, ada diskusi tentang meta ...
trichoplax
1

Jelly , 7 byte

*+3Ẓµ4#

Cobalah online! (mencetak dua elemen, bukan 4, sehingga Anda benar-benar dapat melihatnya berhenti)

nnn+3

Penjelasan

*+3Ẓµ4#
     4#  Find the first four numbers with the following property:
    µ      (bracketing/grouping: place everything to the left inside the loop)
*          {The number} to the power of {itself}
 +3        plus 3
   Ẓ       is prime
ais523
sumber
0

R, 30 byte, dapat diperdebatkan apakah itu deterministik

while(any(sample(2,654,T)>1))1

Generator angka acak default R memiliki distribusi kesetaraan dalam 653 dimensi berurutan tetapi tidak diketahui dalam 654 dimensi. Dengan demikian mungkin ada atau mungkin tidak ada urutan nomor pseudorandom yang sampel elemen terendah dari vektor yang diberikan 654 kali berturut-turut (di sini vektor 1:2).

Sejak R RNG periodik (meskipun dengan waktu yang sangat lama), saya menyatakan bahwa ini adalah deterministik karena akhirnya akan loop putaran ke awal. Pendapat Anda mungkin berbeda, tentu saja.

JDL
sumber
0

Python 3, 101 byte

Saya tahu ini lebih lama daripada yang lain, tetapi saya menghabiskan banyak waktu melihat betapa singkatnya saya bisa bermain golf ini.

Upaya ini untuk menyangkal dugaan Sum of Powers Euler untuk k=6(tidak ada solusi bilangan bulat positif untuk persamaan Diophantine A^6+B^6+C^6+D^6+E^6==F^6), yang tidak ditemukan sampel tandingan.

R=[1]
while 1:R+=[R[-1]+1];eval(("[1/("+"+%s**6"*5+"!=%%s**6)%s]"%("for %s in R "*6))%(*"ABCDEF"*2,))

Dalam Python 2 (104 byte):

R=[1]
while 1:R+=[R[-1]+1];eval(("[1/("+"+%s**6"*5+"!=%%s**6)%s]"%("for %s in R "*6))%tuple("ABCDEF"*2))

Kurang bermain golf:

x=2
while 1:
    R=range(1,x)
    [1/(A**6+B**6+C**6+D**6+E**6!=F**6)for F in R for E in R for D in R for C in R for B in R for A in R]
    x+=1

Versi matematika tanpa eval:

R=range
x=2
while 1:
    for i in R(x**6):1/(sum(map(lambda x:x**6,[1+(i%x**-~j/x**j)for j in R(6)]))-i%x-1)
    x+=1

Referensi alternatif: Euler's Sum of Powers Conjecture - MathWorld

mbomb007
sumber
0

Python, 68 byte

n=2
while"".join(str((i+2)**n)[0]for i in range(8))!="23456789":n+=1

Cobalah online

Mencoba menjawab salah satu Pertanyaan Gelfand .

  1. Apakah baris "23456789" akan muncul untuk n> 1? Tidak ada yang berhasil untuk n <= 10 ^ 5. ...
mbomb007
sumber
0

Clojure, 154 byte

(loop[x 82001](if(= 0(reduce +(map{true 1 false 0}(for[y(range 3 6)](true?(for[z(str(range 2 y))](.indexOf z(Integer/toString x y))))))))x(recur(inc x))))

Cek apakah ada angka di atas 82.000 yang hanya berisi 0 dan 1 untuk basis 2 sampai ke basis 5. Dengan kata lain, memeriksa apakah ada nomor lain dalam urutan ini .

Dalam kelompok khusus, hanya ada 3 nomor: 0, 1dan 82,000. Tidak ada lagi angka yang mengikuti aturan yang kurang dari kira-kira 3*10^19723.

Qwerp-Derp
sumber