14
\$\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\$
  • 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 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 at 7:22
  • 1
    \$\begingroup\$ @DominicvanEssen - yes, non repeating patterns have no period, or 0 length. \$\endgroup\$ – vrintle Oct 26 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\$ – FryAmTheEggman Oct 26 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\$ – Nahuel Fouilleul Oct 27 at 6:36

14 Answers 14

14
\$\begingroup\$

Jelly, 6 bytes

R⁵*%i1

Try it online!

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

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ wait i feel dumb for not figuring out at least a suboptimal version of this approach lmao \$\endgroup\$ – HyperNeutrino Oct 26 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!

| improve this answer | |
\$\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)
| improve this answer | |
\$\endgroup\$
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)
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Perl 5 (-p -Mbigint), 31 bytes

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

Try it online!

| improve this answer | |
\$\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.

| improve this answer | |
\$\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).

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

K (oK), 28 33 bytes

{$[^o:1+(x{x!y*10}[x]\10)?1;0;o]}

Try it online!

If it's okay to return nulls (0N) instead of "any non-positive integer", 4 bytes can be saved by shortening the code to:

{o*~^o:1+(x{x!y*10}[x]\10)?1}

K (ngn/k), 16 23 bytes

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

As suggested by @traws. Adapted to work with long patterns.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ You could do {1+(x!*\x#10)?1} in ngn/k, where 0N+1 wraps around becoming negative. \$\endgroup\$ – Traws Oct 26 at 14:48
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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ -3 bytes by starting with m=1. \$\endgroup\$ – Arnauld Oct 26 at 10:44
  • \$\begingroup\$ @Arnauld Nice one - thanks! :-) \$\endgroup\$ – Noodle9 Oct 26 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!

| improve this answer | |
\$\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.

| improve this answer | |
\$\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.

| improve this answer | |
\$\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
| improve this answer | |
\$\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.

| improve this answer | |
\$\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.