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}\$)

  • \$\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 '20 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\$ – Wheat Wizard Mar 14 '20 at 21:15
  • \$\begingroup\$ What do you think about this one? codegolf.stackexchange.com/q/68031/20260 \$\endgroup\$ – xnor Mar 14 '20 at 21:19
  • 1
    \$\begingroup\$ @HyperNeutrino the post describes it as period 1 (a repeating zero). \$\endgroup\$ – Jonathan Allan Mar 14 '20 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 '20 at 21:57

Jelly, 9 bytes


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

Try it online! Or see the test-suite.


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

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!


Wolfram Language (Mathematica), 30 bytes


Try it online!


Charcoal, 33 bytes


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:


Input n.


Start with a list containing just 2⁰.


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.


Print the difference in the two exponents.


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!


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