Pertimbangkan kekuatan bilangan bulat positif lima dalam desimal. Berikut adalah 25 pertama, selaras kanan:
X 5^X
1 5
2 25
3 125
4 625
5 3125
6 15625
7 78125
8 390625
9 1953125
10 9765625
11 48828125
12 244140625
13 1220703125
14 6103515625
15 30517578125
16 152587890625
17 762939453125
18 3814697265625
19 19073486328125
20 95367431640625
21 476837158203125
22 2384185791015625
23 11920928955078125
24 59604644775390625
25 298023223876953125
Perhatikan bahwa kolom paling kanan dari kekuasaan adalah semua 5
. Kolom kedua dari kanan adalah milik semua 2
. Kolom ketiga dari kanan, dibaca dari atas ke bawah, bergantian 1
, 6
, 1
, 6
, dll kolom berikutnya dimulai 3
, 5
, 8
, 0
dan kemudian siklus.
Bahkan, setiap kolom (jika kita turun cukup jauh) memiliki urutan siklus digit yang panjangnya dua kali lipat dari siklus sebelumnya, kecuali untuk siklus awal 5
dan 2
siklus itu.
Memanggil N nomor kolom, dimulai dengan N = 1 di sebelah kanan, beberapa siklus pertama adalah:
N cycle at column N
1 5
2 2
3 16
4 3580
5 17956240
6 3978175584236200
7 19840377976181556439582242163600
8 4420183983595778219796176036355599756384380402237642416215818000
Tantangan
Dengan bilangan bulat positif N, hasilkan digit desimal dari siklus pada kolom N, seperti dijelaskan di atas. Sebagai contoh, output untuk N = 4 adalah 3580
.
Digit dapat berupa output seperti daftar [3, 5, 8, 0]
atau dalam format lain yang wajar selama:
- Angka-angka itu agar dibaca dari atas ke bawah di kolom daya. mis
0853
. tidak valid. - Siklus dimulai dengan angka teratas di kolom kekuatannya. mis.
5803
tidak valid karena kolom ke-4 dimulai dengan3
tidak5
. - Persis satu siklus adalah output. misalnya
358
atau35803
atau35803580
semua akan menjadi tidak valid.
Kode Anda harus bekerja setidaknya untuk N = 1 hingga 30.
Jika diinginkan Anda dapat menganggap kolom-kolom tersebut diindeks 0 bukannya 1 diindeks. Jadi N = 0 memberi 5
, N = 1 memberi 2
, N = 2 memberi 16
, N = 3 memberi 3580
, dll.
Kode terpendek dalam byte menang .
Terima kasih kepada Downgoat dan DJ untuk dukungan tantangan.
2^(N-2)
kecualiN = 1
Jawaban:
Python 2,
626158 byteBerbasis nol. Saya berasumsi akhiran L dapat diterima.
Keluaran:
Solusi sebelumnya:
Penjelasan:
The
range(2**n/2)
menggunakan pengamatan bahwa setiap siklus memiliki panjang r = 2 n-1 kecuali ketika n = 0, jadi kami hanya menghitung n-th digit selama 5 m sampai 5 m + r - 1 .Awal siklus 5 m adalah angka pertama yang lebih besar dari 10 n . Memecahkan 5 m ≥ 10 n memberi m ≥ n / log 10 5. Di sini kami memperkirakan log 10 5 ≈ 0,7 yang akan rusak ketika n = 72. Kita bisa menambahkan lebih banyak digit untuk meningkatkan akurasi:
Di
/ 10**n % 10
dalam loop cukup mengekstrak digit yang diinginkan. Solusi alternatif lain menggunakan manipulasi string. Saya menggunakan trik di~n == -n-1
sini untuk menghapus 1 byte.Disebutkan dalam komentar, ungkapan
5**(m+i) / 10**n
lebih lanjut dapat disederhanakan dengan cara ini, yang memberikan jawaban 58 byte saat ini.(Pembagian
x/2**n
dapat dilakukan menggunakan bitwise-shift kananx>>n
. Sayangnya, karena operator Python lebih diutamakan, ini tidak menghemat byte.) Fraksi 3/7 juga dapat ditingkatkan dalam mannar serupa:sumber
(5**(n*3/7-~i)>>n)%10
. Karena Anda mengambil kekuatan 5 dibagi dengan kekuatan (lebih kecil) dari 10, Anda dapat mengurangi kekuatan 5, dan bergeser ke kanan.n/.7 - n
→n*10/7 - n
→n*3/7
. Pada prinsipnya, ini mengekstraksi digit dari kekuatan terkecil 5 lebih besar dari 2ⁿ (dengan 3/7 perkiraan untuk 1 / log₂ (5) ). Selain itu, menggunakanrange(2**n/2or 1)
gantinya akan memberi Anda output yang konsisten.(x>>n)%10
tidak memberikan perbaikan atasx/2**n%10
jadi saya tidak menggunakan bit shift untuk saat ini, karena mungkin ada cara untuk faktor yang umum2**n
.2**n
, tampaknya sedikit lebih lama:int(5**(-~i-n*log(2,5)%1))%10
(Saya sudah disederhanakanint(n*log(2,5))-n*log(2,5)
sebagai-(n*log(2,5)%1)
).2**n
argumen di sini dan rentang.dc , 72 byte
Pengindeksan berbasis 0.
Ini menggunakan aritmatika integer yang tepat - tidak ada perkiraan logaritma. Ini akan bekerja hingga kapasitas memori komputer.
Coba program dc online!
Kode dc dapat diubah menjadi solusi Bash:
Utilitas Bash + GNU,
967775 byteCoba versi Bash online!
sumber
Mathematica,
666052 byteFungsi anonim, diindeks 0. Menggunakan perkiraan log5 (10) (≈ 0.7)
Bagaimana itu bekerja?
Ambil lebih besar dari 2 ^ (input) / 2 dan 1. Hasilkan {1..that number}
Tambahkan input / .7
Naikkan 5 pangkat hasil (menghasilkan pangkat 5), bagi dengan 10 ^ input (singkirkan angka di sebelah kanan kolom yang diinginkan)
Terapkan modulo 10, ambil digit seseorang (kolom yang diinginkan).
Versi yang tepat, 58 byte
sumber
JavaScript (ES7),
7876 byte0-diindeks, yaitu
f(0)
memberi2
.Cuplikan tes
Tampilkan cuplikan kode
Cuplikan menggunakan
Math.pow
alih-alih**
untuk kompatibilitas lintas-browser.sumber
CJam, 35
Cobalah online
Ini hemat ruang dan tidak terlalu lambat, butuh beberapa menit untuk input 30 di komputer saya (menggunakan penerjemah java).
sumber
Jelly ,
2621 byte-2 byte menggunakan ide aproksimasi 0.7 kennytm
Cobalah online! (waktu habis untuk n> 15 )
Mengembalikan daftar bilangan bulat, digit.
Berbasis nol. Secara teoritis bekerja untuk n <= 72 (ganti
.7
dengan5l⁵¤
, untuk mendapatkan akurasi floating point).Bagaimana?
Lokal: memori set yang berfungsi untuk n = 17 naik ke sekitar 750MB kemudian melonjak menjadi sekitar 1GB ; untuk n = 18 perlahan-lahan mencapai 2.5GB kemudian melonjak menjadi sekitar 5GB .
sumber
Perl 6 , 52 byte
Berfungsi untuk input tinggi yang sewenang-wenang, mengingat memori yang cukup (mis. Tidak ada perkiraan logaritma) .
Mengembalikan daftar digit.
Cobalah online!
Bagaimana itu bekerja
Bagian "elemen melewatkan" berfungsi seperti ini:
//
adalah operator "didefinisikan atau".|()
mengembalikan Slip kosong , yang larut ke daftar luar sebagai 0 elemen, pada dasarnya memastikan bahwa elemen saat ini dilewati.Kasus tepi
n=1
bekerja dengan baik, karena2**n/4
menjadi0.5
, dan^(0.5)
berarti0 ..^ 0.5
alias "bilangan bulat antara 0 (inklusif) dan 0,5 (tidak inklusif)", yaitu daftar dengan elemen tunggal 0.sumber
J, 50 byte
Catatan: harus melewati nomor yang diperpanjang
Pemakaian:
sumber
Haskell , 73 byte
Cobalah online! Menggunakan pengindeksan 0.
Penjelasan:
sumber
Batch, 294 byte
Output setiap digit pada barisnya sendiri. Bekerja dengan menghitung kekuatan 5 tangan, tetapi hanya bekerja hingga
N=33
karena menggunakan bilangan bulat 32-bit untuk menghitung berapa banyak digit untuk dicetak.s
berisi (terbalik)N
digit terakhir dari kekuatan saat ini dari 5, sementara itut
berisix
s digunakan sebagai bantalan, meskipunx=0
membuat mereka mengevaluasi sebagai nol ketika kekuatan berikutnya dihitung. Contoh untukN=4
:sumber
JavaScript (ES6), 73 byte
1-diindeks. Sedikit lebih pendek dari jawaban ES7 , tetapi gagal 3 langkah sebelumnya (pada N = 13).
Demo
Tampilkan cuplikan kode
sumber
PHP> = 7.1, 104 Bytes
PHP Sandbox Online
sumber