Wikipedia:Reference desk/Archives/Mathematics/2018 November 17
| Mathematics desk | ||
|---|---|---|
| < November 16 | << Oct | November | Dec >> | Current desk > |
| Welcome to the Wikipedia Mathematics Reference Desk Archives |
|---|
| The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
November 17
editnth composite number divisible by n
editAre 1, 2, 5, 6, and 7 the only positive integers n for which the nth composite number is divisible by n? GeoffreyT2000 (talk) 16:14, 17 November 2018 (UTC)
- Looks like it. There aren't any other small ones, then the number of composite is more than half of the upper number so it can't divide it. Bubba73 You talkin' to me? 16:58, 17 November 2018 (UTC)
- Here's a proof. Please find a flaw if possible:
- The nth composite number is bounded below by n.
- Because all even numbers greater than 2 and some odd numbers are composite, the presence of at least 2 composite odd numbers proves that the nth composite number will always be less than 2n for all n where 2n > the second odd composite number (15.)
- Therefore, for all n >= 8, the nth composite number will be between n and 2n, and dividing it by n will give a number between 1 and 2 and thus it can't be an integer.
Can anyone find a flaw here?? Georgia guy (talk) 17:51, 17 November 2018 (UTC)
- I think that's right. After that point the ratio is always strictly between 1 and 2. Bubba73 You talkin' to me? 01:31, 18 November 2018 (UTC)
- A related question: If a(n) is the nth composite number, are there an infinite number of n's so that a(n)/n = 1+1/k for some k? For example (assuming my calculations are correct) a(n)/n = 3/2 for n = 24, 26, 28, 30, 32 and a(n)/n = 4/3 for n = 93, 96, 99, 105. Note that pi(a(n)) = a(n)-n+1 where pi is the Prime-counting function. --RDBury (talk) 05:08, 18 November 2018 (UTC)
- Do you mean for a fixed k? Off the top of my head, probably not. The primes form a less and less dense subset of the numbers, so the number of composites approaches 100%. So I think that eventually a(n)/n will be > 1+1/k for a fixed k, but I need to think about it more (later). Bubba73 You talkin' to me? 05:21, 18 November 2018 (UTC)
- I meant some k where k depends on n. (For a fixed k the number of n's would be finite by essentially the same proof as given above.) Actually, by applying the Prime number theorem I believe you can show a(n)/n ~ 1 + 1/log n, which gives ek as a ballpark estimate for n in terms of k. I did some number crunching and found that solutions exist for all k ≤ 14; for k = 14 there are 15 values of n ranging from 8921290 to 8922830. My processing power and programming skills are limited so 14 is about as high as I can go. --RDBury (talk) 12:02, 18 November 2018 (UTC)
- Correction, actually a(n)/n ~ 1 + 1/log n is obvious since a(n)/n and 1 + 1/log n are both ~1. What I should have said was a(n)/n = 1 + 1/log n + o(1/log n). --RDBury (talk) 17:58, 18 November 2018 (UTC)
- Using OEIS:A038625, the smallest n for k is around A038625(k+1)×k/(k+1). Assuming correctness of the OEIS sequence, the smallest for k = 1 to 49 is: 5, 24, 93, 276, 905, 2658, 7364, 21608, 58095, 159280, 440803, 1204344, 3272191, 8921290, 24257625, 65990992, 179408055, 487205532, 1324483920, 3599858180, 9781165863, 26580367572, 72229699468, 196296050304, 533467135175, 1449815874780, 3940263612747, 10709036057524, 29105918065900, 79107390087240, 215010172388833, 584394426250240, 1588390452684816, 4317301265437368, 11734671691292690, 31895736939042660, 86695604114932233, 235648080307087472, 640520326622683767, 1741020550592597280, 4732347545674762806, 12863257280167193676, 34964451581289156721, 95039423137755548716, 258334285328363071485, 702200908598678530374, 1908717748466836346374, 5188274437378776764592, 14102788619438915542083. My value for k = 14 agrees with RDBury. PrimeHunter (talk) 18:17, 18 November 2018 (UTC)
- I think I see what you're doing, so let me do an example and tell me know if it's what you had in mind. From OEIS you have pi(330) = 66. So taking a(n) = 330 in the equation pi(a(n))=a(n)-n-1 (I had a sign wrong above), and solving for n you get a(263)=330. Define f(n) = n-4(a(n)-n) = 5n-4a(n), so f(263)=-5. If n is increased by 1 then f(n) either increases by 1 or decreases (by 3), also f→∞ as n→∞, so f must eventually be 0 and since you're starting so close to 0 the computation to get to find the exact value where this happens is feasible. In fact you can iterate n→n-f(n)=4(a(n)-n) until you reach a fixed point, in this case 276 after 3 iterations. I'm guessing that Golomb's proof that the entries in A038625 always exist follows the same sort of logic, and it would imply that A038625(k) is always < the value of n we're looking for. In any case, the answer to the question posed above is yes, in fact for every k there is n so that a(n)/n = 1+1/k. It may also be interesting to note that the ratio of successive entries in your sequence seems to converge to e as you might expect. --RDBury (talk) 08:28, 19 November 2018 (UTC)
- Yes, that was basically my algorithm. After reading the terms of A038625, a PARI/GP line computed the list in 0.2s. PrimeHunter (talk) 11:48, 19 November 2018 (UTC)
- I think I see what you're doing, so let me do an example and tell me know if it's what you had in mind. From OEIS you have pi(330) = 66. So taking a(n) = 330 in the equation pi(a(n))=a(n)-n-1 (I had a sign wrong above), and solving for n you get a(263)=330. Define f(n) = n-4(a(n)-n) = 5n-4a(n), so f(263)=-5. If n is increased by 1 then f(n) either increases by 1 or decreases (by 3), also f→∞ as n→∞, so f must eventually be 0 and since you're starting so close to 0 the computation to get to find the exact value where this happens is feasible. In fact you can iterate n→n-f(n)=4(a(n)-n) until you reach a fixed point, in this case 276 after 3 iterations. I'm guessing that Golomb's proof that the entries in A038625 always exist follows the same sort of logic, and it would imply that A038625(k) is always < the value of n we're looking for. In any case, the answer to the question posed above is yes, in fact for every k there is n so that a(n)/n = 1+1/k. It may also be interesting to note that the ratio of successive entries in your sequence seems to converge to e as you might expect. --RDBury (talk) 08:28, 19 November 2018 (UTC)
- Using OEIS:A038625, the smallest n for k is around A038625(k+1)×k/(k+1). Assuming correctness of the OEIS sequence, the smallest for k = 1 to 49 is: 5, 24, 93, 276, 905, 2658, 7364, 21608, 58095, 159280, 440803, 1204344, 3272191, 8921290, 24257625, 65990992, 179408055, 487205532, 1324483920, 3599858180, 9781165863, 26580367572, 72229699468, 196296050304, 533467135175, 1449815874780, 3940263612747, 10709036057524, 29105918065900, 79107390087240, 215010172388833, 584394426250240, 1588390452684816, 4317301265437368, 11734671691292690, 31895736939042660, 86695604114932233, 235648080307087472, 640520326622683767, 1741020550592597280, 4732347545674762806, 12863257280167193676, 34964451581289156721, 95039423137755548716, 258334285328363071485, 702200908598678530374, 1908717748466836346374, 5188274437378776764592, 14102788619438915542083. My value for k = 14 agrees with RDBury. PrimeHunter (talk) 18:17, 18 November 2018 (UTC)
- Correction, actually a(n)/n ~ 1 + 1/log n is obvious since a(n)/n and 1 + 1/log n are both ~1. What I should have said was a(n)/n = 1 + 1/log n + o(1/log n). --RDBury (talk) 17:58, 18 November 2018 (UTC)
- I meant some k where k depends on n. (For a fixed k the number of n's would be finite by essentially the same proof as given above.) Actually, by applying the Prime number theorem I believe you can show a(n)/n ~ 1 + 1/log n, which gives ek as a ballpark estimate for n in terms of k. I did some number crunching and found that solutions exist for all k ≤ 14; for k = 14 there are 15 values of n ranging from 8921290 to 8922830. My processing power and programming skills are limited so 14 is about as high as I can go. --RDBury (talk) 12:02, 18 November 2018 (UTC)
- Do you mean for a fixed k? Off the top of my head, probably not. The primes form a less and less dense subset of the numbers, so the number of composites approaches 100%. So I think that eventually a(n)/n will be > 1+1/k for a fixed k, but I need to think about it more (later). Bubba73 You talkin' to me? 05:21, 18 November 2018 (UTC)