25
\$\begingroup\$

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 . Shortest answer in bytes wins.

\$\endgroup\$
3
  • \$\begingroup\$ OEIS A225404 \$\endgroup\$
    – Leaky Nun
    Jun 7, 2018 at 13:52
  • 1
    \$\begingroup\$ Do we need to print leading zeros as well? Most answers (including my Java answer) are currently failing for those. i.e. n=12 outputting 87895134587 instead of 087895134587. Personally I would make it optional, since it would invalidate almost all answers.. \$\endgroup\$ Jun 7, 2018 at 13:56
  • \$\begingroup\$ @KevinCruijssen done \$\endgroup\$
    – Leaky Nun
    Jun 7, 2018 at 14:14

13 Answers 13

28
\$\begingroup\$

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.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ I would like to see a more detailed explanation on how this works, very nice answer! \$\endgroup\$
    – user41805
    Jun 7, 2018 at 15:43
  • \$\begingroup\$ Should (r**3)**e = x (mod 10**k) be (r**3)**e = r (mod 10**k)? Also is it just a coincidence that (2 * 10**k + 1)/3 = 1/3 (mod 10**k)? \$\endgroup\$
    – H.PWiz
    Jun 8, 2018 at 1:46
  • \$\begingroup\$ @H.PWiz Yes, thanks, I fixed it. I'm not sure if it being an inverse for 3 is a coincidence. It's certainly not enough, as replacing the 2 with other values doesn't work. \$\endgroup\$
    – xnor
    Jun 8, 2018 at 1:57
  • \$\begingroup\$ @xnor I think it is enough. You should be able to replace to replace 2 with any number x = 2 (mod 3) \$\endgroup\$
    – H.PWiz
    Jun 8, 2018 at 2:23
  • \$\begingroup\$ As usual, maths win! \$\endgroup\$ Jun 8, 2018 at 13:07
20
\$\begingroup\$

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 \$d_n\$ be the \$n\$th digit of the number (from the right).

$$ \begin{align*} d_1^3 &\equiv 3 &&\pmod{10} \\ d_1 &\equiv 3^3 &&\pmod{10} \\ &\equiv 27 &&\pmod{10} \\ &\equiv 7 &&\pmod{10} \\ \end{align*} $$

Now, assume we know the number up to the \$k\$th digit, \$x\$

$$ \begin{align*} x^3 &\equiv 3 &&\pmod{10} \\ (d_{k+1} \cdot 10^k + x)^3 &\equiv 3 &&\pmod{10} \\ m \cdot 10^{2k} + 3 \cdot d_{k+1} x^2 \cdot 10^k + x^3 &\equiv 3 &&\pmod{10^{k+1}} \;\textrm{(for some } m \textrm{)} \\ 3 \cdot d_{k+1} x^2 \cdot 10^k + x^3 &\equiv 3 &&\pmod{10^{k+1}} \\ \end{align*} $$

We know that:

$$ \begin{align*} x &\equiv 7 &&\pmod{10} \\ x^2 &\equiv 49 &&\pmod{10} \\ &\equiv 9 &&\pmod{10} \\ x^2 \cdot 10^k &\equiv 9 \cdot 10^k &&\pmod{10^{k+1}} \\ 3 \cdot x^2 \cdot 10^k &\equiv 27 \cdot 10^k &&\pmod{10^{k+1}} \\ &\equiv 7 \cdot 10^k &&\pmod{10^{k+1}} \\ \end{align*} $$

Substituting this in:

$$ \begin{align*} 3 \cdot d_{k+1} x^2 \cdot 10^k + x^3 &\equiv 3 &&\pmod{10^{k+1}} \\ 7 \cdot d_{k+1} \cdot 10k + x^3 &\equiv 3 &&\pmod{10^{k+1}} \\ d_{k+1} &\equiv \frac{3 - x3}{7 \cdot 10^k} &&\pmod{10} \\ \therefore d_{k+1} &\equiv \frac{3 \cdot \left(3 - x^3\right)}{10^k} &&\pmod{10} \; (7^{-1} \equiv 3 \pmod{10}) \end{align*} $$

\$\endgroup\$
9
  • \$\begingroup\$ Actually this solution is likely to be optimal. (for most languages where the formula is less verbose than brute forcing) Explanation can be found somewhere in chat, although quite scattered. \$\endgroup\$
    – DELETE_ME
    Jun 7, 2018 at 11:00
  • \$\begingroup\$ If you aimed to golf the "non-exec" solution, this works for 62 bytes as a full program instead of a function \$\endgroup\$
    – Mr. Xcoder
    Jun 7, 2018 at 12:53
  • \$\begingroup\$ This only prints the last 11 digits for n=12 and n=13. \$\endgroup\$
    – Emigna
    Jun 7, 2018 at 13:41
  • 4
    \$\begingroup\$ × and x look really quite similar in some fonts, and make the maths extremely hard to read. May I suggest using · (centre dot) instead of × ? (And, obviously, it would be nice to have MathJax). \$\endgroup\$ Jun 7, 2018 at 16:06
  • 1
    \$\begingroup\$ save 5 bytes \$\endgroup\$
    – H.PWiz
    Jun 7, 2018 at 16:40
