Saya suka menganggap angka 10-adic sebagai angka yang bergerak tak terhingga ke kiri, atau modul integer dengan kekuatan 10 yang sangat besar.

Benda-benda terbawa tanpa batas ke kiri dan menghilang. Untuk melihat apa yang saya maksud, perhatikan itu...6667 * 3 = 1 di tanah 10-adic, karena "2" yang membawa ke kiri pergi hingga tak terbatas.

Penambahan dan penggandaan masuk akal untuk angka 10-adic, karena ndigit terakhir dari jumlah / produk hanya bergantung pada ndigit terakhir dari jumlah / multiplikasi.

Mengingat n, Anda perlu mencetak ndigit terakhir dari akar kubus 10-adic dari 3, yaitu xmemuaskanx*x*x = 3 .

Ini berakhir:

...878683312291648481630318492665160423850087895134587

Kode Anda harus diakhiri n=1000sebelum pengiriman.

Katakanlah jika angka yang Anda perlu cetak dimulai dengan nol, maka Anda tidak perlu mencetak angka nol di depannya, karena itu sebenarnya bukan titik untuk mencetak angka nol tambahan.

Ini adalah kode-golf . Jawaban terpendek dalam byte menang.

Python 2 , 33 byte

lambda k:pow(3,10**k*2/3+1,10**k)

Cobalah online!

The powFungsi efisien menghitung eksponen modular 3**(10**k*2/3+1)%10**k.

Kami diminta untuk menemukan solusi r**3 = 3 (mod 10**k). Kami ingin menemukan eksponen eyang petanya x -> x**eterbalik dengan cubing x -> x**3working mod 10**k, sama seperti eksponen dekripsi dan enkripsi di RSA yang dibatalkan untuk menghasilkan nilai asli. Ini artinya (x**3)**e = x (mod 10**k)untuk semua x. (Kita akan mengasumsikan sepanjang itu gcd(x,10) = 1.) Lalu, kita bisa pulih rdengan membalikkan cubing untuk mendapatkannya r = 3**e (mod 10**k).

Memperluas (r**3)**e = r (mod 10**k), kita dapatkan

r**(3*e-1) = 1 (mod 10**k)

Kami sedang mencari eksponen 3*e-1yang menjamin bahwa melipatgandakan banyak salinan memberi kami 1.

Modulo perkalian 10**kmembentuk grup untuk angka yang dapat dibalik, yaitu mereka yang memiliki gcd(x,10) = 1. Dengan Lagrange's Theorem, di x**c = 1mana cadalah jumlah elemen dalam grup. Untuk modulo grup N, penghitungan itu adalah nilai total Euler φ(N), jumlah nilai dari 1hingga Nyang relatif prima N. Jadi, sudah r**φ(10**k) = 1 (mod 10**k). Oleh karena itu, cukup untuk 3*e-1menjadi kelipatan φ(10**k).

Kami menghitung

