Odd Long Tally Counter

If we examine the problem, we see that for a given number $n$ from $1$ to $10^7$ , $F(n)$ is equal to $\dfrac{10^7}{gcd(10^7, n)}$ because the counter repeats at every multiple of $gcd(10^7, n)$ . For example, if $n = 100$ , then $gcd(10^7, n)$ is $100$ , therefore $100$ divides into $10^7$ 100 times, and finally $F(100)$ is $10^5$ . We then just add the values of $F(n)$ from $1$ to $10^7$ , like this in Python:

from fractions import gcd

sum = 0
for num in range(1, 10**7):
    sum += 10**7/gcd(10**7, num)

This executes in less than 5 minutes on my laptop.

That exclamation mark may be interpreted as a factorial. It may be nice to \left[ (m,x)=d\right] \frac{m}{\gcd(m,x)} ] $= \sum_{d|m} \sum_{x=1}^m \left[ (m,x)=d\right] \frac{m}{d}= \sum_{d|m} \frac{m}{d} \sum_{x=1}^m \left[ (m,x)=d\right]$ [= \sum {d|m} \frac{m}{d} \sum {x=1}^m \left[ (m/d,x/d)=1\right]= \sum_{d|m} \frword it differently to avoid that ambiguity.

First, using the mighty Haskell

let sumOfTally m = sum $ map ((m `div`).(gcd m)) [1..m-1]

Then sumOfTally (10^7) is our answer. Instead of 10^7 I will consider the general case of m. We can compute $F(x)=\frac{m}{gcd (m,x)}$ , and we know that because when adding to the tally, we are always in $kx \mod{m}$ for some $k$ . Then $d=gcd(m,x)$ will always divide $kx$ and $m$ so that reminder will be divisible by d. Furthermore, appart from $gcd(x/d,m/d)=1$ , so factoring the d, it will give relative prime numbers, so it will pass through every number modulo $m/d$ . And that is fast enough $O(n\log{n})$ (Great Common Denominator is really O(log n) where n is the smaller number). Some five, ten seconds maybe.

But we can do better. I will use the notation that [P] is 1 when P is true, 0 when is false. And that $gcd(x,y)$ divides both x and y. To simplify things, I will sum until i=m, then substract that case (Note that F(m)=1)

$\sum_{i=1}^m F(i)=\sum_{x=1}^m \frac{m}{\gcd(m,x)}=\sum_{d|m} \sum_{x=1}^mac{m}{d} \sum_{y=1}^{m/d} \left[ (m/d,y)=1\right]$ $= \sum_{d|m} \frac{m}{d}\phi\left(\frac{m}{d}\right) = \sum_{d|m} d\phi\left(d\right)$

Coding phi is standard, as well as getting the list of divisors, and you can make some optimizations by knowing already the factorization of $m$ But we can still do better, at least we can have a nicer code. Bottomline, the bottleneck would be factorizing $m$ still.

By the theory of multiplicative functions, if that thing I name it $G(m)$ , then G(m) is multiplicative, because $1/n$ is multiplicative, as well as $phi$ and G is the convolution of both things. That means that if $m=\prod_{i=1}^r p_i ^{a_i}$ then $G(m)=\prod_{i=1}^r G(p_i ^{a_i})$ . So lets calculate $G(p^k)$ .

$G(p^k)=1+(p^2-p)+(p^4-p^3)+...+(p^{2k}-p^{2k-1}=\sum_{t=0}^{2k} (-p)^t = \frac{p^{2k+1}+1}{p+1}$

So with all this have now a nice formula for the sum (plus 1). To wrap this, lets do some code in Haskell.

import Data.List
primes = 2:filter (\k-> and [rem k p>0|p<-takeWhile ((<=k).(^2)) primes]) [3,5..]
numFactors p n = genericLength $ takeWhile ((==0).(flip rem p)) $ iterate (`div` p) n
factorFrom p n = head $ dropWhile ((==0).(flip rem p)) $ iterate (`div` p) n
factors (p:ps) n 
    | n==1 = 1
    | rem n p == 0 =  (p,numFactors p n):factors ps (factorFrom p n)
    | otherwise = factors ps n
sumOfTally n = (-1) $ product $ map (\(p,k)->(p^(2*k+1)+1) `div` p+1) $ factors primes n

Little bit faster.

Python Sol::::

def F1(k, num):
    tally, i = [], 0
    if i % 2 == 1 and i % 5 != 0:
        return num
    m, n = fac2(k), fac5(k)
    return make(m, n, num)

def make(m, n, num):
    for i in range(m + 1)[::-1]:
        for j in range(n + 1)[::-1]:
            res = num/float((2**i)*(5**j))
            if res == int(res):
                return int(res)


def F(k, num):
    tally, i = [], 0
    while True:
        if len(tally) < 2:
            tally.append((k*i)%num)
        elif tally[-1] == tally[0]:
            tally.pop()
            return len(tally)
        else:
            tally.append((k*i)%num)
        i += 1

def fac2(n):
    times = 0
    while n > 0:
        if n%2 == 0:
            times += 1
        else:
            return times
        n = n/2

def fac5(n):
    times = 0
    while n > 0:
        if n%5 == 0:
            times += 1
        else:
            return times
        n = n/5



tot = 0
for i in range(1, 10000000):
    tot += F1(i, 10000000)

The main key is to proof that $F(n) = \frac{10^7}{GCD(n,10^7)}$

Once you get it, just use a single loop + Euclid's algorithm to get the answer.

The proof of $F(n)$ is left as an exercise, :)

It's the same program (solution) as for the other problem but this time we have to take care not to overflow the int type so we just need to keep the sum modulo 1000:

#include <iostream>

int gcd(int a, int b){ 
if (b == 0) return a;
else return gcd(b, a % b);
} 

int main(int argc, char** argv) {

int sum=0, i;
for(i=1;i<5000000;i++){
    sum += 2 * 10000000 / gcd(i, 10000000);
    sum %= 1000;
}
sum += 10000000 / gcd(i, 10000000); //for the middle 5000000
sum %= 1000;
printf("sum=%d", sum);
return 0;
}

The output is:

sum=382

=MOD(14 (4^k-1)+500 (k-1)+20,1000) for tally counter with k digits

=382 for k=7

In Ruby:

(1..9999999).inject(0){|s,i|s+=10000000/10000000.gcd(i)}

Mathematically: F(x) = N/GCD(x,10^7). Used Excel to Compute SUM(F(x)) for x=1 to 9,999,999 . ( Use Datable after calculating from 0 to 999,999). For Excel file you can send a request at www.excelmagicpro.com by going in the interest form section under Contact.

We need to find the least multiple which devides 10^7 and n and then devide it by n. It is easier if we just remove the common devisors of both from 10^7. 10^7 is only devided by 2^7 and 5^7 which makes our work easier: import sys

def counter(number,upper):
    i=1
    while i<8:
        if number%(2**i)==0:
            i=i+1
        else:
            break
    upper=upper/2**(i-1)
    i=1
    while i<8:
        if number%(5**i)==0:
            i=i+1
        else:
            break
    upper=upper/5**(i-1)
    return upper%1000

sum=0
for i in range(1,10000000):
    if i%10000==0:
        print i
    sum=sum+counter(i,10000000)
    if sum>=1000:
        sum=sum%1000
print sum

Basically, $F(n) = \frac{10^7}{\mathrm{gcd}(10^7, \, n)}$ . Using just that fact alone, I was able to get a runtime of about 3 seconds. However, one can also note that $F(n) = F(10^7 - n)$ .Therefore, we find the sum from 1 to 10^7/2 - 1, double that, and add 2 (to account for F(10^7/2) = 2), which cuts runtime in half to 1.5 s.

I feel like there's an even more clever way involving the totient function and the divisors of 10^7, but I can't come up with one atm.