7
$\begingroup$

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

$\endgroup$
4
  • 4
    $\begingroup$ Is this homework? How many powers of 2 can divide your special numbers? $\endgroup$
    – user641
    Jul 1, 2011 at 11:27
  • $\begingroup$ We have holiday, i don't go to school :-) Is your question is a hint? $\endgroup$ Jul 1, 2011 at 11:52
  • 2
    $\begingroup$ 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? $\endgroup$
    – hardmath
    Jul 1, 2011 at 12:05
  • $\begingroup$ 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 ... $\endgroup$ Jul 1, 2011 at 12:07

4 Answers 4

15
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Thanks a lot ! Seems like experimenting is very useful, thanks for teaching me something :) And thanks for an so full answer. Chris $\endgroup$ Jul 1, 2011 at 14:20
  • 4
    $\begingroup$ +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... $\endgroup$ Jul 2, 2011 at 4:11
  • 3
    $\begingroup$ @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. $\endgroup$ Jul 2, 2011 at 4:28
1
$\begingroup$

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);
    }
}
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Jul 2, 2011 at 14:01
0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – TonyK
    Jul 1, 2011 at 13:46
  • $\begingroup$ @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. $\endgroup$ Jul 1, 2011 at 16:25
  • $\begingroup$ 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. $\endgroup$ Jul 2, 2011 at 4:43
  • $\begingroup$ I didn't want to give away the whole thing. $\endgroup$ Jul 2, 2011 at 13:25
0
$\begingroup$

If $2n$ is a divisor of $2m$1, then

$$ 2n \mid 2m \Leftrightarrow n \mid m $$

In other words, $2n$ is a divisor of $2m$ if and only if $n$ is a divisor of $m$. So for every even divisor of $2m$ there is a divisor of $m$, and for every divisor of $m$ there is an even divisor of $2m$. Now we conclude that the number of even divisors of $2m$ is equal to the number of divisors of $m$ (#).

Now if $2n - 1$ is a divisor of $2m$, then

$$ 2n - 1 \mid 2m \Leftrightarrow 2n - 1 \mid m $$

In other words, $2n - 1$ is a divisor of $2m$ if and only if $2n - 1$ is a divisor of $m$. So for every odd divisor of $2m$ there is an odd divisor of $m$ and for every odd divisor of $m$ there is an odd divisor of $2m$. Now we conclude that the number of odd divisors of $2m$ is equal to the number of odd divisors of $m$ (##).

If the number of even divisors of $2m$ is equal to the number of odd divisors of it, from ## and # we conclude that the number of divisors of $m$ is equal to the number of odd divisors of it, which means all of the divisors of $m$ are odd, so $m$ is odd.

So if the number of even divisors and odd divisors of $2m$ are equal, then $m$ is odd.

\begin{align} 2m &= 2(2n - 1) \\ &= 4n - 2 \\ &= 2 + 4(n - 1) \\ &= a_1 + d(n - 1), n \in \mathbb{N} \end{align}

Every term of the sequence of every other even number starting with $2$ has the property.


1.As you said the number has to be even so I wrote $2m$.
$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .