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$
$\endgroup$ 23 Answers
$\begingroup$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.
$\endgroup$ $\begingroup$The oeis is a good source for sequences like these.
For example, your answer can be found here as linked from here.
In particular, the answer is $945$.
If you want to check this particular example, you could do it as so in Wolfram|Alpha.
$\endgroup$ $\begingroup$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
