16
\$\begingroup\$

This problem is based on non-terminating, repeating decimal points.

Let \$n\$ be any positive integer \$(n > 1 \text{ and } n < 10000)\$, say \$7\$. Then, \$1/n = 1/7 = 0.142857142857142857...\$

We see a pattern like, 0. 142857 142857 142857 ...
In this, the 142857 part is always repeating, which has length of \$6\$. Or, if \$n = 11\$, then \$1/n = 1/11 = 0.0909090909090909...\$

Here the length of the pattern is 2. So, here goes the problem!

Task

Given a positive integer \$n\$, \$(n > 1 \text{ and } n < 10000)\$, find the length of pattern in \$1/n\$, if it's repeating. Otherwise, return any non-positive integer (e.g., cases: \$1/5, 1/94, 1/22\$). Note that, the pattern should start just after the decimal point. Hint: \$1/22 = 0.04545454545454545454545\$.

Sample I/O

  • 5 -> -1
  • 13 -> 6
  • 21 -> 6
  • 27 -> 3
  • 33 -> 2
  • 37 -> 3
  • 94 -> -1
  • 22 -> -1
  • 69 -> 22
  • 197 -> 98
  • 65 -> -1
  • \$1/9979\$
  • \$1/9967\$

This is a , so the fewest bytes will win!

\$\endgroup\$
8
  • 1
    \$\begingroup\$ What should the output for n=1 be? I'd suggest guaranteeing that n>1, since n=1 is somewhat of a special case. \$\endgroup\$
    – xnor
    Oct 26 '20 at 5:03
  • 2
    \$\begingroup\$ Closely related. If anyone wants to close as dupe of this one, I'm not opposed to it. \$\endgroup\$
    – Bubbler
    Oct 26 '20 at 7:22
  • 1
    \$\begingroup\$ @DominicvanEssen - yes, non repeating patterns have no period, or 0 length. \$\endgroup\$
    – vrintle
    Oct 26 '20 at 11:03
  • 1
    \$\begingroup\$ I've decided to close this as a dupe for now since it seems there wasn't any difference in the overall algorithm, just the specifics of dealing with the "special cases" that sometimes lead to minor differences. \$\endgroup\$ Oct 26 '20 at 13:52
  • 2
    \$\begingroup\$ i don't agrée it's notre a dupe. Code golf the aim is to write the shortest and there are different ways. Check the answers. The "special cases" make the différence. \$\endgroup\$ Oct 27 '20 at 6:36

15 Answers 15

14
\$\begingroup\$

Jelly, 6 bytes

R⁵*%i1

Try it online!

Basically compute 10**[1..n] % n and get the 1-based index of 1.

\$\endgroup\$
1
  • \$\begingroup\$ wait i feel dumb for not figuring out at least a suboptimal version of this approach lmao \$\endgroup\$
    – hyper-neutrino
    Oct 26 '20 at 13:36
3
\$\begingroup\$

JavaScript (Node.js), 39 bytes

Expects a BigInt. Returns \$0\$ if there's no repeating pattern.

f=(n,k=1n)=>10n**(k%=n)%n-1n?f(n,-~k):k

Try it online!

\$\endgroup\$
3
\$\begingroup\$

05AB1E, 7 6 bytes

L.Δ°I%

Port of @Bubbler's Jelly answer, so make sure to upvote him!
-1 byte thanks to @ovs.

Outputs -1 if it's non-repeating.

Try it online or verify all test cases (times out for the final test case).

Explanation:

L       # Push a list in the range [1, (implicit) input-integer]
 .Δ     # Find the first value in this list which is truthy for:
        # (results in -1 if none are found)
   °    #  Take 10 to the power the current integer
    I%  #  Modulo the input-integer
        #  (Note: Only 1 is truthy in 05AB1E)
        # (after which the result is output implicitly as result)
\$\endgroup\$
2
  • 2
    \$\begingroup\$ 6 bytes with \$\endgroup\$
    – ovs
    Oct 26 '20 at 11:00
  • \$\begingroup\$ @ovs Ah, smart. Thanks \$\endgroup\$ Oct 26 '20 at 11:16
3
\$\begingroup\$

K (ngn/k), 16 23 19 bytes

{1+(x(x!10*)\10)?1}

Try it online!

