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

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, 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, 975, 3, 3, 1086, 3, 3, 1218, 3, 3, 1326, 3, 3, 1455

Offset: 1

Author

Alec Jones, Feb 24 2016

Keywords

• easy
• nonn
• nice

Comments

For n > 2, I can prove that a(n) = 3 if 3 does not divide n, and in general, 3 divides a(n).

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.

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.

Examples

			a(1) = 1;
a(2) = 1 because a(1) divides 2;
a(3) = 3 because a(1) and a(2) divide 3: 1+2=3;
a(4) = 3 because a(1) and a(2) divide 4: 1+2=3;
a(5) = 3 because a(1) and a(2) divide 5: 1+2=3;
a(6) = 15 because a(1), a(2), a(3), a(4), and a(5) divide 6: 1+2+3+4+5=15.
		

Links

• Chai Wah Wu, Table of n, a(n) for n = 1..10000 (n = 1..1000 from Alec Jones)

Crossrefs

Cf. A088167 which gives the number of m < n for which a(m) divides n.

Cf. A271326, A271328.

Programs

Haskell

a269347 1 = 1
a269347 n = genericIndex a269347_list (n - 1)
a269347_list = map a [1..] where
  a n = sum $ filter ((==) 0 . mod n . a269347) [1..n-1]
-- Peter Kagey, Jun 17 2016

Java

int[] terms = new int[1000];
terms[0] = 1;
for (int i = 1; i < 1000; i++) {
     int count = 0;
     for (int j = 0; j < i; j++) {
          if ((i + 1) % terms[j] == 0) {
               count = count + (j + 1);
          }
     }
     terms[i] = count;
}

Mathematica

a = {1}; Do[AppendTo[a, Total@ Select[Range[n - 1], Divisible[n, a[[#]]] &]], {n, 2, 66}]; a (* Michael De Vlieger, Mar 24 2016 *)

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

Python

from itertools import count, islice
from sympy import divisors
def A269347_gen(): # generator of terms
    A268347_dict = {1:1}
    yield 1
    for n in count(2):
        yield (s:=sum(A268347_dict.get(d,0) for d in divisors(n,generator=True)))
        A268347_dict[s] = A268347_dict.get(s,0) + n
A269347_list = list(islice(A269347_gen(),40)) # Chai Wah Wu, Nov 17 2022

Ruby

def a(n)
  seq = [1]
  (2..Float::INFINITY).each do |i|
    return seq.last[0...n].last if seq.length > n
    indices = seq.each_index.select { |j| i % seq[j] == 0 }
    seq << indices.map(&:next).reduce(:+)
  end
end # Peter Kagey, Feb 25 2016