Subscribe via feed.

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*n, 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.
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?


This post is under “MathsChallenge” and has 22 respond so far.
If you enjoy this article, make sure you subscribe to my RSS Feed.

22 Responds so far- Add one»

  1. 1. cazayoux Said:

    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.

  2. 2. Karl Sharman Said:

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

  3. 3. John24 Said:

    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.

  4. 4. Karl Sharman Said:

    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!

  5. 5. John24 Said:

    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.

  6. 6. John24 Said:

    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

  7. 7. slavy Said:

    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 )

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

  8. 8. slavy Said:

    Forgot to do the multiplication – my number is 5391411025

  9. 9. John24 Said:

    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.

  10. 10. John24 Said:

    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

  11. 11. John24 Said:

    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

  12. 12. slavy Said:

    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.

  13. 13. DP Said:

    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

  14. 14. slavy Said:

    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.

  15. 15. slavy Said:

    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.

  16. 16. Chris Said:

    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.

  17. 17. slavy Said:

    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 :)

  18. 18. slavy Said:

    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 :)

  19. 19. Chris Said:

    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(pn) = (pn+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).

  20. 20. Chris Said:

    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.

  21. 21. slavy Said:

    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 :(

  22. 22. DP Said:

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

Post a reply




PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0