φ(10**k) = φ(5**k) φ(2**k)= 4 * 5**(k-1) * 2**(k-1) = 4 * 10**(k-1)`

Jadi, kami ingin 3*e-1menjadi kelipatan4 * 10**(k-1)

3*e - 1 = r * 4 * 10**(k-1)
e = (4r * 10**(k-1) + 1)/3

Banyak pilihan yang dimungkinkan r, tetapi r=5memberikan ekspresi singkat

e = (2 * 10**k + 1)/3

dengan enomor keseluruhan. Sebuah golf kecil menggunakan memendek lantai-divisi euntuk 10**k*2/3+1, dan mengekspresikan r = 3**e (mod 10**k)memberikan hasil yang diinginkan r.

Python 2 (PyPy) , 55 50 byte

-5 byte terima kasih kepada @ HP Wiz !

n=p=1;exec"p*=10;n+=3*(3-n**3)%p;"*input();print n

Cobalah online!

Menghitung (non-bruteforcing) digit demi digit, jadi lebih cepat dari brute force.

Versi tanpa exec

Penjelasan

(Terima kasih @Leaky Nun dan @ user202729 untuk mencari tahu ini)

Pertama, amati bahwa itu n**3adalah involusi modulo 10 (yaitu jika fungsinya disebut f, maka f(f(n)) == n). Ini dapat dikonfirmasi menggunakan pencarian lengkap.

Kita dapat menggunakan induksi matematika untuk menemukan digit berikutnya.
Membiarkan menjadi digit nomor urut (dari kanan).dnn

d 1 3 ≡ 3 (mod 10)
 d 1 ≡ 3 3 (mod 10)
    ≡ 27 (mod 10)
    ≡ 7 (mod 10)

Sekarang, anggap kita tahu nomornya hingga kdigit ke th,x

              x 3 ≡ 3 (mod 10 k )
  (d k + 1 · 10 k + x) 3 ≡ 3 (mod 10 k + 1 )
3 · d k + 1 x 2 · 10 k + x 3 ≡ 3 (mod 10 k + 1 ) (ekspansi binomial.)
(Perhatikan bahwa dua istilah lainnya dapat diabaikan karena mereka adalah 0 mod 10 k + 1 )
3 · d k + 1 x 2 · 10 k + x 3 ≡ 3 (mod 10 k + 1 )

Kita tahu itu:

       x ≡ 7 (mod 10)
      x 2 ≡ 49 (mod 10)
         ≡ 9 (mod 10)
  x 2 · 10 k ≡ 9 · 10 k   (mod 10 k + 1 )
3 · x 2 · 10 k ≡ 27 · 10 k (mod 10 k + 1 )
         ≡ 7 · 10 k   (mod 10 k + 1 )

Mengganti ini dalam:

3 · d k + 1 x 2 · 10 k + x 3 ≡ 3 (mod 10 k + 1 )
  7 · d k + 1 · 10 k + x 3 ≡ 3 (mod 10 k + 1 )
             d k + 1 ≡ (3 - x 3 ) ÷ (7 · 10 k ) (mod 10)
                 ≡ (3 - x 3 ) ÷ (7 · 10 k ) (mod 10)
           ∴ d k + 1 ≡ 3 · (3 - x 3 ) ÷ 10 k    (mod 10) (3 adalah kebalikan dari 7 mod 10)

Bahasa Wolfram (Mathematica) , 21 byte

PowerMod[3,1/3,10^#]&

Cobalah online!

05AB1E , 17 13 byte

7IGD3mN°÷7*θì

Port of @ ASCII-only Python 2 (PyPy) menjawab .
-4 byte DAN bug-diperbaiki untuk output dengan nol terkemuka berkat @ Emigna , dengan mengganti T%N°*+dengan θì.

Cobalah online.

Penjelasan:

7               # Start result-string `r` at '7'
IG              # Loop `N` in the range [1, input)
  D3m           #  `r` to the power 3
       ÷        #  Integer-divided with
     N°         #  10 to the power `N`
        7*      #  Multiplied by 7
          θì    #  Then take the last digit of this, and prepend it to the result `r`
                # Implicitly output result `r` after the loop

Java 8, 158 156 141 136 135 byte

n->{var t=n.valueOf(3);var r=n.ONE;for(int i=0;i++<n.intValue();)r=r.add(t.subtract(r.pow(3)).multiply(t).mod(n.TEN.pow(i)));return r;}

Port of @ ASCII-only Python 2 (PyPy) menjawab .
-2 byte terima kasih kepada @Neil .
-20 byte berkat hanya @ ASCII .

CATATAN: Sudah ada jawaban Java yang jauh lebih pendek oleh @ OlivierGrégoire menggunakan pendekatan algoritmik modPow.

Cobalah online.

Penjelasan:

n->{                            // Method with BigInteger as both parameter and return-type
  var t=n.valueOf(3);           //  Temp BigInteger with value 3
  var r=n.ONE;                  //  Result-BigInteger, starting at 1
  for(int i=0;i++<n.intValue();)//  Loop `i` in the range [1, n]
    r=r.add(                    //   Add to the result-BigDecimal:
       t.subtract(r.pow(3))     //    `t` subtracted with `r` to the power 3
       .multiply(t)             //    Multiplied by 3
       .mod(n.TEN.pow(i)));     //    Modulo by 10 to the power `i`
  return r;}                    //  Return the result-BigInteger

Java (JDK 10) , 106 byte

n->n.valueOf(3).modPow(n.valueOf(2).multiply(n=n.TEN.pow(n.intValue())).divide(n.valueOf(3)).add(n.ONE),n)

Cobalah online!

Kredit

• Pelabuhan xnor's Python 2 menjawab .
• -6 byte terima kasih kepada Kevin Cruijssen

dc , 15

3?Ar^d2*3/1+r|p

Menggunakan eksponensial modular, seperti jawaban @ xnor .

Cobalah online!

TIO menghitung input = 1000 dalam 21d.

Pyth , 12

.^3h/y^TQ3^T

Cobalah online!

Sekali lagi, menggunakan eksponensial modular, seperti jawaban @ xnor .

Haskell , 37 byte

1 byte disimpan berkat ASCII-only!

(10!1!!)
n!x=x:(n*10)!mod(9-3*x^3+x)n

Cobalah online!

Saya menggunakan pendekatan yang mirip dengan ASCII saja, tetapi saya menghindari menggunakan divisi

Pyth , 23 byte

Tentu saja, ini menggunakan pendekatan ASCII saja.

K7em=+K*%*7/^K3J^TdTJtU

Coba di sini!

Arang , 26 22 byte

≔⁷ηＦＮ≧⁺﹪׳⁻³Ｘη³Ｘχ⊕ιηＩη

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Penjelasan:

≔⁷η

Inisialisasi hasilnya menjadi 7. (Tidak harus menjadi 7, tetapi 0 tidak berfungsi.)

ＦＮ

Ulangi jumlah digit yang diperlukan.

        η       Current result.
       Ｘ ³     Take the cube. 
     ⁻³         Subtract from 3.
   ׳           Multiply by 3.
            ⊕ι  Increment the loop index.
          Ｘχ    Get that power of 10.
  ﹪             Modulo
≧⁺            η Add to the result.

Sekarang menggunakan pendekatan @ HPWiz untuk menghemat 4 byte.

Ｉη

Cetak hasilnya.

Berikut ini adalah versi brute-force 28-byte yang mengambil akar pangkat tiga dari nilai arbitrer:

ＦＮ⊞υ⊟Φχ¬﹪⁻ＸＩ⁺κ⭆⮌υμ³ＩηＸχ⊕ι↓Ｉυ

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Input pertama adalah jumlah digit, kedua adalah nilai untuk di-root.

J , 33 byte

f=:3 :'((10x^y)|]+3*3-^&3)^:y 1x'

TIO

port jawaban @ ASCII saja tetapi menggunakan modulo tetap 10 ^ n seluruh

Jelly , 23 18 17 byte

*3:×7DṪ×+⁸
R⁵*çƒ7

Cobalah online!

Saya tahu ƒakan bermanfaat.