Coprime Period

Lemma

If the prime factor decomposition of $n$ is $n = p_1^{e_1} \cdot p_2^{e_2} \cdot \cdots$ then the period of $f_n$ is equal to $T = p_1 \cdot p_2 \cdots.$

Application

In this case, since $1400 = 2^3 \cdot 5^2 \cdot 7,$ the solution is $2 \cdot 5 \cdot 7 = \boxed{70}.$

Proof

(1) We show that if there is a $p|n$ such that $p \not | T$ , then there exist $m$ with $f_n(m) = 0$ but $f_n(m+T) = 1$ .

Assuming this, let $m = q_1\cdot q_2\cdots$ be the product of all prime factor of $n$ that do not divide $T$ . Then $f_n(m) = 0$ because $\gcd(n,m) = m > 1$ . Now suppose that there is some prime factor $q|\gcd(n,m+T)$ , implying both $q|n$ and $q|(m+T)$ . The way we defined $m$ , $q$ is a prime factor of either $T$ or $m$ , but not both. Therefore $q$ does not divine $m+T$ ; it follows that such a prime number $q$ does not exist. We conclude $\gcd(n,m+T) = 1$ and $f_n(m+T) = 1$ .

It follows that $T$ must be at least a multiple of all prime divisors $p_1,p_2,\dots$ of $n$ .

(2) We show that if $T = p_1\cdot p_2 \cdots$ , then $f_n(m) = f_n(m+T)$ for all $m$ .

If $f_n(m) = 0$ then $\gcd(n,m) > 1$ , which means there is a prime factor $p|\gcd(n,m)$ ; this means that $p|n$ and $p|m$ . From $p|n$ and the definition of $T$ is follows that $p|T$ . From $p|m$ and $p|T$ it follows that $p|(m+T)$ . Therefore $p|\gcd(n,m+T)$ , implying that $f_n(m+T) = 0$ as well.

Conversely, suppose that $f_n(m) = 1$ , i.e. $\gcd(n,m) = 1$ . Then no prime factor $p|n$ can be a divisor of $m$ . But if $p\not | m$ and $p|T$ then $p \not | m+T$ , implying that $\gcd(n,m+T) = 1$ and $f_n(m+T) = 1$ .

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

# https://brilliant.org/practice/greatest-common-divisor-lowest-common-multiple-4-c/?p=4

def gcd(*numbers):
    """Return the greatest common divisor of the given integers"""
    from fractions import gcd
    return reduce(gcd, numbers)

def period_n(l):
    s_arr=''
    for i in range(0,len(l)):
        s_arr=s_arr+l[i]
        sp_list=string_.split(s_arr)
        c = 0
        for j in sp_list:
            if j =='':
                c+=1
        if c == len(sp_list):
            break
    return s_arr, sp_list, c

f_target = 1400
string_ = ''
for i in range(f_target):
    if gcd(i,f_target) > 1:
        string_ += '0'
    else:
        string_ += '1'

binarylist=list(string_)
strarr, splitlist, counter = period_n(binarylist)

if counter == len(splitlist):
    if counter == 2:
        print "No repeating substring found in string %r"%(string_)
    else:
        print "Substring %r of period %d (%d times)"%(strarr, len(strarr), counter)
else :
    print "No repeating substring found in string %r"%(string_)

Substring '0101000001010100010100010001010101000101010100010001010001010100000101' of period 70 (21 times)