For the new year!

Any number N can be written as a product of primes and this is unique by the fundamental theorem of arithmetic.

So N= p1^a1.....pn^an. It follows that the number of distinct divisors of this number is (a1+1)(a2+1).....(an+1). Where the ai are powers of the primes.

Now note that this expression will change parity when N is a perfect square as otherwise, the number of divisors will be even. So s(n) changes its parity when N is a perfect square.

We note that s(1), s(2), s(3). Are odd but s(4),...s(8) are even. Now 44^2<2015 but 45^2 > 2015.

Repeating the pattern noticed above shows us that a= (2^2 -1^2 )+(4^2 - 3^2 )+...+(44^2 -43^2 ). This can easily be evaluated to give A=990.

Now b=2015-990= 1025. So |A-B|= 35

Lemma $s(n)≡[\sqrt{n}]$ $(mod$ $2)$

Proof Consider the function, $f(n)=[\sqrt{n}]+\sum_{k=1}^{n}t(k)$ .

I will prove by induction that $f(n)$ is even.

Note that $f(1)$ is even.

Suppose $f(n)$ is even,say $2k$

Now, $f(n+1)=f(n)+t(n+1)+[\sqrt{n+1}]-[\sqrt{n}]$

If $n+1$ is a square,then $t(n+1)$ is odd,say $2m+1$ and $[\sqrt{n+1}]=[\sqrt{n}]+1$ .

So, $f(n+1)=2(k+m+1)$

If $n+1$ is not a square,then $t(n+1)$ is even,say $2p$ and $[\sqrt{n+1}]=[\sqrt{n}]$ .

So, $f(n+1)=2(k+p)$ .Hence,in both cases $f(n+1)$ is even and the lemma is proved.

Solution to the main problem

Hence $A=(n$ $such$ $that$ $[\sqrt{n}]$ $is$ $odd,1≤n≤2015)$ and $B=(n$ $such$ $that$ $[\sqrt{n}]$ $is$ $even,1≤n≤2015)$

Note that $44^{2}<2015≤45^2$

Now, $A=([(2k-1)^{2},(2k)^{2}-1],k=1,..22)$

So, $|A|=\sum_{k=1}^{22}((2k)^{2}-1-(2k-1)^{2}+1)=\sum_{k=1}^{22}(4k-1)=990$

So, $|B|=2015-990=1025$ .

So, $|A-B|=35$

I programmed the functions for t(n) and s(n) in Python, and used dynamic programming (http://en.m.wikipedia.org/wiki/Dynamic_programming) on t(n) so that I didn't have to calculate its value over and over again, and it also makes it so I have the computing capacity to calculate s(n). From there, I tested all values of s(n) between 1 and 2015 to see if they were odd or even to find A and B, then printed the absolute value of the difference between A and B.

 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

memo = {}
def t(n):
    if n in memo:
        return memo[n]
    count = 2
    i = 2
    while i <= n/2:
        if n % i == 0:
            count += 1
        i += 1
    memo[n] = count
    return count
def s(n):
    total = 0
    i = 1
    while i <= n:
        total += t(i)
        i += 1
    return total
n = 1
A = 0
B = 0
while n <= 2015:
    if s(n) % 2 != 0:
        A += 1
    else:
        B += 1
    n += 1
print abs(A-B)

That program is still pretty slow though, so then I reprogrammed s(n) to use dynamic programming:

1
2
3
4
5
6

memo2 = {1:t(1)}
def s(n):
    if n in memo2:
        return memo2[n]
    memo2[n] = s(n-1)+t(n)
    return memo2[n]