Me gusta pensar en un número de 10 adic como un número que va infinitamente a la izquierda, o un módulo entero con una potencia muy grande de 10.

Las cosas se llevan infinitamente a la izquierda y se desvanecen. Para ver lo que quiero decir, tenga ...6667 * 3 = 1en cuenta que en la tierra de 10 adictos, ya que el "2" que lleva a la izquierda va al infinito.

La suma y la multiplicación tienen sentido para los números de 10 adic, ya que los últimos ndígitos de la suma / producto solo dependen de los últimos ndígitos de los sumandos / multiplicandos.

Dado n, debe imprimir los últimos ndígitos de la raíz cúbica de 10 adic de 3, es decir, xsatisfactorio x*x*x = 3.

Termina:

...878683312291648481630318492665160423850087895134587

Su código debe terminar n=1000antes del envío.

Digamos que si el número que necesita imprimir comienza con cero, entonces no necesita imprimir los ceros iniciales, ya que en realidad no es el punto para imprimir ceros adicionales.

Este es el código de golf . La respuesta más corta en bytes gana.

Python 2 , 33 bytes

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

Pruébalo en línea!

La powfunción calcula eficientemente el exponente modular 3**(10**k*2/3+1)%10**k.

Se nos pide encontrar una solución para r**3 = 3 (mod 10**k). Queremos encontrar un exponente epara el que el mapa x -> x**esea ​​inverso a la x -> x**3modificación del funcionamiento en cubos 10**k, al igual que los exponentes de descifrado y cifrado en RSA se cancelan para producir el valor original. Esto significa que (x**3)**e = x (mod 10**k)para todos x. (Asumiremos a lo largo de eso gcd(x,10) = 1). Entonces, podemos recuperar rinvirtiendo el cubo para obtener r = 3**e (mod 10**k).

Expandiéndonos (r**3)**e = r (mod 10**k), obtenemos

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

Estamos buscando un exponente 3*e-1que garantice la multiplicación que tantas copias nos da 1.

El módulo de multiplicación 10**kforma un grupo para números invertibles, es decir, aquellos con gcd(x,10) = 1. Por el teorema de Lagrange, x**c = 1donde cestá la cuenta de elementos en el grupo. Para el módulo de grupo N, ese recuento es el valor total de Euler φ(N), el número de valores de 1a Nque son relativamente primos N. Entonces, tenemos r**φ(10**k) = 1 (mod 10**k). Por lo tanto, es suficiente para 3*e-1ser un múltiplo de φ(10**k).

Calculamos

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

Entonces, queremos 3*e-1ser un múltiplo de4 * 10**(k-1)

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

Son posibles muchas opciones r, pero r=5da la breve expresión

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

con eun número entero Un poco de golf usando acorta suelo de división ea 10**k*2/3+1, y expresando r = 3**e (mod 10**k)da el resultado deseado r.

Python 2 (PyPy) , 55 50 bytes

-5 bytes gracias a @HP Wiz !

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

Pruébalo en línea!

Calcula (sin fuerza bruta) dígito por dígito, por lo que es más rápido que la fuerza bruta.

Versión sin ejecutivo

Explicación

(Gracias @Leaky Nun y @ user202729 por resolver esto)

Primero, observe que n**3es un módulo de involución 10 (es decir, si se llama a la función f, entonces f(f(n)) == n). Esto se puede confirmar mediante una búsqueda exhaustiva.

Podemos usar la inducción matemática para encontrar el siguiente dígito.
Deje ser el dígito th del número (desde la derecha).dnn

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

Ahora, supongamos que sabemos el número hasta el kdígito 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 ) (Expansión binomial).
(Tenga en cuenta que los otros dos términos pueden ignorarse ya que son 0 mod 10 k + 1 )
3 · d k + 1 x 2 · 10 k + x 3 ≡ 3 (mod 10 k + 1 )

Lo sabemos:

       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 )

Sustituyendo esto en:

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 es el inverso de 7 mod 10)

Wolfram Language (Mathematica) , 21 bytes

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

Pruébalo en línea!

05AB1E , 17 13 bytes

7IGD3mN°÷7*θì

Puerto de la respuesta de Python 2 (PyPy) de @ ASCII-only .
-4 bytes Y corrección de errores para salidas con ceros iniciales gracias a @Emigna , reemplazando T%N°*+con θì.

Pruébalo en línea.

Explicación:

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 bytes

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;}

Puerto de la respuesta de Python 2 (PyPy) de @ ASCII-only .
-2 bytes gracias a @Neil .
-20 bytes gracias a @ ASCII-only .

NOTA: @ OlivierGrégoire ya cuenta con una respuesta Java mucho más corta que utiliza un enfoque algorítmico modPow.

Pruébalo en línea.

Explicación:

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 bytes

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

Pruébalo en línea!

Créditos

• Port of xnor's Python 2 respuesta .
• -6 bytes gracias a Kevin Cruijssen

corriente continua , 15

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

Utiliza exponenciación modular, como la respuesta de @ xnor .

Pruébalo en línea!

TIO calcula input = 1000 en 21s.

Pyth , 12

.^3h/y^TQ3^T

Pruébalo en línea!

Nuevamente, usando exponenciación modular, como la respuesta de @ xnor .

Haskell , 37 bytes

¡1 byte guardado gracias a ASCII-only!

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

Pruébalo en línea!

Utilizo un enfoque similar al ASCII solo, pero evito usar la división

Pyth , 23 bytes

Por supuesto, esto utiliza el enfoque de ASCII solamente.

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

Pruébalo aquí!

Carbón , 26 22 bytes

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

Pruébalo en línea! El enlace es a la versión detallada del código. Explicación:

≔⁷η

Inicialice el resultado a 7. (No tiene que ser 7, pero 0 no funciona).

ＦＮ

Pase el número de dígitos requeridos.

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

Ahora usa el enfoque de @ HPWiz para guardar 4 bytes.

Ｉη

Imprime el resultado.

Aquí hay una versión de fuerza bruta de 28 bytes que toma raíces cúbicas de valores arbitrarios:

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

Pruébalo en línea! El enlace es a la versión detallada del código. La primera entrada es el número de dígitos, la segunda es el valor de la raíz.

J , 33 bytes

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

TIO

puerto de la respuesta de @ ASCII-only pero usando un módulo fijo 10 ^ n en todo

Gelatina , 23 18 17 bytes

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

Pruébalo en línea!

Sé ƒque será útil.