Terinspirasi oleh pertanyaan ini di Matematika .
Masalah
Biarkan
n
menjadi bilangan alami≥ 2
. Ambil pembagi terbesarn
- yang berbeda darin
dirinya sendiri - dan kurangi darin
. Ulangi sampai Anda mendapatkan1
.
Pertanyaan
Berapa banyak langkah yang diperlukan untuk meraih 1
angka tertentu n ≥ 2
.
Contoh terperinci
Mari
n = 30
.
Pembagi terbesar:
1. 30 is 15 --> 30 - 15 = 15
2. 15 is 5 --> 15 - 5 = 10
3. 10 is 5 --> 10 - 5 = 5
4. 5 is 1 --> 5 - 1 = 4
5. 4 is 2 --> 4 - 2 = 2
6. 2 is 1 --> 2 - 1 = 1
Dibutuhkan 6 langkah untuk mencapainya 1
.
Memasukkan
- Input adalah bilangan bulat
n
, di manan ≥ 2
. - Program Anda harus mendukung input hingga nilai integer maksimum bahasa.
Keluaran
- Cukup tampilkan jumlah langkah, seperti
6
. - Leading / trailing spasi putih atau baris baru baik-baik saja.
Contohnya
f(5) --> 3
f(30) --> 6
f(31) --> 7
f(32) --> 5
f(100) --> 8
f(200) --> 9
f(2016^155) --> 2015
Persyaratan
- Anda bisa mendapatkan input dari
STDIN
, argumen baris perintah, sebagai parameter fungsi atau dari padanan terdekat. - Anda dapat menulis suatu program atau fungsi. Jika ini adalah fungsi anonim, harap sertakan contoh cara memintanya.
- Ini adalah kode-golf sehingga jawaban terpendek dalam byte menang.
- Celah standar tidak diijinkan.
Seri ini dapat ditemukan di OEIS juga: A064097
Logaritma kuasi didefinisikan secara induktif oleh
a(1) = 0
dana(p) = 1 + a(p-1)
jikap
adalah prima dana(n*m) = a(n) + a(m)
jikam,n > 1
.
code-golf
math
arithmetic
masukkan nama pengguna di sini
sumber
sumber
2^32 - 1
. Sisanya terserah Anda dan sistem Anda. Harapan, inilah yang Anda maksud dengan pertanyaan Anda.Jawaban:
Jelly , 9 byte
Cobalah online! atau verifikasi semua kasus uji .
Latar Belakang
Definisi urutan A064097 menyiratkan bahwa
Dengan formula produk Euler
di mana φ menunjukkan fungsi total Euler dan p bervariasi hanya pada bilangan prima.
Menggabungkan keduanya, kami menyimpulkan properti
di mana ω menunjukkan jumlah faktor prima yang berbeda dari n .
Menerapkan rumus yang dihasilkan k + 1 kali, di mana k cukup besar sehingga φ k + 1 (n) = 1 , kita dapatkan
Dari properti ini, kami memperoleh formula
di mana persamaan terakhir berlaku karena ω (1) = 0 .
Bagaimana itu bekerja
sumber
05AB1E ,
1311 byteKode:
Penjelasan:
Menggunakan pengodean CP-1252 . Cobalah online! .
sumber
[¼Ñü-¤ÄD#]¾
- Saya hampir memotong satu byte dengan berpasangan, oh well ...[Ð#Ò¦P-¼]¾
.Ð
lebih baik daripadaDD
.Pyth, 11 byte
Suite uji
Ulangi berulang sampai benar.
Penjelasan:
sumber
f
ilter.f
?f
tanpa argumen kedua mengulangi semua bilangan bulat positif mulai dari1
dan mengembalikan nilai pertama yang memberikan true pada pernyataan dalam. Nilai ini kebetulan tidak digunakan dalam program ini, sehingga mengembalikan berapa kali ia berjalan. Bukan tidak berdokumen, hanya ortodoks :) Jika ini membantu, Anda dapat menganggap ini sebagaifor
loop seperti:for(int i=1; some_condition_unrelated_to_i; i++) { change_stuff_that_affects_condition_but_not_i;}
f <l:T> <none>
),f
adalah input Pertama di manaA(_)
kebenaran berakhir[1, 2, 3, 4...]
.Python 2,
5049 byteIni tidak akan menyelesaikan ujian terakhir dalam waktu dekat ...
Atau, inilah 48-byte yang mengembalikan
True
bukan1
untukn=2
:sumber
Jelly , 10 byte
Cobalah online! atau verifikasi sebagian besar kasus uji . Kasing uji terakhir selesai dengan cepat secara lokal.
Bagaimana itu bekerja
sumber
Retina , 12
Ini mengasumsikan input yang diberikan dalam unary dan output diberikan dalam desimal. Jika ini tidak dapat diterima maka kita dapat melakukan ini selama 6 byte lagi:
Retina , 18
Cobalah online - baris pertama ditambahkan untuk menjalankan semua testcases dalam sekali jalan.
Sayangnya ini menggunakan unary untuk perhitungan, jadi input 2016 155 tidak praktis.
1
ssumber
\b
.Pyth -
151413 byteCasing khusus
1
benar-benar membunuh saya.Cobalah online di sini .
sumber
1
?1
adalah[]
, yang menyebabkan kesalahan ketika saya mengambil elemen pertama. Saya harus membuat case khusus untuk membuatnya kembali1
lagi sehingga titik.u
tetap berakhir. Saya menemukan cara yang lebih baik daripada.x
coba-kecuali yang menyelamatkan saya 2 byte..u
tetap pada akhirnya akan mencapai1
semua input, di mana pada titik itu harus dikurung khusus.JavaScript (ES6),
* 4438Edit 6 byte yang disimpan, terima kasih @ l4m2
(* 4 dipukul masih 4)
Fungsi rekursif
Kurang golf
Uji
sumber
f=(n,d=n)=>n>1?n%--d?f(n,d):f(n-d)+1:0
?Mathematica, 36 byte
Fungsi yang tidak disebutkan namanya membutuhkan byte yang sama:
Ini adalah implementasi definisi yang sangat mudah sebagai fungsi rekursif.
sumber
Oktaf,
595855 byteSampel berjalan:
sumber
end
diperlukan dalam oktaf?Haskell, 59 byte
Pemakaian:
Mungkin sedikit tidak efisien untuk angka besar karena menghasilkan daftar.
sumber
<1
alih-alih==0
menyimpan beberapa byte:f 1=0;f n=1+f(n-last[a|a<-[1..n
div2],mod n a<1])
Julia,
56504539 byteIni adalah fungsi rekursif yang menerima integer dan mengembalikan integer.
Tidak Disatukan:
Cobalah online! (termasuk semua kasus uji)
Disimpan 6 byte berkat Martin Büttner dan 11 terima kasih kepada Dennis!
sumber
PowerShell v2 +, 81 byte
Terkuat dari kekuatan kasar.
Mengambil input
$a
, memasukkan satufor
lingkaran hingga$a
kurang dari atau sama dengan1
. Setiap loop kita melewatifor
loop lain yang menghitung mundur dari$a
sampai kita menemukan pembagi (!($a%$i
). Paling buruk, kita akan menemukan$i=1
sebagai pembagi. Ketika kita melakukannya, tambahkan penghitung kita$j
, kurangi pembagi kita$a-=$i
dan bersiap$i=0
untuk keluar dari lingkaran dalam. Akhirnya, kita akan mencapai kondisi di mana loop luar salah (yaitu,$a
telah mencapai1
), jadi output$j
dan keluar.Perhatian : Ini akan memakan waktu lama untuk angka yang lebih besar, terutama bilangan prima. Input 100.000.000 memakan waktu ~ 35 detik pada laptop Core i5 saya. Sunting - baru diuji dengan
[int]::MaxValue
(2 ^ 32-1), dan butuh ~ 27 menit. Tidak terlalu buruk, kurasa.sumber
Matlab, 58 byte
sumber
Japt , 12 byte (tidak bersaing)
Uji secara online! Non-bersaing karena menggunakan banyak fitur yang ditambahkan jauh setelah tantangan diposting.
Bagaimana itu bekerja
Teknik ini terinspirasi oleh jawaban 05AB1E . Versi sebelumnya digunakan
²¤
(tekan 2, potong dua item pertama)Å
karena lebih pendek satu byte daris1
(perhatikan spasi tambahan); Saya baru menyadari setelah fakta bahwa karena ini menambahkan angka 2 ke akhir array dan irisan dari awal , sebenarnya gagal pada angka komposit ganjil, meskipun ia bekerja pada semua kasus uji yang diberikan.sumber
Python 3,
75, 70, 67 byte.Ini adalah solusi rekursif yang cukup lurus ke depan. Dibutuhkan waktu yang SANGAT lama untuk kasus uji angka tinggi.
sumber
> <>, 32 byte
Mengharapkan nomor input
n
,, pada tumpukan.Program ini membangun urutan lengkap di tumpukan. Karena satu-satunya angka yang dapat mengarah
1
adalah2
, membangun urutan berhenti ketika2
tercapai. Ini juga menyebabkan ukuran tumpukan sama dengan jumlah langkah, bukan jumlah langkah +1.sumber
Ruby, 43 byte
Temukan angka terkecil
i
sedemikian sehinggax
membagix-i
dan berulang sampai kita mencapai1
.sumber
Haskell, 67 byte
Ini kodenya:
Dan inilah salah satu alasan mengapa Haskell luar biasa:
Ya, di Haskell Anda dapat mendefinisikan
-->
setara dengan==
.sumber
Matlab, 107 byte
sumber
MATL,
1716 byteCobalah secara Online
Penjelasan
sumber
C99,
6261 byte1 byte bermain golf oleh @Alchymist.
Panggil sebagai f (x, & y), di mana x adalah input dan y adalah output.
sumber
Julia,
3936 byteCobalah online!
sumber
Clojure,
116104 byte-12 byte dengan memfilter rentang untuk menemukan kelipatan, kemudian menggunakan
last
satu untuk mendapatkan yang terbesarSolusi naif yang pada dasarnya hanya menyelesaikan masalah seperti yang dijelaskan oleh OP. Sayangnya, menemukan pembagi terbesar saja membutuhkan setengah dari byte yang digunakan. Setidaknya saya harus punya banyak ruang untuk bermain golf dari sini.
Pregolfed dan uji:
sumber
Perl 6 , 35 byte
Cobalah online!
Bagaimana itu bekerja
sumber
Pyth,
1716 byteCobalah online! (The
y.v
pada akhirnya adalah untuk pemanggilan fungsi)17 byte asli:
Cobalah online! (The
y.v
pada akhirnya adalah untuk pemanggilan fungsi)(Saya benar-benar menjawab pertanyaan itu dengan program Pyth ini.)
sumber
u
mungkin lebih pendek dari rekursi yang sebenarnya.Pyke, 11 byte (tidak bersaing)
Ini menggunakan perilaku baru di mana jika ada pengecualian yang muncul setelah goto, ia mengembalikan keadaan dari sebelum goto (kecuali definisi variabel) dan berlanjut. Dalam hal ini setara dengan kode python berikut:
Ini semua dimungkinkan menggunakan Pyke tanpa konstruksi loop sementara - yay goto!
Coba di sini!
sumber
JavaScript (ES6),
7054 bytePenerapan rumus rekursif yang disediakan, tetapi sekarang diperbarui untuk menggunakan rekursi untuk menemukan pembagi juga.
sumber
Perl, 57 +1 (
-p
bendera) = 58 bytePemakaian:
Tidak Disatukan:
sumber
Clojure,
9896 bytegunakan
for
:when
untuk menemukan pembagi terbesar, loop sampai tidak ada nilai lebih besar dari yang ditemukan.sumber