## An Abundance of Questions

Posted by DP on August 23, 2011 – 6:46 am

If the sum of the divisors of integer * n* is equal to 2*

*, we call the number perfect. For example, the divisors of 28 are 1, 2, 4, 7, 14, and 28. 1+2+4+7+14+28 = 56 = 28*2.*

**n**Similarly, if the sum of the divisors exceeds twice the number, we call the number

*abundant*. For example, 12 is abundant because the divisors of 12 are 1, 2, 3, 4, 6, and 12. 1+2+3+4+6+12 = 28 > 24 = 2*12. It’s

*abundance*is 28-24=4.

1) How many 2-digit *abundant numbers* are there?

2) What is the smallest odd *abundant number*?

3) What is the first *abundant number* not divisible by 2 or 3?

August 23rd, 2011 at 9:33 am

1) There are 21 2-digit abundant numbers

I have not found an abundant number yet that is odd or not divisible by 2 or 3. Still looking.

August 23rd, 2011 at 10:29 am

The first abundant odd number I have found is 945 – but I could be wrong…. seems a little high!

August 23rd, 2011 at 10:33 am

I agree with cazayoux, there are 21 2-digit abundant numbers.

12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56, 60, 66, 70, 72, 78, 80, 84, 88, 90, 96

The smallest odd abundant number is 945. Divisors are

1, 3, 5, 7, 9, 15, 21, 45, 27, 35, 45, 63, 105, 135, 189, 315, & 945

Will be back with the smallest ODD (must be odd otherwise it would be divisible by

~~3~~2) abundant number not divisible by 3.August 23rd, 2011 at 10:43 am

John 24 – Odd otherwise it would be divisible by 3?

Sure about 945? – I rushed it and am not convinced…? First number to spew out of the program!

August 23rd, 2011 at 12:19 pm

Karl,

Sorry for the typo. It is obviously 2.

945 was the first to spew out of my program as well. I am pretty confident in that number because it makes sense the number be divisible by 3, 5, 7 & 9 in order to get the most divisors as well as multiples of these divisors 15, 21, 27, etc.

I am at 800000+ in search of my odd abundant number not divisible by 3.

August 23rd, 2011 at 2:45 pm

I am still looking for the abundant number not divisible by 3. At 1 billion + and going slowly.

I did find lots of odd abundant numbers shown below in the format of Number, Factors and Sum of Factors.

945 – 1, 3, 5, 7, 9, 15, 21, 27, 35, 45, 63, 105, 135, 189, 315, 945 = 1920

1575 – 1, 3, 5, 7, 9, 15, 21, 25, 35, 45, 63, 75, 105, 175, 225, 315, 525, 1575 = 3224

2205 – 1, 3, 5, 7, 9, 15, 21, 35, 45, 49, 63, 105, 147, 245, 315, 441, 735, 2205 = 4446

2835 – 1, 3, 5, 7, 9, 15, 21, 27, 35, 45, 63, 81, 105, 135, 189, 315, 405, 567, 945, 2835 = 5808

3465 – 1, 3, 5, 7, 9, 11, 15, 21, 33, 35, 45, 55, 63, 77, 99, 105, 165, 231, 315, 385, 495, 693, 1155, 3465 = 7488

4095 – 1, 3, 5, 7, 9, 13, 15, 21, 35, 39, 45, 63, 65, 91, 105, 117, 195, 273, 315, 455, 585, 819, 1365, 4095 = 8736

4725 – 1, 3, 5, 7, 9, 15, 21, 25, 27, 35, 45, 63, 75, 105, 135, 175, 189, 225, 315, 525, 675, 945, 1575, 4725 = 9920

5355 – 1, 3, 5, 7, 9, 15, 17, 21, 35, 45, 51, 63, 85, 105, 119, 153, 255, 315, 357, 595, 765, 1071, 1785, 5355 = 11232

5775 – 1, 3, 5, 7, 11, 15, 21, 25, 33, 35, 55, 75, 77, 105, 165, 175, 231, 275, 385, 525, 825, 1155, 1925, 5775 = 11904

5985 – 1, 3, 5, 7, 9, 15, 19, 21, 35, 45, 57, 63, 95, 105, 133, 171, 285, 315, 399, 665, 855, 1197, 1995, 5985 = 12480

6435 – 1, 3, 5, 9, 11, 13, 15, 33, 39, 45, 55, 65, 99, 117, 143, 165, 195, 429, 495, 585, 715, 1287, 2145, 6435 = 13104

