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?
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
32) 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(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).
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?