# Find the binary period [duplicate]

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

• 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. – xnor Mar 14 at 21:11
• @xnor I gave it a search and came up with nothing. If you (or anyone else) find it I would like to know. – Ad Hoc Garf Hunter Mar 14 at 21:15
• @HyperNeutrino the post describes it as period 1 (a repeating zero). – Jonathan Allan Mar 14 at 21:53
• Almost, I don't think you take binary length, just divide by two until odd, then take the result from that challenge. – xnor Mar 14 at 21:57

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


# 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

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


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!