Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

With given number N, how to determine first number after N with same amount of odd and even divisors? For example if we have N=1, then next number we are searching for is :

2
because divisors:
odd : 1
even : 2

I figured out that this special number can't be odd and obviously it can't be prime. I can't find any formula for this or do i have just compute it one by one and check if it's this special number ? Obviously 1 and number itself is divisors of this number. Cheers

share|improve this question
4  
Is this homework? How many powers of 2 can divide your special numbers? –  user641 Jul 1 '11 at 11:27
    
We have holiday, i don't go to school :-) Is your question is a hint? –  Chris Jul 1 '11 at 11:52
2  
Here's a hint. Try and pair up the even and odd factors in a natural way. You gave 2 = 1*2 as an example. How about factors of 2p, where p is an odd prime? –  hardmath Jul 1 '11 at 12:05
    
Whenever you have two finite sets of the same size, you can think about whether there is a one-to-one correspondence (a bijection) between them. You might think whether you could apply this observation to the divisors of a number ... –  Mark Bennet Jul 1 '11 at 12:07
add comment

3 Answers 3

up vote 7 down vote accepted

To get some idea of what's going on, we do like other scientists do, we experiment.

Special numbers will be even, so we write down the number of odd divisors, even divisors, for the even numbers, starting with $2$. If a number turns out to be special, we put a $\ast$ in its row.

So we make a table, giving the number, how many odd divisors it has, how many even. Calculations are easy, but we must be very careful, since errors could lead us down the wrong path.

$2 \qquad 1 \qquad 1\quad\ast$

$4 \qquad 1 \qquad 2$

$6 \qquad 2 \qquad 2\quad\ast$

$8 \qquad 1 \qquad 3$

$10 \qquad 2 \qquad 2\quad\ast$

$12 \qquad 2 \qquad 4$

$14 \qquad 2 \qquad 2\quad\ast$

$16 \qquad 1 \qquad 4$

$18 \qquad 3 \qquad 3\quad\ast$

We could easily go on for a while. It is definitely not a waste of time, since it is useful to be well-acquainted with the structure of the smallish numbers that we bump into often.

A pattern seems to jump out: every second even number seems to be special. It looks as if "special" numbers are not all that special! It can be dangerous to jump to conclusions from data about small integers. But in this case, the conclusion turns out to be correct.

The special numbers, so far, all have the shape $2a$, where $a$ is an odd number. They are divisible by $2$ but not by $4$. The even numbers in our list that are not special are all divisible by $4$.

Now we try to prove that every number that is divisible by $2$ but not by $4$ is special, and that the others are not.

Take an odd number $b$, and look at the number $2b$. Think about the divisors of $2b$. If $k$ is an odd divisor of $2b$, then $2k$ is an even divisor of $2b$, and vice-versa.

If $k$ is an odd divisor of $2b$, call $2k$ the friend of $k$. Split the divisors of $2b$ into pairs of friends. For example, if $b=45$, we have the following pairs of friends.

$$(1,2)\qquad (3,6) \qquad(5,10)\qquad(9,18)\qquad(15,30) \qquad (45,90)$$

We have split the divisors of $2b$ into pairs of friends. Each pair has one odd number and one even number, so $2b$ has exactly as many odd divisors as even divisors.

Now let's show that no number divisible by $4$ can be special. The idea is that if a number is divisible by $4$, then it has "too many" even divisors. I will not write out the details, but you should. The idea goes as follows. Take a number $n$ that is divisible by $4$, like $36$ or $80$. Split the divisors of $n$ into teams. If $k$ is an odd divisor of $n$, put into the same team as $k$ the numbers $2k$, $4k$, and so on however far you can go.

Here are the teams for $n=36$. $$(1,2,4) \qquad (3,6,12)\qquad (9,18,36)$$

Each team has more even numbers than odd numbers, so $n$ has more even divisors than odd divisors. That means $n$ can't be special.

Now let's get to your question: what is the first special number after $N$?

