24
\$\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\$
  • \$\begingroup\$ OEIS A225404 \$\endgroup\$ – Leaky Nun Jun 7 '18 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\$ – Kevin Cruijssen Jun 7 '18 at 13:56
  • \$\begingroup\$ @KevinCruijssen done \$\endgroup\$ – Leaky Nun Jun 7 '18 at 14:14

13 Answers 13

26
\$\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\$
  • 1
    \$\begingroup\$ I would like to see a more detailed explanation on how this works, very nice answer! \$\endgroup\$ – Cows quack Jun 7 '18 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 '18 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 '18 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 '18 at 2:23
  • \$\begingroup\$ As usual, maths win! \$\endgroup\$ – Olivier Grégoire Jun 8 '18 at 13:07
18
\$\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 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)
\$\endgroup\$
  • \$\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\$ – user202729 Jun 7 '18 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 '18 at 12:53
  • \$\begingroup\$ This only prints the last 11 digits for n=12 and n=13. \$\endgroup\$ – Emigna Jun 7 '18 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\$ – Peter Taylor Jun 7 '18 at 16:06
  • 1
    \$\begingroup\$ save 5 bytes \$\endgroup\$ – H.PWiz Jun 7 '18 at 16:40
6
\$\begingroup\$

Wolfram Language (Mathematica), 21 bytes

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

Try it online!

\$\endgroup\$
4
\$\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\$
  • \$\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 '18 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\$ – Kevin Cruijssen Jun 8 '18 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\$
  • \$\begingroup\$ Oh, you used that algorithm too? I'll rollback my answer and add you changes ;) \$\endgroup\$ – Olivier Grégoire Jun 7 '18 at 11:53
  • \$\begingroup\$ java.math.BigInteger u=null,r=u.valueOf(7),t=r;? \$\endgroup\$ – Neil Jun 7 '18 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\$ – Kevin Cruijssen Jun 7 '18 at 12:23
  • 1
    \$\begingroup\$ 141? \$\endgroup\$ – ASCII-only Jun 8 '18 at 0:25
  • 1
    \$\begingroup\$ *modpow, not modpod :P \$\endgroup\$ – ASCII-only Jun 8 '18 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\$
  • 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\$ – Kevin Cruijssen Jun 7 '18 at 11:47
  • 1
    \$\begingroup\$ 1 more byte to save by changing the loop to for(int l=0,d;l++<n;). \$\endgroup\$ – Kevin Cruijssen Jun 7 '18 at 12:11
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\$
2
\$\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
    \$\begingroup\$ 37? \$\endgroup\$ – ASCII-only Jun 7 '18 at 23:59
1
\$\begingroup\$

Pyth, 23 bytes

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

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

Try it here!

\$\endgroup\$
  • 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 '18 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\$
  • \$\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 '18 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 '18 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 '18 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 '18 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, privacy policy and cookie policy

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