login
Numbers k that can be written as the sum of 3 divisors of k (not necessarily distinct).
12

%I #50 Oct 30 2023 06:35:30

%S 3,4,6,8,9,12,15,16,18,20,21,24,27,28,30,32,33,36,39,40,42,44,45,48,

%T 51,52,54,56,57,60,63,64,66,68,69,72,75,76,78,80,81,84,87,88,90,92,93,

%U 96,99,100,102,104,105,108,111,112,114,116,117,120,123,124,126,128,129,132,135

%N Numbers k that can be written as the sum of 3 divisors of k (not necessarily distinct).

%C From _Bernard Schott_, Aug 06 2023: (Start)

%C Equivalently: positive numbers that are divisible by 3 or by 4.

%C Proof (similar to the proof proposed by _Robert Israel_ in A355641).

%C If k is divisible by 3, then k is in the sequence because k = k/3 + k/3 + k/3.

%C If k is divisible by 4, then k is in the sequence because k = k/2 + k/4 + k/4.

%C Moreover, if k is positive and divisible by 6 (A008588), then k = k/3 + k/3 + k/3, but k is also in the sequence because k = k/2 + k/3 + k/6.

%C Conversely, to show that every term of this sequence is divisible by 3 or by 4, we consider all positive integer solutions of the equation 1 = 1/a + 1/b + 1/c. Without loss of generality, we may assume a <= b <= c, then 3/a >= 1/a + 1/b + 1/c = 1. So a <= 3. Similarly, given a, we have 2/b >= 1/b + 1/c = 1 - 1/a, so b <= 2/(1 - 1/a).

%C -> if a = 1, then 1 = 1 + 1/b + 1/c; this equation has clearly no solution.

%C -> if a = 2, then 1/2 = 1/b + 1/c with b <= 2/(1 - 1/2) = 4; in this case, there are two solutions: (a,b,c) = (2,3,6) or (a,b,c) = (2,4,4).

%C -> if a = 3, then 2/3 = 1/b + 1/c with b <= 2/(1 - 1/3) = 3; in this case, there is one solution: (a,b,c) = (3,3,3).

%C It turns out that there are only 3 solutions with a <= b <= c. Each corresponds to a possible pattern k = k/a + k/b + k/c for writing k as the sum of 3 of its divisors, which works when k is divisible by 3 or by 4. (End)

%C From _David A. Corneth_, Aug 07 2023: (Start)

%C Proof that a(n + 6) = a(n) + 12.

%C As k is in the sequence, k = k/d1 + k/d2 + k/d3 where d1, d2 and d3 | k and they are not necessarily distinct. By discussion above from _Bernard Schott_, Aug 06 2023, (d1, d2, d3) are in {(2, 3, 6), (2, 4, 4), (3, 3, 3)}. The lcm of these tuples are 6, 4 and 3 respectively. So any number k in the sequence is divisible by 3, 4 or 6.

%C This tells us that if k is in the sequence then k + 12 is in the sequence since k + 12 is divisible by one of 3, 4 or 6 since lcm(3, 4, 6) = 12.

%C So we can write a(n + m) = a(n) + 12 for some m. Inspection gives m = 6 so a(n + 6) = a(n) + 12. (End)

%H Ray Chandler, <a href="/A355200/b355200.txt">Table of n, a(n) for n = 1..1000</a>

%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (2,-2,2,-2,2,-1).

%F a(n + 6) = a(n) + 12. - _David A. Corneth_, Oct 08 2022

%F Sum_{n>=1} (-1)^(n+1)/a(n) = 2*log(2)/3 - log(3)/4. - _Amiram Eldar_, Sep 10 2023

%F From _Wesley Ivan Hurt_, Oct 30 2023: (Start)

%F a(n) = 2*n + (sin(Pi*n/3) + sin(2*Pi*n/3))/sqrt(3).

%F a(n) = A005843(n) + A134667(n). (End)

%e 6 is in the sequence since it can be written as the sum of 3 of its (not necessarily distinct) divisors: 6 = 1+2+3 = 2+2+2 with 1|6, 2|6, and 3|6.

%t q[n_, k_] := AnyTrue[Tuples[Divisors[n], k], Total[#] == n &]; Select[Range[135], q[#, 3] &] (* _Amiram Eldar_, Aug 21 2022 *)

%t Table[2n + (Sin[Pi*n/3] + Sin[2*Pi*n/3])/Sqrt[3], {n, 100}] (* _Wesley Ivan Hurt_, Oct 30 2023 *)

%o (PARI) isok(k) = my(d=divisors(k)); forpart(p=k, if (setintersect(d, Set(p)) == Set(p), return(1)), , [3,3]); \\ _Michel Marcus_, Aug 21 2022

%o (PARI) is(n) = my(v = [3,4,6]); sum(i = 1, 3, n%v[i] == 0) > 0 \\ _David A. Corneth_, Oct 08 2022

%Y Cf. A002966, A008588, A348536.

%Y Numbers k that can be written as the sum of j divisors of k (not necessarily distinct) for j=1..10: A000027 (j=1), A299174 (j=2), this sequence (j=3), A354591 (j=4), A355641 (j=5), A356609 (j=6), A356635 (j=7), A356657 (j=8), A356659 (j=9), A356660 (j=10).

%Y Equals positive terms of A008585 union A008586.

%Y Cf. A005843, A134667.

%K nonn,easy

%O 1,1

%A _Wesley Ivan Hurt_, Jun 23 2022