7
\$\begingroup\$

Wolfram Language (Mathematica), 21 bytes

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

Try it online!

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ H.P.Wiz has golfed my approach, and the challenge no longer requires leading zeroes so you may be able to golf it more? \$\endgroup\$
    – ASCII-only
    Jun 8, 2018 at 0:44
  • \$\begingroup\$ @ASCII-only Perhaps, but not sure how. @Emigna has already golfed T%N°*+ to θì for me, and the leading zero 'fix' was just a nice bonus with this approach. \$\endgroup\$ Jun 8, 2018 at 6:51
4
\$\begingroup\$

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
\$\endgroup\$
13
  • \$\begingroup\$ Oh, you used that algorithm too? I'll rollback my answer and add you changes ;) \$\endgroup\$ Jun 7, 2018 at 11:53
  • \$\begingroup\$ java.math.BigInteger u=null,r=u.valueOf(7),t=r;? \$\endgroup\$
    – Neil
    Jun 7, 2018 at 12:20
  • \$\begingroup\$ @Neil Of course.. thanks. I had java.math.BigInteger t=null,r=u.valueOf(7);t=r; initially before I added the u to save some bytes. \$\endgroup\$ Jun 7, 2018 at 12:23
  • 1
    \$\begingroup\$ 141? \$\endgroup\$
    – ASCII-only
    Jun 8, 2018 at 0:25
  • 1
    \$\begingroup\$ *modpow, not modpod :P \$\endgroup\$
    – ASCII-only
    Jun 8, 2018 at 9:32
4
\$\begingroup\$

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 166 bytes by changing the loop to for(int l=0,d;++l<=n; and changing BigInteger I=null; to var I=new BigInteger("3"); which we can re-use. \$\endgroup\$ Jun 7, 2018 at 11:47
  • 1
    \$\begingroup\$ 1 more byte to save by changing the loop to for(int l=0,d;l++<n;). \$\endgroup\$ Jun 7, 2018 at 12:11
3
\$\begingroup\$

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

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 37? \$\endgroup\$
    – ASCII-only
    Jun 7, 2018 at 23:59
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

Pyth, 12

.^3h/y^TQ3^T

Try it online!

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

\$\endgroup\$
1
\$\begingroup\$

Pyth, 23 bytes

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

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

Try it here!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ @DigitalTrauma Oh >_< I swear I haven't noticed your answer lol... I first had a port of ASCII's solution, then I saw xnor's and I ported it directly to golf it :P I guess I will rollback to the initial revision, though. \$\endgroup\$
    – Mr. Xcoder
    Jun 8, 2018 at 7:43
1
\$\begingroup\$

Charcoal, 26 22 bytes

≔⁷ηFN≧⁺﹪׳⁻³Xη³Xχ⊕ιηIη

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

FN

Loop over the number of required digits.

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

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

Iη

Print the result.

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

FN⊞υ⊟Φχ¬﹪⁻XI⁺κ⭆⮌υμ³IηXχ⊕ι↓Iυ

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

\$\endgroup\$
4
  • \$\begingroup\$ H.P.Wiz has updated (read: golfed) my approach. Also, stringmap shouldn't be needed anymore since Leaky Nun has updated the requirements. also the first link also points to the brute force version >_> \$\endgroup\$
    – ASCII-only
    Jun 8, 2018 at 0:34
  • \$\begingroup\$ @ASCII-only Thanks, I've fixed the links and ported H.P.Wiz's approach, but I needed StringMap to concatenate k with the reversed list as a base 10 number. \$\endgroup\$
    – Neil
    Jun 8, 2018 at 8:25
  • \$\begingroup\$ Hmm. I would have thought just doing it the plain number way may have been golfier. I guess not though \$\endgroup\$
    – ASCII-only
    Jun 8, 2018 at 8:44
  • \$\begingroup\$ @ASCII-only For the previous version I used Base(Reverse(u), 10) but prefixing k would have cost 4 bytes while doing it as a string only costs 2 bytes resulting in a 1-byte saving after taking the Cast into account. \$\endgroup\$
    – Neil
    Jun 8, 2018 at 9:06
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

Jelly, 23 18 17 bytes

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

Try it online!

I know ƒ will be useful.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.