How many numbers in interval with k(odd) number of divisors?

by hemangsarkar, Nov 26, 2016, 7:41 PM

The problem is http://www.spoj.com/problems/ODDDIV/

We need to find the number of numbers in a given interval with k (an odd number) of divisors.
The interval can be $(1, 10^{10})$ in the worst case.

first observation

How to find number of divisors

How to find number of divisors 2

This should have worked?

Final Step

This post has been edited 2 times. Last edited by hemangsarkar, Nov 26, 2016, 7:45 PM

number theory

competitive coding

sieve

Number of subset pairs

by hemangsarkar, Jun 20, 2016, 7:10 AM

Q) Let A be a set of the first N positive integers :A={1,2,3,4.........N}.
Let B be the set containing all the subsets of A.
A relations is defined as follows:

R1={ (x,y) : x and y belong to B and x is not a subset of y and y is not a subset of x and the intersection of x and y is equal to empty set }

NOTE : (x,y) is the same as (y,x) ,i.e the pairs are unordered.

example:
Let A={1,2}
Then B={Phi,{1},{2},{1,2}}
Phi=Empty Set
So R1=Either {({1},{2})} or {({2},{1})} hence number of relations is 1.

Solution:

We are given a number $n$ , the first thing we need to think of is how many numbers from $1$ to $n$ can we use to make our relation? We can use a minimum of $2$ numbers and a maximum $n$ numbers.

Let us use say $p$ numbers where $2 \leq p \leq n$ .

Number of ways to select $p$ numbers out of $n$ numbers is $\binom{n}{p}$ .

Once we have selected $p$ numbers, we start thinking about our unordered pair $(x,y)$ .

$x$ can contain a minimum of $1$ and a maximum of $p-1$ numbers. Hence if we are considering ordered pairs then we can have a total of

$\binom{p}{1} + \binom{p}{2} + \binom{p}{3} + \cdots + \binom{p}{p-1}$

pairs.

We know that $\binom{p}{0} + \binom{p}{1} + \binom{p}{2} + \cdots + \binom{p}{p} = 2^{p}$ .

hence our required sum is $2^{p} - 2$ .

But this counts the number of ordered pairs and we want number of unordered pairs hence we divide by $2$ .

$2^{p-1} - 1$ pairs for $p$ numbers selected out of $n$ numbers.

We can easily see that the final answer will be:

$\sum_{p=2}^{n} \binom{n}{p}(2^{p-1} - 1)$

or, $\sum_{p=2}^{n} \binom{n}{p}2^{p-1} - \sum_{p=2}^{n} \binom{n}{p}$

or, $\left(\frac{1}{2}\right)\left(\sum_{p=0}^{n} \binom{n}{p}2^{p} -1 - 2n\right) - 2^{n} + 1 + n$

or, $\left(\frac{1}{2}\right)\left(\sum_{p=0}^{n} \binom{n}{p}2^{p} +1\right) - 2^{n}$

or, $\left(\frac{3^{n} + 1}{2}\right) - 2^{n}$

You can also go here to see another solution:
http://math.stackexchange.com/questions/216984/finding-the-number-of-subset-pairs-of-a-set

This post has been edited 2 times. Last edited by hemangsarkar, Jun 20, 2016, 8:05 AM

Coin Change Problem Recursive Solution

by hemangsarkar, Dec 31, 2015, 6:32 PM

Q) You are given a set A which has the values of say m coins and a positive integer n. You are asked to find the number of different ways you can use these coins to make a total of n. Assume you have an infinite supply of each type of coin.
Example: A = {1,2,3} and n=4. You can have 4 = 1 + 1 + 1 + 1, 1 + 3, 2+2, 2+1+1. Note that the order of the coins doesn't matter. There are 4 different ways to get 4 using these coins.

Solution:
Though the recursive solution is not at all optimal, it is good for a start to understand the problem.

Take any one coin from the set A.
Using this coin, we can divide the solution space into two parts. The first part uses this coin to get to n and the second part doesn't. These two parts are mutually exclusive and so if we add the number of solutions in each, we get the final answer.

We now make a function which illustrates the idea.
Here int A[] is the given array of coin values.
It is a 0 indexed array, so the values are A[0], A[1], ... , A[m-1]

int count( int A[], int m, int n )
{
// If n is 0 then there is 1 solution: do not include any coin
if (n == 0)
return 1;

// If n is less than 0 then no solution exists
if (n < 0)
return 0;

// If there are no coins and n is greater than 0, then no solution exists
if (m <=0 && n > 0)
return 0;

return count( A, m - 1, n ) + count( A, m, n-A[m-1] );
/*count( A, m - 1, n ) means the number of solutions which don't include A[m-1] and thus only have elements from A[0] to A[m-2].
and count(A, m, n-A[m-1]) has already included A[m-1] once. It might well come again and so we don't change m to m-1*/
}

simultaneous powers of 2

by hemangsarkar, Nov 18, 2015, 7:39 PM

Q) Find all positive integers $a$ and $b$ such that $36a+b$ and $36b+a$ are both powers of 2.

