# finding the first odd abundant number less than $1000$

We say about number $n$ abundant if the sum of the divisors except $n$ is bigger than the number $n$.For example : $12$ is abundant because the sum of divisors except $12$ is bigger than $12$ : $1+2+3+4+6=16>12$ .How to find the first odd abundant number less than $1000$

-
"the first odd abundant number less than 1000": that's a strange way of putting it! If the smallest abundant number is less than 1000, then that's your answer right there; and if it's not, then your question is like "who is the present king of France?" –  TonyK Jan 21 '13 at 20:54
@TonyK The smallest abundant number. –  sen Jan 21 '13 at 20:57

We will take the problem to be finding the smallest abundant number, then will confirm that it is less than $1000.$ For a prime power $p^e$, the sum of divisors is $\sum_{i=1}^e p^i=\frac{p^{e+1}-1}{p-1}$. The sum of divisors function is multiplicative, so if $n=\prod_i p_i^{e_i}$, the sum of divisors of $n, \sigma(n) = \prod_i \frac{p_i^{e_i+1}-1}{p_i-1}$. We need $\frac {\sigma(n)}n =\prod_i \frac{p_i^{e_i+1}-1}{p_i^{e_i}(p_i-1)}=\prod_i 1+\frac {p_i^{e_i}-1}{p_i^{e_i}(p_i-1)}\gt 2$

If we make a table of $\frac{p_i^{e_i+1}-1}{p_i^{e_i}(p_i-1)}$ we get

$$\begin {array}&&3&5&7&11\\0&1&1&1&1\\ 1&1.333333&1.2&1.142857&1.090909\\ 2&1.444444&1.24&1.163265&1.099174\\ 3&1.481481&1.248&1.166181&1.099925\\ 4&1.493827&1.2496&1.166597&1.099993\\ 5&1.497942&1.24992&1.166657&1.099999\\ 6&1.499314&1.249984&1.166665&1.1\\ \end{array}$$

where the column is the prime and the row is the exponent. We want to find the set of entries that multiply to more than $2$ with the smallest product of prime powers. This makes us think that what as we increase the power of each prime, what we get is the difference of the log of the next entry and the current entry and what we pay is the log of the prime. So we make a new table that way

$$\begin{array} &&3&5&7&11\\ 1&0.26186&0.113283&0.068622&0.036287\\ 2&0.072858&0.020373&0.009096&0.003147\\ 3&0.023045&0.003996&0.001286&0.000285\\ 4&0.007554&0.000796&0.000184&2.59E-05\\ 5&0.002504&0.000159&2.62E-05&2.35E-06\\ 6&0.000833&3.18E-05&3.74E-06&2.14E-07\\ \end{array}$$

Using the greedy algorithm, the priority order of factors is $3,5,3,7,11,3,5\ldots$ leading to a series of candidates $3,15,45,315,3465$, but we see we can sneak another factor of $3$ onto $315$ giving $945$. The way the candidates stack up:

$$\begin{array} n&\sigma(n)&\frac {\sigma(n)}n\\ 3&4&1.333333\\ 15&24&1.6\\ 45&78&1.733333\\ 315&624&1.980952\\ 945&1920&2.031746\\ 3465&7488&2.161039 \end {array}$$

and $945$ is the first to exceed $2$. We get more "bang for the buck" with $3465$, but $945$ is good enough.

-

The oeis is a good source for sequences like these.

In particular, the answer is $945$.

If you want to check this particular example, you could do it as so in Wolfram|Alpha.

-

If you're familiar with a bit of R-programming, then you could try this script:

n <- 1000
o <- sapply(seq(3, n, by=2), function(x) {
t <- sapply(1:x-1, function(y) {
ifelse(x %% y == 0, y, 0)
})
t <- sum(t, na.rm = TRUE)
})
df <- data.frame(num = seq(3, n, by = 2), sum_div = o)
> df[with(df, sum_div > num), ]

#     num sum_div
# 472 945     975
-