5, 2, 16, 3580, Apa yang terjadi selanjutnya?

51

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, 0dan 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 5dan 2siklus 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. 5803tidak valid karena kolom ke-4 dimulai dengan 3tidak 5.
  • Persis satu siklus adalah output. misalnya 358atau 35803atau 35803580semua 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.

Hobi Calvin
sumber
Perintah membuat ini sangat rumit.
Dennis
9
Panjang siklus selalu 2^(N-2)kecualiN = 1
JungHwan Min
1
Bisakah perkiraan digunakan? Outputnya valid hingga N = 72 , yang secara teoritis akan mencetak 2,36E + 21 digit.
JungHwan Min
Apakah urutan ini ada dalam OEIS?
StarWeaver
@StarWeaver Tidak.
Mego

Jawaban:

26

Python 2, 62 61 58 byte

Berbasis nol. Saya berasumsi akhiran L dapat diterima.

lambda n:[5**(n*3/7-~i)/2**n%10for i in range(2**n/2or 1)]

Keluaran:

0 [5]
1 [2]
2 [1, 6]
3 [3, 5, 8, 0]
4 [1, 7, 9, 5, 6, 2, 4, 0]
5 [3, 9, 7, 8, 1, 7, 5, 5, 8, 4, 2, 3, 6, 2, 0, 0]
6 [1, 9, 8, 4, 0, 3, 7, 7, 9, 7, 6, 1, 8, 1, 5, 5, 6, 4, 3, 9, 5, 8, 2, 2, 4, 2L, 1L, 6L, 3
L, 6L, 0L, 0L]
7 [4, 4, 2, 0, 1, 8, 3, 9, 8, 3, 5, 9, 5, 7, 7, 8, 2, 1, 9, 7, 9, 6, 1, 7, 6L, 0L, 3L, 6L,
3L, 5L, 5L, 5L, 9L, 9L, 7L, 5L, 6L, 3L, 8L, 4L, 3L, 8L, 0L, 4L, 0L, 2L, 2L, 3L, 7L, 6L, 4L,
 2L, 4L, 1L, 6L, 2L, 1L, 5L, 8L, 1L, 8L, 0L, 0L, 0L]

Solusi sebelumnya:

lambda n:[5**int(n/.7-~i)/10**n%10for i in range(2**n/2or 1)]
lambda n:[str(5**int(n/.7-~i))[~n]for i in range(2**n/2)]or 5

Penjelasan:

def f(n):
    r = max(2**n / 2, 1)
    m = int(n/0.7 + 1)
    for i in range(r):
        yield (5**(m+i) / 10**n) % 10

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:

| approximation             | valid until        | penalty   |
|---------------------------|--------------------|-----------|
| .7                        | n = 72             | +0 bytes  |
| .699                      | n = 137            | +2 bytes  |
| .69897                    | n = 9297           | +4 bytes  |
| .698970004                | n = 29384          | +8 bytes  |
| .6989700043               | n = 128326         | +9 bytes  |
| .6989700043360189         | too large to check | +15 bytes |
| import math;math.log10(5) | same as above      | +23 bytes |

Di / 10**n % 10dalam 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**nlebih lanjut dapat disederhanakan dengan cara ini, yang memberikan jawaban 58 byte saat ini.

masukkan deskripsi gambar di sini

(Pembagian x/2**ndapat dilakukan menggunakan bitwise-shift kanan x>>n. Sayangnya, karena operator Python lebih diutamakan, ini tidak menghemat byte.) Fraksi 3/7 juga dapat ditingkatkan dalam mannar serupa:

