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

Improve this question
\$\endgroup\$
9
  • \$\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\$ Commented Mar 14, 2020 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\$ Commented Mar 14, 2020 at 21:15
  • \$\begingroup\$ What do you think about this one? codegolf.stackexchange.com/q/68031/20260 \$\endgroup\$ Commented Mar 14, 2020 at 21:19
  • 1
    \$\begingroup\$ @HyperNeutrino the post describes it as period 1 (a repeating zero). \$\endgroup\$ Commented Mar 14, 2020 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\$ Commented Mar 14, 2020 at 21:57

5 Answers 5

Reset to default
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

Ｎθ⊞υ¹Ｗ¬№﹪υθ﹪⊕Συθ⊞υ⊕ΣυＩ⊕⌕﹪⮌υθ﹪⊕Συθ

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.

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.