6615 – 1, 3, 5, 7, 9, 15, 21, 27, 35, 45, 49, 63, 105, 135, 147, 189, 245, 315, 441, 735, 945, 1323, 2205, 6615 = 13680

6825 – 1, 3, 5, 7, 13, 15, 21, 25, 35, 39, 65, 75, 91, 105, 175, 195, 273, 325, 455, 525, 975, 1365, 2275, 6825 = 13888

7245 – 1, 3, 5, 7, 9, 15, 21, 23, 35, 45, 63, 69, 105, 115, 161, 207, 315, 345, 483, 805, 1035, 1449, 2415, 7245 = 14976

7425 – 1, 3, 5, 9, 11, 15, 25, 27, 33, 45, 55, 75, 99, 135, 165, 225, 275, 297, 495, 675, 825, 1485, 2475, 7425 = 14880

7875 – 1, 3, 5, 7, 9, 15, 21, 25, 35, 45, 63, 75, 105, 125, 175, 225, 315, 375, 525, 875, 1125, 1575, 2625, 7875 = 16224

8085 – 1, 3, 5, 7, 11, 15, 21, 33, 35, 49, 55, 77, 105, 147, 165, 231, 245, 385, 539, 735, 1155, 1617, 2695, 8085 = 16416

8415 – 1, 3, 5, 9, 11, 15, 17, 33, 45, 51, 55, 85, 99, 153, 165, 187, 255, 495, 561, 765, 935, 1683, 2805, 8415 = 16848

8505 – 1, 3, 5, 7, 9, 15, 21, 27, 35, 45, 63, 81, 105, 135, 189, 243, 315, 405, 567, 945, 1215, 1701, 2835, 8505 = 17472

8925 – 1, 3, 5, 7, 15, 17, 21, 25, 35, 51, 75, 85, 105, 119, 175, 255, 357, 425, 525, 595, 1275, 1785, 2975, 8925 = 17856

9135 – 1, 3, 5, 7, 9, 15, 21, 29, 35, 45, 63, 87, 105, 145, 203, 261, 315, 435, 609, 1015, 1305, 1827, 3045, 9135 = 18720

9555 – 1, 3, 5, 7, 13, 15, 21, 35, 39, 49, 65, 91, 105, 147, 195, 245, 273, 455, 637, 735, 1365, 1911, 3185, 9555 = 19152

9765 – 1, 3, 5, 7, 9, 15, 21, 31, 35, 45, 63, 93, 105, 155, 217, 279, 315, 465, 651, 1085, 1395, 1953, 3255, 9765 = 19968

It is curious that all of the numbers are also 945 + 210*x where x is some number but not necessarily all numbers 1-14.

945 + 210 * 3 = 1575

945 + 210 * 6 = 2205

945 + 210 * 9 = 2835

945 + 210 * 12 = 3465

945 + 210 * 15 = 4095

945 + 210 * 18 = 4725

945 + 210 * 21 = 5355

but then the formula breaks its pattern of jumping by 3s

945 + 210 * 23 = 5775

945 + 210 * 24 = 5985

and further breaks down on the next 2 numbers

945 + 210 * 24 + 450 * 1 = 6435

945 + 210 * 24 + 450 * 1 + 180 * 1 = 6615

but notice 450 + 180 is 630.

There has to be a reason why the numbers increase by such a constant rate.

So I went to 100000 and the spreads between each abundant number change and include many values almost all of which are multiples of 30. The only Abundant Odd Number which is not an increase of a multiple of 30 is 81081 which is 546 greater than the previous AON and 504 less than the next AON.

So what do all of these values have in common? This is a mostly complete list of the increments between AONs.

30, 60, 90, 120, 150, 180, 210, 240, 270, 360, 420, 450, 540, 504, 546, 570, 630, 720, 840, 990, 1010, 1050, 1260, 1350, 1680

These are all the result of multiplying prime numbers 2, 3, 5, 7, 9, 11, 13 using each value as many times as needed.

30 = 2 * 3 * 5

60 = 2 * 2 * 3 * 5

90 = 2 * 3 * 3 * 5

etc.

seems to me this could be used to find the next value without trying every number.

945 + 210 * 23 = 6435

August 24th, 2011 at 10:00 am

My guess for the last item is 5^2*7*11*13*17*19*23*29. I am almost certain that this is the smallest one (you can at least check that the number is indeed abundant), but to completely prove that I need more time that I don’t have right now. I will not reveal my solution for the moment being and will let the others come up with their own arguments (mathematical, not programming )

P.S. Once again Math beated CS – good luck finding the answer with your programmed loops

August 24th, 2011 at 10:04 am

