Lubię myśleć o liczbie 10-adycznej jako liczbie, która idzie nieskończenie w lewo, lub o liczbach całkowitych o bardzo dużej potędze 10.

Rzeczy przenoszą się nieskończenie w lewo i znikają. Aby zobaczyć, co mam na myśli, zauważ, że ...6667 * 3 = 1w krainie 10-adycznej, ponieważ „2”, które prowadzi w lewo, przechodzi w nieskończoność.

Dodawanie i mnożenie ma sens dla liczb 10-adycznych, ponieważ ostatnie ncyfry sumy / iloczynu zależą tylko od ostatnich ncyfr sum / mnożników.

Biorąc pod uwagę n, musisz wydrukować ostatnie ncyfry 10-adicowego pierwiastka sześcianu z 3, czyli xsatysfakcjonujące x*x*x = 3.

Kończy się:

...878683312291648481630318492665160423850087895134587

Twój kod musi zostać zakończony n=1000przed przesłaniem.

Powiedzmy, że jeśli liczba, którą chcesz wydrukować, zaczyna się od zera, to nie musisz drukować zer wiodących, ponieważ tak naprawdę nie jest to sens drukowania dodatkowych zer.

To jest golf golfowy . Najkrótsza odpowiedź w bajtach wygrywa.

Python 2 , 33 bajty

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

Wypróbuj online!

powFunkcja efektywnie oblicza modułową wykładnik 3**(10**k*2/3+1)%10**k.

Jesteśmy proszeni o znalezienie rozwiązania r**3 = 3 (mod 10**k). Chcemy znaleźć wykładnik, edla którego mapa x -> x**ejest odwrotna do x -> x**3działającego modu tworzenia kostek 10**k, podobnie jak wykładniki dekodowania i szyfrowania w RSA anulują się, aby uzyskać oryginalną wartość. Oznacza to, że (x**3)**e = x (mod 10**k)dla wszystkich x. (Założymy się przez cały czas gcd(x,10) = 1.) Następnie możemy wyzdrowieć r, odwracając kostkę, aby uzyskać r = 3**e (mod 10**k).

Rozwijamy się (r**3)**e = r (mod 10**k), rozumiemy

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

Szukamy wykładnika, 3*e-1który gwarantuje nam zwielokrotnienie liczby kopii 1.

Modulo mnożenia 10**ktworzy grupę dla liczb odwracalnych, czyli tych z gcd(x,10) = 1. Według Twierdzenia Lagrange'a, x**c = 1gdzie cjest liczba elementów w grupie. W przypadku modułu grupowego Nliczba ta jest wartością φ(N)całkowitą Eulera , a liczba wartości od 1do Njest względnie pierwsza N. Więc mamy r**φ(10**k) = 1 (mod 10**k). Dlatego wystarczy 3*e-1być wielokrotnością φ(10**k).

Obliczamy

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

Chcemy 3*e-1być wielokrotnością4 * 10**(k-1)

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

Możliwych jest wiele wyborów r, ale r=5daje to krótkie wyrażenie

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

z eliczbą całkowitą. Trochę gry w golfa za pomocą podziału podłogi skraca esię 10**k*2/3+1, a wyrażanie r = 3**e (mod 10**k)daje pożądany rezultat r.

Python 2 (PyPy) , 55 50 bajtów

-5 bajtów dzięki @HP Wiz !

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

Wypróbuj online!

Oblicza (nie brutalnie) cyfra po cyfrze, więc jest szybsza niż brutalna siła.

Wersja bez exec

Wyjaśnienie

(Dzięki @Leaky Nun i @ user202729 za zrozumienie tego)

Najpierw zauważ, że n**3jest to moduł inwolucji 10 (tzn. Jeśli funkcja zostanie wywołana f, to f(f(n)) == n). Można to potwierdzić za pomocą wyczerpującego wyszukiwania.

Możemy użyć indukcji matematycznej, aby znaleźć następną cyfrę.
Niech będzie trzecią cyfrą liczby (od prawej).dnn

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

Załóżmy, że znamy liczbę aż do kcyfry 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 ) (ekspansja dwumianowa.)
(Zauważ, że pozostałe dwa warunki można zignorować, ponieważ są to 0 mod 10 k + 1 )
3 · d k + 1 x 2 · 10 k + x 3 ≡ 3 (mod 10 k + 1 )

Wiemy to:

       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 )

Podstawiając to w:

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 jest odwrotnością 7 mod 10)

Wolfram Language (Mathematica) , 21 bajtów

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

Wypróbuj online!

05AB1E , 17 13 bajtów

7IGD3mN°÷7*θì

Port odpowiedzi @ Python 2 (PyPy) tylko dla ASCII .
-4 bajtów i bug-ustalony dla wyjść z zerem na początku, dzięki @Emigna , zastępując T%N°*+z θì.

Wypróbuj online.

Wyjaśnienie:

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 bajtów

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 odpowiedzi @ Python 2 (PyPy) tylko dla ASCII .
-2 bajty dzięki @Neil .
-20 bajtów dzięki tylko @ ASCII .

UWAGA: Odpowiedź Javy na @ OlivierGrégoire jest już znacznie krótsza przy użyciu algorytmu modPow.

Wypróbuj online.

Wyjaśnienie:

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 bajtów

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

Wypróbuj online!

Kredyty

• Odpowiedź portu Python 2 na port xnor .
• -6 bajtów dzięki Kevin Cruijssen

dc , 15

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

Wykorzystuje potęgowanie modułowe, takie jak odpowiedź @ xnor .

Wypróbuj online!

TIO oblicza dane wejściowe = 1000 w 21s.

Pyth , 12

.^3h/y^TQ3^T

Wypróbuj online!

Ponownie, stosując modułowe potęgowanie, jak odpowiedź @ xnor .

Haskell , 37 bajtów

1 bajt zapisany dzięki tylko ASCII!

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

Wypróbuj online!

Używam podobnego podejścia do ASCII, ale unikam dzielenia

Pyth , 23 bajty

Oczywiście wykorzystuje to podejście tylko ASCII.

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

Wypróbuj tutaj!

Węgiel drzewny , 26 22 bajtów

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

Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:

≔⁷η

Zainicjuj wynik na 7. (Nie musi to być 7, ale 0 nie działa.)

ＦＮ

Zapętlaj liczbę wymaganych cyfr.

        η       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.

Teraz wykorzystuje podejście @ HPWiz do zapisania 4 bajtów.

Ｉη

Wydrukuj wynik.

Oto 28-bajtowa wersja brute-force, która bierze pierwiastki z dowolnych wartości:

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

Wypróbuj online! Link jest do pełnej wersji kodu. Pierwsze wejście to liczba cyfr, drugie to wartość do zrootowania.

J , 33 bajty

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

TIO

port @ ASCII tylko na odpowiedź , ale stosując stałe modulo 10 ^ n całym

Galaretka , 23 18 17 bajtów

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

Wypróbuj online!

Wiem, ƒże się przyda.