Find the 10-adic cube root of 3

Question

I like to think of a 10-adic number as a number that goes infinitely to the left, or an integer modulo a very very large power of 10.

Things carry infinitely to the left and vanish. To see what I mean, note that ...6667 * 3 = 1 in the 10-adic land, since the "2" that carries to the left goes to infinity.

Addition and multiplication make sense for 10-adic numbers, since the last n digits of the sum/product only depend on the last n digits of the summands/multiplicands.

---

Given n, you need to print the last n digits of the 10-adic cube root of 3, i.e. x satisfiying x*x*x = 3.

It ends:

...878683312291648481630318492665160423850087895134587

---

Your code must terminate for n=1000 before submission.

Let's say that if the number you need to print begins with zero, then you don't need to print the leading zeroes, since it isn't actually the point to print extra zeroes.

---

This is code-golf. Shortest answer in bytes wins.

Answer 1

Python 2, 33 bytes

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

Try it online!

The pow function efficiently computes the modular exponent 3**(10**k*2/3+1)%10**k.

We're asked to find a solution to r**3 = 3 (mod 10**k). We want to find an exponent e for which the map x -> x**e is inverse to cubing x -> x**3 working mod 10**k, just as the decryption and encryption exponents in RSA cancel to produce the original value. This means that (x**3)**e = x (mod 10**k) for all x. (We'll assume throughout that gcd(x,10) = 1.) Then, we can recover r by inverting the cubing to get r = 3**e (mod 10**k).

Expanding out (r**3)**e = r (mod 10**k), we get

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

We're looking for an exponent 3*e-1 that guarantees that multiplying that many copies gives us 1.

Multiplication modulo 10**k forms a group for invertible numbers, that is those with gcd(x,10) = 1. By Lagrange's Theorem, x**c = 1 where c is the count of elements in the group. For the group modulo N, that count is the Euler totient value φ(N), the number of values from 1 to N that are relatively prime to N. So, we have r**φ(10**k) = 1 (mod 10**k). Therefore, its suffices for 3*e-1 to be a multiple of φ(10**k).

We compute

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

So, we want 3*e-1 to be a multiple of 4 * 10**(k-1)

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

Many choices are possible for r, but r=5 gives the short expression

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

with e a whole number. A little golfing using floor-division shortens e to 10**k*2/3+1, and expressing r = 3**e (mod 10**k) gives the desired result r.

Answer 2

Python 2 (PyPy), 55 50 bytes

-5 bytes thanks to @H.P. Wiz!

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

Try it online!

Calculates (non-bruteforcing) digit by digit, so it's faster than brute force.

Version without exec

Explanation

(Thanks @Leaky Nun and @user202729 for figuring this out)

First, observe that n**3 is an involution modulo 10 (i.e. if the function is called f, then f(f(n)) == n). This can be confirmed using an exhaustive search.

We can use mathematical induction to find the next digit.
Let dn be the nth digit of the number (from the right).

d13 ≡ 3  (mod 10)
 d1 ≡ 33 (mod 10)
    ≡ 27 (mod 10)
    ≡ 7  (mod 10)

Now, assume we know the number up to the kth digit, x

              x3 ≡ 3 (mod 10k)
  (dk+1·10k + x)3 ≡ 3 (mod 10k+1)
3·dk+1x2·10k + x3 ≡ 3 (mod 10k+1) (Binomial expansion.)
(Note that the other two terms can be ignored since they are 0 mod 10k+1)
3·dk+1x2·10k + x3 ≡ 3 (mod 10k+1)

We know that:

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

Substituting this in:

3·dk+1x2·10k + x3 ≡ 3                  (mod 10k+1)
  7·dk+1·10k + x3 ≡ 3                  (mod 10k+1)
             dk+1 ≡ (3 - x3) ÷ (7·10k) (mod 10)
                 ≡ (3 - x3) ÷ (7·10k) (mod 10)
           ∴ dk+1 ≡ 3·(3 - x3) ÷ 10k   (mod 10) (3 is the inverse of 7 mod 10)

Answer 3

Wolfram Language (Mathematica), 21 bytes

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

Try it online!

Answer 4

05AB1E, 17 13 bytes

7IGD3mN°÷7*θì

Port of @ASCII-only's Python 2 (PyPy) answer.
-4 bytes AND bug-fixed for outputs with leading zeros thanks to @Emigna, by replacing T%N°*+ with θì.

Try it online.

Explanation:

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

Answer 5

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)

Try it online!

Credits

• Port of xnor's Python 2 answer.
• -6 bytes thanks to Kevin Cruijssen

Answer 6

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

Port of @ASCII-only's Python 2 (PyPy) answer.
-2 bytes thanks to @Neil.
-20 bytes thanks to @ASCII-only.

NOTE: There is already a much shorter Java answer by @OlivierGrégoire using an algorithmic approach utilizing modPow.

Try it online.

Explanation:

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

Answer 7

dc, 15

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

Uses modular exponentiation, like @xnor's answer.

Try it online!

TIO calculates input=1000 in 21s.

Answer 8

Pyth, 12

.^3h/y^TQ3^T

Try it online!

Again, using modular exponentiation, like @xnor's answer.

Answer 9

Haskell, 37 bytes

1 byte saved thanks to ASCII-only!

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

Try it online!

I use a similar approach to ASCII-only, but I avoid using division

Answer 10

Pyth, 23 bytes

Of course, this uses ASCII-only's approach.

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

Try it here!

Answer 11

Charcoal, 26 22 bytes

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

Try it online! Link is to verbose version of code. Explanation:

≔⁷η

Initialise the result to 7. (Doesn't have to be 7, but 0 doesn't work.)

ＦＮ

Loop over the number of required digits.

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

Now uses @H.P.Wiz's approach to save 4 bytes.

Ｉη

Print the result.

Here's a 28-byte brute-force version that takes cube roots of arbitrary values:

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

Try it online! Link is to verbose version of code. First input is number of digits, second is value to root.

Answer 12

J, 33 bytes

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

TIO

port of @ASCII-only's answer but using fixed modulo 10^n throughout

Answer 13

Jelly, 23 18 17 bytes

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

Try it online!

I know ƒ will be useful.