| approximation                   | valid until         | penalty   |
|---------------------------------|---------------------|-----------|
| n*3/7                           | n = 72              | +0 bytes  |
| n*31/72                         | n = 137             | +2 bytes  |
| n*59/137                        | n = 476             | +3 bytes  |
| n*351/815                       | n = 1154            | +4 bytes  |
| n*643/1493                      | n = 10790           | +5 bytes  |
| n*8651/20087                    | n = 49471           | +7 bytes  |
| int(n*.43067655807339306)       | too large to check  | +20 bytes |
| import math;int(n/math.log2(5)) | same as above       | +26 bytes |
kennytm
sumber
1
(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 - nn*10/7 - nn*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, menggunakan range(2**n/2or 1)gantinya akan memberi Anda output yang konsisten.
primo
1
@primo Terima kasih, diperbarui. (x>>n)%10tidak memberikan perbaikan atas x/2**n%10jadi saya tidak menggunakan bit shift untuk saat ini, karena mungkin ada cara untuk faktor yang umum 2**n.
kennytm
ide menarik yang keluar 2**n, tampaknya sedikit lebih lama: int(5**(-~i-n*log(2,5)%1))%10(Saya sudah disederhanakan int(n*log(2,5))-n*log(2,5)sebagai -(n*log(2,5)%1)).
Primo
@ Primo Menarik, tapi yang saya maksud adalah 2**nargumen di sini dan rentang.
kennytm
10

dc , 72 byte

[3Q]sq2?dsa^1+2/dsusk[Ola^/O%plk1-dsk1>q]sp1[d5r^dOla^<psz1+d4/lu>t]dstx

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, 96 77 75 byte

u=$[(2**$1+1)/2]
dc -e "[O$1^/O%p]sp1[d5r^dO$1^<psz1+d4/$u>t]dstx"|head -$u

Coba versi Bash online!

Mitchell Spector
sumber
9

Mathematica, 66 60 52 byte

Floor@Mod[5^Floor[Range@Max[2^#/2,1]+#/.7]/10^#,10]&

Fungsi anonim, diindeks 0. Menggunakan perkiraan log5 (10) (≈ 0.7)

Bagaimana itu bekerja?

Range@Max[2^#/2,1]

Ambil lebih besar dari 2 ^ (input) / 2 dan 1. Hasilkan {1..that number}

...+#/.7

Tambahkan input / .7

5^Floor[...]/10^#

Naikkan 5 pangkat hasil (menghasilkan pangkat 5), bagi dengan 10 ^ input (singkirkan angka di sebelah kanan kolom yang diinginkan)

Mod[ ...,10]

Terapkan modulo 10, ambil digit seseorang (kolom yang diinginkan).

Versi yang tepat, 58 byte

Floor@Mod[5^Floor[Range@Max[2^#/2,1]+#/5~Log~10]/10^#,10]&
JungHwan Min
sumber
5

JavaScript (ES7), 78 76 byte

f=(N,z=5,s,X=2**N,q=z/10**N|0)=>s|q?X>0?q+f(N,z*5%10**-~N,1,X-2):"":f(N,z*5)

0-diindeks, yaitu f(0)memberi 2.

Cuplikan tes

Cuplikan menggunakan Math.powalih-alih **untuk kompatibilitas lintas-browser.

Produksi ETH
sumber
4

CJam, 35

5ri(:N.7/i)#2N(#mo{_AN#/o5*AN)#%}*;

Cobalah online

Ini hemat ruang dan tidak terlalu lambat, butuh beberapa menit untuk input 30 di komputer saya (menggunakan penerjemah java).

aditsu
sumber
3

Jelly , 26 21 byte

-2 byte menggunakan ide aproksimasi 0.7 kennytm

2*HĊR+÷.7$Ḟ*@5:⁵*⁸¤%⁵

Cobalah online! (waktu habis untuk n> 15 )

Mengembalikan daftar bilangan bulat, digit.
Berbasis nol. Secara teoritis bekerja untuk n <= 72 (ganti .7dengan 5l⁵¤, untuk mendapatkan akurasi floating point).

Bagaimana?

2*HĊR+÷.7$Ḟ*@5:⁵*⁸¤%⁵ - Main link: n
2*                    - 2 raised to the power of n
  H                   - halved: 2 raised to the power of n-1
   Ċ                  - ceiling: adjust 2**-1 = 0.5 up to 1 for the n=0 edge case
    R                 - range: [1,2,...,ceiling(2**(n-1))] - has length of the period
         $            - last two links as a monad:
      ÷.7             -     divide by 0.7 (approximation of log(5, 10), valid up to n=72)
     +                - add (vectorises)
          Ḟ           - floor (vectorises)
             5        - 5
           *@         - exponentiate (vectorises) with reversed @arguments
                  ¤   - nilad followed by link(s) as a nilad
               ⁵      -     10
                 ⁸    -     left argument, n
                *     -     exponentiate: 10 raised to the power of n
              :       - integer division: strips off last n digits
                   %⁵ - mod 10: extracts the last digit

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 .

Jonathan Allan
sumber
3

Perl 6 , 52 byte

->\n{(map {.comb[*-n]//|()},(5 X**1..*))[^(2**n/4)]}

Berfungsi untuk input tinggi yang sewenang-wenang, mengingat memori yang cukup (mis. Tidak ada perkiraan logaritma) .
Mengembalikan daftar digit.

Cobalah online!

Bagaimana itu bekerja

->\n{                                              }  # A lambda with argument n.
                            (5 X**1..*)               # The sequence 5, 25, 125, 625...
      map {               },                          # Transform each element as such:
           .comb[*-n]                                 #   Extract the n'th last digit,
                     //|()                            #   or skip it if that doesn't exist.
     (                                 )[^(2**n/4)]   # Return the first 2^(n-2) elements.

Bagian "elemen melewatkan" berfungsi seperti ini:

  • Pengindeksan daftar pada indeks ilegal mengembalikan Kegagalan , yang dihitung sebagai nilai "tidak terdefinisi".
  • // 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=1bekerja dengan baik, karena 2**n/4menjadi 0.5, dan ^(0.5)berarti 0 ..^ 0.5alias "bilangan bulat antara 0 (inklusif) dan 0,5 (tidak inklusif)", yaitu daftar dengan elemen tunggal 0.

seseorang
sumber
2

J, 50 byte

(2^0>.2-~]){.' '-.~-{"1[:([:":[:|:[:,:5^[:>:i.)2^]

Catatan: harus melewati nomor yang diperpanjang

Pemakaian:

   q =: (2^0>.2-~]){.' '-.~-{"1[:([:":[:|:[:,:5^[:>:i.)2^]
   q 1x
5
   q 2x
2
   q 4x
3580
ljeabmreosn
sumber
2
mengapa downvote?
ljeabmreosn
2

Haskell , 73 byte

f 0="5"
f n=take(2^(n-1))[reverse x!!n|x<-show<$>iterate(*5)1,length x>n]

Cobalah online! Menggunakan pengindeksan 0.

Penjelasan:

f 0="5"              -- if the input is 0, return "5"
f n=                 -- otherwise for input n
  take(2^(n-1))      -- return the first 2^(n-1) elements of the list
    [reverse x!!n    -- of the nth column of x
      |x<-show<$>    --    where x is the string representation
        iterate(*5)1 --    of the elements of the infinite list [5,25,125,...]
      ,length x>n    -- if x has at least n+1 columns
    ]                -- this yields a list of characters, which is equivalent to a string
Laikoni
sumber
1

Batch, 294 byte

@echo off
if %1==1 echo 5
set/a"l=1<<%1-2,x=0,s=1
set t=
for /l %%i in (2,1,%1)do call set t=%%t%%x
:l
if %l%==0 exit/b
set t=%s%%t%
set s=
set c=
:d
set/ac+=%t:~,1%*5,r=c%%10,c/=10
set s=%s%%r%
set t=%t:~1%
if "%t%"=="" echo %r%&set/al-=1&goto l
if %c%%t:~,1%==0x goto l
goto d

Output setiap digit pada barisnya sendiri. Bekerja dengan menghitung kekuatan 5 tangan, tetapi hanya bekerja hingga N=33karena menggunakan bilangan bulat 32-bit untuk menghitung berapa banyak digit untuk dicetak. sberisi (terbalik) Ndigit terakhir dari kekuatan saat ini dari 5, sementara itu tberisi xs digunakan sebagai bantalan, meskipun x=0membuat mereka mengevaluasi sebagai nol ketika kekuatan berikutnya dihitung. Contoh untuk N=4:

s   t
1   xxx (initial values before the first power of 5 is calculated)
5   xxx
52  xx
521 x
526 x
5213    (print 3)
5265    (print 5)
5218    (print 8)
5260    (print 0)
Neil
sumber
1

JavaScript (ES6), 73 byte

1-diindeks. Sedikit lebih pendek dari jawaban ES7 , tetapi gagal 3 langkah sebelumnya (pada N = 13).

n=>(g=x=>k>>n?'':(s=''+x*5%1e15)[n-1]?s.substr(-n,1)+g(s,k+=4):g(s))(k=1)

Demo

Arnauld
sumber
0

PHP> = 7.1, 104 Bytes

for($s=1;$i++<2**(-1+$a=$argn);)~($s=bcmul($s,5))[-$a]?$g.=$s[-$a]:0;echo substr($g,0,max(2**($a-2),1));

PHP Sandbox Online

Jörg Hülsermann
sumber