Forgot to do the multiplication – my number is 5391411025

August 24th, 2011 at 10:25 am

My program is chugging along very slowly and I considered using the prime factorization method but didn’t have time to work on it by hand or program.

It has to be a number with a great deal of factors otherwise it wouldn’t sum to greater than twice its original value.

Your answer definitely has both a great deal of factors and is abundant but is it the smallest.

btw it may take days for my program to get to 5.391 billion.

August 24th, 2011 at 10:53 am

Slavy,

Your answer does make sense when you figure it cannot have a prime factor of 2 or 3 otherwise it would be an even number and/or one divisible by 3.

It also makes sense that you could start with 5 and build your way up to your answer very quickly.

5*7

5*7*11

5*7*11*13

5*7*11*13*17

5*7*11*13*17*19

5*7*11*13*17*19*23

5^2*7*11*13*17*19*23 2 * 5391411250 = 10,782,822,050

August 24th, 2011 at 10:55 am

Sorry previous post got mangled.

Slavy,

Your answer does make sense when you figure it cannot have a prime factor of 2 or 3 otherwise it would be an even number and/or one divisible by 3.

It also makes sense that you could start with 5 and build your way up to your answer very quickly.

5*7

5*7*11

5*7*11*13

5*7*11*13*17

5*7*11*13*17*19

5*7*11*13*17*19*23

5^2*7*11*13*17*19*23 notice 5^2 would be the next odd value not divisible by 3

5*7*11*13*17*19*23*29

5^2*7*11*13*17*19*23*29

The factors of 5391411025 are

1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 35, 55, 65, 77, 85, 91, 95, 115, 119, 133, 143, 145, 161, 175, 187, 203, 209, 221, 247, 253, 275, 299, 319, 323, 325, 377, 385, 391, 425, 437, 455, 475, 493, 551, 575, 595, 665, 667, 715, 725, 805, 935, 1001, 1015, 1045, 1105, 1235, 1265, 1309, 1463, 1495, 1547, 1595, 1615, 1729, 1771, 1885, 1925, 1955, 2093, 2185, 2233, 2261, 2275, 2431, 2465, 2639, 2717, 2737, 2755, 2975, 3059, 3289, 3325, 3335, 3451, 3553, 3575, 3857, 4025, 4147, 4199, 4301, 4669, 4675, 4807, 5005, 5075, 5083, 5225, 5423, 5525, 5681, 6061, 6175, 6325, 6409, 6545, 7163, 7315, 7337, 7429, 7475, 7735, 7975, 8075, 8645, 8671, 8855, 9367, 9425, 9775, 10465, 10925, 11165, 11305, 11339, 12155, 12325, 12673, 13195, 13585, 13685, 13775, 15295, 16445, 16675, 17017, 17255, 17765, 19019, 19285, 20735, 20995, 21505, 23023, 23345, 24035, 24871, 25025, 25415, 27115, 28405, 29029, 29393, 30107, 30305, 32045, 32725, 33649, 35581, 35815, 36575, 36685, 37145, 37961, 38675, 39767, 42427, 43225, 43355, 44275, 44863, 46189, 46835, 50141, 51359, 52003, 52325, 55825, 55913, 56525, 56695, 60697, 60775, 62491, 63365, 65569, 65975, 67925, 68425, 70499, 76475, 78793, 79373, 81719, 82225, 85085, 86275, 88711, 88825, 95095, 95381, 96425, 96577, 103037, 103675, 104975, 107525, 115115, 116725, 120175, 121771, 124355, 124729, 127075, 135575, 139403, 142025, 145145, 146965, 147407, 150535, 151525, 160225, 164749, 168245, 177905, 179075, 183425, 185725, 189805, 198835, 212135, 215441, 216775, 224315, 230945, 234175, 250705, 256795, 260015, 279565, 283475, 303485, 312455, 316825, 323323, 327845, 352495, 391391, 393965, 396865, 408595, 425425, 437437, 443555, 475475, 476905, 482885, 493493, 515185, 551551, 572033, 575575, 608855, 621775, 623645, 667667, 676039, 697015, 721259, 725725, 734825, 737035, 752675, 823745, 841225, 852397, 873103, 889525, 949025, 975821, 994175, 1031849, 1060675, 1062347, 1077205, 1121575, 1153243, 1154725, 1253525, 1283975, 1300075, 1339481, 1397825, 1508087, 1517425, 1562275, 1616615, 1621477, 1639225, 1762475, 1812239, 1956955, 1969825, 1984325, 2042975, 2187185, 2217775, 2369851, 2384525, 2414425, 2467465, 2575925, 2757755, 2800733, 2860165, 3044275, 3118225, 3338335, 3380195, 3485075, 3606295, 3685175, 4118725, 4261985, 4365515, 4879105, 5159245, 5311735, 5386025, 5766215, 6697405, 7436429, 7540435, 8083075, 8107385, 9061195, 9376367, 9784775, 10935925, 11350339, 11849255, 12337325, 12685673, 13788775, 14003665, 14300825, 16588957, 16691675, 16900975, 18031475, 19605131, 21309925, 21827575, 24395525, 25796225, 26558675, 28831075, 30808063, 33487025, 37182145, 37702175, 40536925, 45305975, 46881835, 56751695, 59246275, 63428365, 70018325, 82944785, 98025655, 154040315, 185910725, 215656441, 234409175, 283758475, 317141825, 414723925, 490128275, 770201575, 1078282205, 5391411025

