3
\$\begingroup\$

We know that not all fractions have a terminating binary representation. However every fraction can be written as a leading portion followed by a repeating portion. For example \$1/3\$ starts with \$0.\$ and then just repeats \$01\$ endlessly. This corresponds to the bar notation taught in primary school. For example

$$ 1/3 = 0.\overline{01} $$

Where the portion with the bar is the repeating section.

For numbers with a terminating representation, (e.g. \$1/2 = 0.1\$) the repeating section is just \$0\$, since there are endless implicit zeros at the end of a terminating representation.

We will call the minimum1 length of the repeating section the binary period of the fraction.

Your task is to write a program or function which takes a positive integer \$n\$ as input and outputs the binary period of \$1/n\$.

This is so answers will be scored in bytes with fewer bytes being better.

OEIS A007733


1: We say minimum because if you duplicate a section again it keeps a valid representation. (e.g. \$0.\overline{01} = 0.\overline{0101}\$)

\$\endgroup\$
  • \$\begingroup\$ I feel like we've had a similar challenge mod 10, or maybe about finding the period of the powers of 10 mod n which is similar. \$\endgroup\$ – xnor Mar 14 at 21:11
  • \$\begingroup\$ @xnor I gave it a search and came up with nothing. If you (or anyone else) find it I would like to know. \$\endgroup\$ – Ad Hoc Garf Hunter Mar 14 at 21:15
  • \$\begingroup\$ What do you think about this one? codegolf.stackexchange.com/q/68031/20260 \$\endgroup\$ – xnor Mar 14 at 21:19
  • 1
    \$\begingroup\$ @HyperNeutrino the post describes it as period 1 (a repeating zero). \$\endgroup\$ – Jonathan Allan Mar 14 at 21:53
  • 1
    \$\begingroup\$ Almost, I don't think you take binary length, just divide by two until odd, then take the result from that challenge. \$\endgroup\$ – xnor Mar 14 at 21:57
1
\$\begingroup\$

Jelly, 9 bytes

2*Ɱ%µẠȧQL

A monadic Link accepting a positive integer, n, which yields a positive integer, the period.

Try it online! Or see the test-suite.

How?

2*Ɱ%µẠȧQL - Link: integer, n
2         - literal two
  Ɱ       - map across [1..n]
 *        - exponentiate -> [1,2,4,8,...,2^n]
   %      - modulo n -> [1%n,2%n,4%n,8%n,...,2^n%n]
    µ     - start a new monadic chain - call that X
     Ạ    - all (X)? -> 0 if we reach zero, else 1 - i.e. 0 if n is a power of 2
       Q  - de-duplicate (X) -> the repeating 2^k%n values 
      ȧ   - logical AND -> 0 if n is a power of 2 else Q(X)
        L - length (0 has a length of 1 (after an implicit make_digits))
|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

Python 3, 70 bytes

f=lambda k,a=1:k%2and(a/k%1and f(k,a*2+1)or len(bin(a))-2)or f(k//2,a)

Try it online!

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

Wolfram Language (Mathematica), 30 bytes

Length@@#&@@RealDigits[1/#,2]&

Try it online!

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

Charcoal, 33 bytes

Nθ⊞υ¹W¬№﹪υθ﹪⊕Συθ⊞υ⊕ΣυI⊕⌕﹪⮌υθ﹪⊕Συθ

Try it online! Link is to verbose version of code. Sadly all my attempts to golf this down tended to break on edge cases such as 1 or other powers of 2. Explanation:

Nθ

Input n.

⊞υ¹

Start with a list containing just 2⁰.

W¬№﹪υθ﹪⊕Συθ

See if the next power of 2 is equivalent (modulo n) to any of the elements in the list.

⊞υ⊕Συ

If not then push that power of 2 to the list.

I⊕⌕﹪⮌υθ﹪⊕Συθ

Print the difference in the two exponents.

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

Python, 49 bytes

lambda n:len({2**-~k%n*(n&~-n)for k in range(n)})

An unnamed function accepting a positive integer, n, which returns a positive integer, the period.

Try it online!

|improve this answer|||||
\$\endgroup\$

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