cp's OEIS Frontend

A269347 With a(1) = 1, a(n) is the sum of all 0 < m < n for which a(m) divides n.

%I A269347 #45 Nov 18 2022 03:39:23
%S A269347 1,1,3,3,3,15,3,3,30,3,3,51,3,3,84,3,3,111,3,3,150,3,3,195,3,3,246,3,
%T A269347 3,318,3,3,366,3,3,435,3,3,510,3,3,591,3,3,684,3,3,771,3,3,882,3,3,
%U A269347 975,3,3,1086,3,3,1218,3,3,1326,3,3,1455
%N A269347 With a(1) = 1, a(n) is the sum of all 0 < m < n for which a(m) divides n.
%C A269347 For n > 2, I can prove that a(n) = 3 if 3 does not divide n, and in general, 3 divides a(n).
%C A269347 The base case is a(3) = 3. Suppose that the results hold for a(n) over 3 < n < k; we will show that the results hold for a(k) also. In the case that 3 does not divide k, then a(k) = 3, since a(1) and a(2) divide k but no other previous term can. This proves the first claim.
%C A269347 Otherwise, if 3 does divide k, then a(m) divides k for each 0 < m < k not divisible by 3; these numbers can be divided into k/3 pairs so that the sum of each pair is congruent to 0 modulo 3 (for instance, 1 + 2 == 4 + 5 == 7 + 8 == ... == 0 (mod 3)). If a(m) divides k for some 0 < m < k divisible by 3, this m does not change the congruence class of the sum that forms a(k). Thus, a(k) == 0 (mod 3) as required to prove the second claim.
%H A269347 Chai Wah Wu, <a href="/A269347/b269347.txt">Table of n, a(n) for n = 1..10000</a> (n = 1..1000 from Alec Jones)
%e A269347 a(1) = 1;
%e A269347 a(2) = 1 because a(1) divides 2;
%e A269347 a(3) = 3 because a(1) and a(2) divide 3: 1+2=3;
%e A269347 a(4) = 3 because a(1) and a(2) divide 4: 1+2=3;
%e A269347 a(5) = 3 because a(1) and a(2) divide 5: 1+2=3;
%e A269347 a(6) = 15 because a(1), a(2), a(3), a(4), and a(5) divide 6: 1+2+3+4+5=15.
%t A269347 a = {1}; Do[AppendTo[a, Total@ Select[Range[n - 1], Divisible[n, a[[#]]] &]], {n, 2, 66}]; a (* _Michael De Vlieger_, Mar 24 2016 *)
%o A269347 (Java)
%o A269347 int[] terms = new int[1000];
%o A269347 terms[0] = 1;
%o A269347 for (int i = 1; i < 1000; i++) {
%o A269347      int count = 0;
%o A269347      for (int j = 0; j < i; j++) {
%o A269347           if ((i + 1) % terms[j] == 0) {
%o A269347                count = count + (j + 1);
%o A269347           }
%o A269347      }
%o A269347      terms[i] = count;
%o A269347 }
%o A269347 (PARI) lista(nn) = {va = vector(nn); va[1] = 1; for (n=2, nn, va[n] = sum(k=1, n-1, k*((n % va[k])==0));); va;} \\ _Michel Marcus_, Feb 24 2016
%o A269347 (Ruby)
%o A269347 def a(n)
%o A269347   seq = [1]
%o A269347   (2..Float::INFINITY).each do |i|
%o A269347     return seq.last[0...n].last if seq.length > n
%o A269347     indices = seq.each_index.select { |j| i % seq[j] == 0 }
%o A269347     seq << indices.map(&:next).reduce(:+)
%o A269347   end
%o A269347 end # _Peter Kagey_, Feb 25 2016
%o A269347 (Haskell)
%o A269347 a269347 1 = 1
%o A269347 a269347 n = genericIndex a269347_list (n - 1)
%o A269347 a269347_list = map a [1..] where
%o A269347   a n = sum $ filter ((==) 0 . mod n . a269347) [1..n-1]
%o A269347 -- _Peter Kagey_, Jun 17 2016
%o A269347 (Python)
%o A269347 from itertools import count, islice
%o A269347 from sympy import divisors
%o A269347 def A269347_gen(): # generator of terms
%o A269347     A268347_dict = {1:1}
%o A269347     yield 1
%o A269347     for n in count(2):
%o A269347         yield (s:=sum(A268347_dict.get(d,0) for d in divisors(n,generator=True)))
%o A269347         A268347_dict[s] = A268347_dict.get(s,0) + n
%o A269347 A269347_list = list(islice(A269347_gen(),40)) # _Chai Wah Wu_, Nov 17 2022
%Y A269347 Cf. A088167 which gives the number of m < n for which a(m) divides n.
%Y A269347 Cf. A271326, A271328.
%K A269347 easy,nonn,nice
%O A269347 1,3
%A A269347 _Alec Jones_, Feb 24 2016