SUM = 10,799,308,800 > 2 * 5391411250 = 10,782,822,050

August 24th, 2011 at 2:15 pm

Hi John24. This is the beauty of Math – I can prove that this is the smallest abundant number that is not divisible by 2 and 3, and the only thing I used is a calculator (and logic of course). So I am already sure that my answer is correct and will leave the details to the others (the solution is technical and lengthy so I have no intentions to publish is soon). I would like to see the solution of DP, as well, provided he has one.

August 30th, 2011 at 10:17 am

Well, you have all figured it out. I’ll post the answers anyway, just to make it official.

1) There are 21 2-digit abundant numbers (12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56, 60, 66, 70, 72, 78, 80, 84, 88, 90, & 96) – found by cazayoux & John

2) The smallest odd abundant number is 945 – found by Karl & John

3) This one was a bit harder. The final answer is 5391411025 – found by Slavy

I’m sure to your disappointment, I don’t have any other magical solution.

http://en.wikipedia.org/wiki/Abundant_number

This site gives mention to an algorithm by Lannucci:

(1 − ε)(k lnk)^(2 – ε) < lnA(k) < (1 − ε)(k lnk)^(2 + ε)

For ε>0, and k sufficiently large

Where A(k) represents the smallest abundant number not divisible by the first k primes.

I also had another interesting find while looking for solutions to this one. Amicable numbers are a pair of one abundant number and one deficient number, where the sum of their proper divisors equals the other.

A deficient number is one where the sum of it’s divisors is less than twice the number. (10: 1+2+5+10 = 18 < 20 = 2*10)

A proper divisor is any divisable integer of n that is greater than 0 and less than n.

The smallest pair of amicable numbers is 220 & 284.

220: 1+2+4+5+10+11+20+22+44+55+110 = 284

284: 1+2+4+71+142 = 220

August 31st, 2011 at 2:30 pm

I can spend half an hour now, so let me try to explain the strategy (I present the ideas on an intuitive level without the technical mathematical arguments behind them). First of all, if the number N has decomposition N=(p1^n1)*(p2^n2)*…(pk^nk) for some prime factors p1, p2, … , pk and positive integers n1, n2, …, nk, then the sum s(N) of all his divisors including N is given by the formula

s(N)=(1+p1+p1^2…+p1^n1)*(1+p2+p2^2…+p2^n2)*…*(1+pk+pk^2…+pk^nk).

Now the number N is abundant, if s(N)>2N which, after dividing by N, is equivalent to

s(N)/N=(1+1/p1+(1/p1)^2+…+(1/p1)^n1)*…*(1+1/pk+(1/pk)^2+…+(1/pk)^nk)>2.

But for every p and n, the finite sum 1+1/p+…+(1/p)^n is smaller than the power series \sum_{n from 0 to infinity} (1/p)^n=p/(p-1).

In order N to be as small as possible it is clear that its factorization should contain the smallest possible prime numbers. From the computation above we see, that for every number M that is a power of 5, we have s(M)/M<5/4<2. Analogously, if M is a product of powers of 5 and 7 we have s(M)/M<5/4*7/6<2 and so on. Since (5/4)*(7/6)*(11/10)*(13/12)*(17/16)*(19/18)*(23/22)=2.0376… is the first product, bigger than 2, we see that the smallest abundant N not divisible by 2 or 3 should be divisible by at least 5,7,11,13,17,19, and 23. However, the estimation p/(p-1) can not be achieved since it involves infinite powers. On the other hand, 1+1/p+1/p^2=(1+1/p)*(p^2+p+1)/(p^2+p) meaning that allowing higher powers of p in the factorization increases the product s(N)/N only (p^2+p+1)/(p^2+p) times, while the number N has been increased p times. From this point of view, the optimal strategy should lead to N=5^n1*p2*p3*…*pk, and thus s(N)/N2 and another direct computation gives n1=2 and the final answer N=5391411025.