solution

This post has been edited 1 time. Last edited by hemangsarkar, Nov 18, 2015, 7:40 PM
Reason: added link

sum of powers of 5

by hemangsarkar, Nov 18, 2015, 7:33 PM

Q) Show that $5^{m} + 5^{n}$ can never be a perfect square for positive integers $m$ and $n$ .
Solution:
idea

This post has been edited 1 time. Last edited by hemangsarkar, Nov 18, 2015, 7:34 PM

inequality

by hemangsarkar, Nov 15, 2015, 9:34 PM

Show that
$4 < 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdots + \frac{1}{63} + \frac{1}{64} < 7$

answer

diophantine equation

by hemangsarkar, Nov 12, 2015, 5:11 PM

Q) Solve over integers $x^{2} + y^{2} + z^{2} = 2xyz$ .

Solution: The left hand side is even. Hence of $x, y$ and $z$ we must have either $0$ or $2$ odd numbers.
If we have $2$ odd numbers says $x$ and $y$ then

$x^{2} + y^{2}$ will be of form $4k+2$ and then LHS will be of form $4m + 2$ while RHS is divisible by $4$ .

Hence none of them is odd.

$x = 2u, y = 2v, z = 2w$

$u^{2} + v^{2} + w^{2} = 4uvw$

Continuing this way we see that $x, y, z$ must be divisible by all powers of $2$ .

The only solution possible here is $x = 0, y = 0 , z = 0$

Another Totient sum

by hemangsarkar, Nov 8, 2015, 12:07 PM

Q) $\sum_{k=1}^n gcd(k,n) = \sum_{d|n}d* \phi\left(\frac{n}{d}\right)$ where $\phi(n)$ is the Euler Totient function of $n$ .

Solution:
$gcd(k,n)$ for $1 \le k \le n$ will always be a value from the set of divisors of $n$ .

If we pick any divisor $d$ then we need to find out how many times does $d$ occur when $1 \le k \le n$ .

For each divisor $d$ of $n$ , let
$A(d)=\{k:(k,n)=d,1 \le k \le n\}$

That is, $A(d)$ contains the elements of $S$ which have the gcd $d$ with $n$ . The sets $A(d)$ form a disjoint collection whose union is $S$ .

Let $m$ be one element in $A(d)$ , then $gcd(m,n) = d$ .

hence $m = dl, n = dk$ where $gcd(l,k) = 1$ .

Also since $l \leq k$ and they are relatively prime we have $\phi(k) = \phi\left(\frac{n}{d}\right)$ choices for such $l$ .

Therefore if $f(d)$ denotes the number of integers in $A(d)$ we have

$f(d) = \phi\left(\frac{n}{d}\right)$

So the number of times $d$ occurs in $\sum_{k=1}^n gcd(k,n)$ is $\phi\left(\frac{n}{d}\right)$ .

$\sum_{k=1}^n gcd(k,n) = \sum_{d|n}f(d) = \sum_{d|n}d* \phi\left(\frac{n}{d}\right)$

It can be thus shown that

$\sum_{k=1}^n \frac{n}{gcd(k,n)} = \sum_{d|n}\left(\frac{n}{d}\right)\phi\left(\frac{n}{d}\right) = \sum_{d|n} d*\phi(d)$

This post has been edited 3 times. Last edited by hemangsarkar, Nov 8, 2015, 12:20 PM

Totient function sum of divisors

by hemangsarkar, Nov 8, 2015, 11:36 AM

Q) Let $n \geq 1$ then $\sum_{d|n}\phi(d) = n$ where $\phi(n)$ denotes the Euler Totient function of $n$ .

Solution:
Let $S$ denote the set $\{1,2,\cdots,n\}$ . We distribute the integers of $S$ into disjoint sets as follows. For each divisor $d$ of $n$ , let
$A(d)=\{k:(k,n)=d,1 \le k \le n\}$

That is, $A(d)$ contains the elements of $S$ which have the gcd $d$ with $n$ . The sets $A(d)$ form a disjoint collection whose union is $S$ .

Let $m$ be one element in $A(d)$ , then $gcd(m,n) = d$ .

hence $m = dl, n = dk$ where $gcd(l,k) = 1$ .

Also since $l \leq k$ and they are relatively prime we have $\phi(k) = \phi\left(\frac{n}{d}\right)$ choices for such $l$ .

Therefore if $f(d)$ denotes the number of integers in $A(d)$ we have

$f(d) = \phi\left(\frac{n}{d}\right)$

hence,

$\sum_{d|n}f(d) = \sum_{d|n}\phi\left(\frac{n}{d}\right) = \sum_{d|n}\phi(d) = n$ .

This post has been edited 4 times. Last edited by hemangsarkar, Nov 8, 2015, 11:56 AM

a regular pentagon with all vertices as lattice points?

by hemangsarkar, Oct 17, 2015, 1:42 PM

Q) In the coordinate plane, prove that the vertices of a regular pentagon cannot all be lattice points.

solution

hemangsarkar's blog