As suggested by @traws (returns INT_MIN+1 if there's no repeating pattern), adapted to work with longer patterns that would otherwise overflow 64-bit integers.

  • x(...)\10 set up a monadic-do-scan, run for x iterations and seeded with 10
  • (x!10*) multiply the current value by 10, modding by the original x input
  • (...)?1 get the index of the first 1 showing up in the result (returns 0N if no 1 is present, i.e. if there is no repeating pattern)
  • 1+ add one to that result; converts 0N to -9223372036854775807
\$\endgroup\$
1
  • 1
    \$\begingroup\$ You could do {1+(x!*\x#10)?1} in ngn/k, where 0N+1 wraps around becoming negative. \$\endgroup\$
    – Traws
    Oct 26 '20 at 14:48
2
\$\begingroup\$

Husk, 8 bytes

€1m%¹↑İ⁰

Try it online!

Same approach as Bubbler's answer.

€1m%¹↑İ⁰
€1          # index of first '1' in 
  m         # list of results of applying 
   %¹       # MOD n 
     ↑      # to first n elements of 
      İ⁰    # series of powers of 10 (starting at 10)
\$\endgroup\$
2
\$\begingroup\$

Perl 5 (-p -Mbigint), 31 bytes

$_=++$i<$_?9x$i*1%$_?redo:$i:-1

Try it online!

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

GolfScript, 20 19 bytes

~:x,{10\?x%1=},0+1=

Try it online!

~:x                   # Assign the input to x                  13
   ,                  # Make an array from 0 to x-1            [0 1 2 3 4 5 6 7 8 9 10 11 12]
    {        },       # Find all numbers that pass this test
     10\?x%           # (10^k)%x                               [1 10 9 12 3 4 1 10 9 12 3 4 1]
           1=         # Is it 1?                               [1  0 0  0 0 0 1  0 0  0 0 0 1]
                      # Only the index of the 1s are kept      [0 6 12]
               0+     # Append 0                               [0 6 12 0]
                 1=   # Get the second number                  6

If it doesn't repeat, the array will be [0 0] and 0 will be outputted.

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

Jelly, 21 bytes

R⁵*’ḍ@¹TṂȧ@⁸g10¤’¬¤o-

Try it online!

This is probably very suboptimal (edit yes it is, i don't know why i didn't think to combine the two checks together cuz that would've given Bubbler's algorithm which is pretty smart).

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

C (gcc), 55 52 bytes

Saved 3 bytes thanks to the man himself Arnauld!!!

i;m;f(n){for(i=m=1;(m*=10)%n&&m%n-1;++i);m=m%n?i:0;}

Try it online!

Returns either the length of repeated pattern of \$\frac{1}{\space n \space}\$ or \$0\$ for no repeated pattern.

\$\endgroup\$
2
  • \$\begingroup\$ -3 bytes by starting with m=1. \$\endgroup\$
    – Arnauld
    Oct 26 '20 at 10:44
  • \$\begingroup\$ @Arnauld Nice one - thanks! :-) \$\endgroup\$
    – Noodle9
    Oct 26 '20 at 10:52
1
\$\begingroup\$

Python 3, 50 bytes

f=lambda n,i=1:i*(10**i%n==1)or~(i<n and~f(n,i+1))

Try it online!

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

Wolfram Language (Mathematica), 45 41 39 bytes

n_:>Lookup[Mod[10^#,n]->#&~Array~n,1,0]

Try it online!

Defined as a delayed rule that can be applied to any integer.

\$\endgroup\$
2
  • \$\begingroup\$ 34 bytes \$\endgroup\$
    – att
    Apr 26 at 18:14
  • \$\begingroup\$ Very nice, @att! I think your code deserves a separate answer that I can upvote. \$\endgroup\$
    – Roman
    Apr 26 at 19:37
1
\$\begingroup\$

Wolfram Language (Mathematica), 29 bytes

0&@@10~MultiplicativeOrder~#&

Try it online!

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

Retina, 68 bytes

.+[1379]$
_,$&*_,;
\d+
0
{`;
;_
\G_
10*
+`(_+,)\1
,$1
^_,.+;(_+)
$.1

Try it online! Link includes faster test cases. Explanation:

.+[1379]$
_,$&*_,;

If the number is coprime to 10, then create a work area with the values p=1, n and k=0 (in unary).

\d+
0

But if it is not coprime to 10 then set the answer to 0 immediately.

{`

Repeat until the answer is found.

;
;_

Increment k.

\G_
10*

Multiply p by 10.

+`(_+,)\1
,$1

Reduce p modulo n.

^_,.+;(_+)
$.1

If p=1, then set the answer to k converted to decimal, which allows the loop to exit.

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

Charcoal, 13 bytes

NθI⊕⌕﹪Xχ…¹θθ¹

Try it online! Link is to verbose version of code. Basically a port of @Bubbler's answer, except that my range goes from 1 to n-1. Explanation:

Nθ              Take input as a number
        …       Exclusive range
         ¹      From literal `1`
          θ     To input number
      X         Vectorised raise to power
       χ        Predefined variable `10`
     ﹪          Vectorised reduce modulo
           θ    Input number
    ⌕           Find index of
            ¹   Literal `1`
   ⊕            Increment
  I             Cast to string
                Implicitly print
\$\endgroup\$
0
\$\begingroup\$

Batch, 91 bytes

@set/ap=1,k=0
:g
@set/ak=-~k%%%1,p=p*10%%%1
@if %k% neq 0 if %p% neq 1 goto g
@echo %k%

Explanation: Repeatedly increments the answer and multiplies the power by 10 until (modulo the input) the answer wraps around to zero or the power reduces to 1.

\$\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.