August 31st, 2011 at 2:37 pm

The last part of my post has disappeared so let me repeat it: For N=5^n1*7*11*13*…, we have that s(N)/N is smaller than 2 until pk=29, when the product 5/4*8/7*12/11*14/13*18/17*20/19*24/23*30/29>2. Hence, N=5^n1*7*11*13*17*19*23*29 and it remains to check which is the minimal n1 such that s(N)/N is bigger than 2. Direct computation leads to n1=2 and the final answer N=5391411025.

August 31st, 2011 at 3:26 pm

Hi slavy. Thanks for the explanation.

Sometimes text disappears if you use the “<” sign. If you put a space after it, then you are less likely to get a problem. The safest way is to type “& l t ;” (without the spaces). Similarly “& g t ;” for the > sign – but that doesn’t have so many problems. The problem arises because the < sign looks like the beginning of an html tag sequence.

September 1st, 2011 at 1:31 am

Hi Chris, I’ve noticed that and am trying to replace the “(pk+1)/pk, meaning that the number N1=7^n1*11^2*13*17*…*p(k-1) is smaller than N2=7^n1*11*13*…*p(k-1)*pk and has even bigger s(N)/N ratio. Therefore, one needs to consider several cases, which is not so pleasant if done manually (by calculator) but should not be that difficult to be encoded in a computer routine… To test the program you already have the numbers 945 and 5391411025 (I didn’t mention it explicitly, but it is clear that my algorithm works for the second item of the problem, as well). Good luck

September 1st, 2011 at 1:32 am

Hi Chris, I’ve noticed that and am trying to replace the “bad” sign by the word “smaller” at most of the places, but sometimes I forget. I haven’t ignored your question regarding the relation between the quadratic residuals of 3 and p, but I still didn’t have time to provide an answer there.

To show that the ToM people are smarter than wikipedia, I encourage John24 and all the other programmers here to try to use the recipe I gave for finding the smallest abundant number that does not divide 2,3, and 5. This tusk is trickier since the second estimation for the minimal pk (that was pk=29 in post#14) should give rise to a relatively big prime number. Thus, if such pk is bigger than 132 then (11^2+11+1)/(11^2+11)>(pk+1)/pk, meaning that the number N1=7^n1*11^2*13*17*…*p(k-1) is smaller than N2=7^n1*11*13*…*p(k-1)*pk and has even bigger s(N)/N ratio. Therefore, one needs to consider several cases, which is not so pleasant if done manually (by calculator) but should not be that difficult to be encoded in a computer routine… To test the program you already have the numbers 945 and 5391411025 (I didn’t mention it explicitly, but it is clear that my algorithm works for the second item of the problem, as well). Good luck

September 1st, 2011 at 3:57 am

Hi slavy. I knew you had the right answer ages ago. I did some Googling because I decided that I couldn’t see a nice way to do the problem, and didn’t want to do number crunching.

I found a page which introduced the divisor function. It claimed that the divisor function is (partially) multiplicative i.e. if gcd(a,b) = 1, s(a*b) = s(a)*s(b), allowing the effect of each prime to be considered in isolation. Also, for a prime p, s(p

^{n}) = (p^{n+1}-1)/(p-1). So for n = 1, s(p) = p+1.But you have got it pretty well covered. It does seem to need trial and error to find a solution satisfying a constraint.

Don’t worry about the QR stuff, there’s too much material for you to explain, and there’s tons of info on the internet. I’ve seen enough to cause me to believe that the mod 12 thingy can be derived from the main theorem (i.e. it doesn’t have to be written as an explicit supplement).

September 5th, 2011 at 7:37 pm

Hi slavy. I’ve just noticed that you are an author. You should be able to edit your own posts, but you’d have to log in when you post the comment and again when you edit it. Logging in is necessary for this site to recognise you properly.

September 6th, 2011 at 1:37 am

Hi Chris. Thanks for the info – I didn’t know that I’ll keep this in mind for the future. Thanks also for the detailed explanations of the “residual” problem – I did that stuff (all the steps mentioned by you) once in high school with the national mathematical team, but I never used it afterwards and this material is not part of the Number Theory university courses, so I just took it out of my head

May 22nd, 2012 at 1:33 pm

Was anyone able to find Slavy’s abundant number, not divisible by 2, 3, or 5?