If $N$ is divisible by $4$, the first special number after $N$ is $N+2$. If $N$ is divisible by $2$ but not by $4$, the first special number after $N$ is $N+4$. If $N$ has remainder $1$ on division by $4$, the first special after $N$ is $N+1$, and if the remainder is $3$, the first special is $N+3$. These facts follow easily from what we have discovered about special numbers.

Formulas: We have been operating without formulas, just straight thinking. But I should mention a relevant formula. Let $n$ be an integer greater than $1$, and express $n$ as a product of powers of distinct primes. In symbols, let $$n=p_1^{a_1}p_2^{a_2} \cdots p_k^{a_k}$$ Then the number of divisors of $n$ is given by $$(a_1+1)(a_2+1) \cdots(a_k+1)$$

For example, $720=2^43^25^1$. The number of (positive) divisors of $n$ is $(4+1)(2+1)(1+1)$.

The formula that gives the number of divisors of $n$ is not hard to prove. Try to produce a proof! The formula could be adapted to give a count of the odd divisors of $n$, and of the even divisors. Then we could use these formulas to identify the special numbers. But formulas cannot do the thinking for you. So as a first approach, the way we tackled things is much better than trying to use a formula.

share|improve this answer
    
Thanks a lot ! Seems like experimenting is very useful, thanks for teaching me something :) And thanks for an so full answer. Chris –  Chris Jul 1 '11 at 14:20
2  
+1; this answer embodies a very important lesson. A lot of questions here on math.SE could have been answered by the posters if they had decided to experiment first... –  Qiaochu Yuan Jul 2 '11 at 4:11
1  
@Qiaochu Yuan: A very common problem with students is that they do not really understand that mathematical questions, even those that seem quite abstract, are about concrete things. Unlike working mathematicians, students, even pretty good ones, are often naive formalists. –  André Nicolas Jul 2 '11 at 4:28
add comment

I wrote a C++ application. My results are all the following numbers:

0, 2, 6, 10, 14, 18, 22, 26, 30, 34, ....

So, first zero, then two and then each time plus 4.

This means in general that if $n \equiv 2 (mod 4) $ is true, your number is one of the kind you're searching. Except from the first zero.

Here is the code of the application:

for (int i = 0; i < 1000; i += 2)
// Always +2 because of odd numbers don't have any even divisors
{
    int even = 0;
    int odd = 0;
    for (int d = 1; d <= i; ++d)
    {
        if (i % d == 0)
        {
            if (d % 2 == 0)
            {
                even++;
            } else
            {
                odd++;
            }
        }
    }
    if (even == odd)
    {
        printf("%d\n", i);
    }
}
share|improve this answer
    
We know that there's always 1 divisor odd ( 1 ) and 1 divisor even for sure ( N ), so we need only to check to n/2 or even to sqrt(n) ( not sure if we won't miss some of divisors expect n/2 ). But nice application. –  Chris Jul 2 '11 at 14:01
add comment

For a given integer $n$, every divisor larger than $\sqrt{n}$ is paired with a divisor smaller than $\sqrt{n}$. Use this to figure out a general principle.

share|improve this answer
    
I don't think that's very much help in this case. There is a much simpler way, hinted at in the comments to the OP. –  TonyK Jul 1 '11 at 13:46
    
@TonyK - I think this works as a pairing for this problem, though it involves making sure that you know that $n$ is not a square, so that there is a pairing - but since the number of distinct factors is known to be even, n can't be a square. –  Mark Bennet Jul 1 '11 at 16:25
    
The pairing works of ncmathsadist works just fine, both for the proof that we have equality when $n \equiv 2 \pmod{4}$, and that there are more even divisors than odd when $n \equiv 0 \pmod{4}$. The pairing is in effect the same as mine when $n \equiv 2 \pmod 4$. But the mathematical description of the pairing is substantially better than mine, because the ncmathsadist pairing has a number of other uses. More detail would undoubtedly have been useful to the student. –  André Nicolas Jul 2 '11 at 4:43
    
I didn't want to give away the whole thing. –  ncmathsadist Jul 2 '11 at 13:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.