A385522 Sum of factors chain length.

1, 5, 4, 3, 2, 1, 2, 2, 3, 3, 4, 3, 5, 4, 4, 4, 5, 4, 5, 4, 5, 5, 5, 4, 5, 5, 4, 4, 6, 5, 6, 5, 5, 5, 6, 5, 7, 6, 6, 4, 7, 6, 6, 5, 4, 6, 5, 4, 5, 6, 6, 5, 5, 4, 6, 5, 6, 6, 7, 6, 7, 6, 5, 6, 6, 6, 7, 6, 5, 5, 7, 6, 6, 5, 5, 5, 6, 6, 6, 5, 6, 6, 6, 5, 6, 7, 6, 5, 6, 5, 6, 5, 7, 7, 6

Offset

1,2

Comments

We generate a chain via the following method:

Start with a number N. Compute the noncomposite factors of N and sum them together to get N'. Iterate this procedure until you reach a number you've already seen, at which point terminate.

The largest value of the sequence under 1,000,000 is N = 931844, which evaluates to 16.

Question: How quickly does this function grow relative to N?

Links

Table of n, a(n) for n=1..95.

Example

1 : [[1]] -> 1
2 : [[1, 2], [1, 3], [1, 2, 2], [1, 5], [1, 2, 3]] -> 5
3 : [[1, 3], [1, 2, 2], [1, 5], [1, 2, 3]] -> 4
4 : [[1, 2, 2], [1, 5], [1, 2, 3]] -> 3
5 : [[1, 5], [1, 2, 3]] -> 2
6 : [[1, 2, 3]] -> 1
7 : [[1, 7], [1, 2, 2, 2]] -> 2
8 : [[1, 2, 2, 2], [1, 7]] -> 2
9 : [[1, 3, 3], [1, 7], [1, 2, 2, 2]] -> 3

Prog

(Python)
def prime_factors(n):
  i = 2
  factors = [1]
  while i * i <= n:
    if n % i:
      i += 1
    else:
      n //= i
      factors.append(i)
  if n > 1:
    factors.append(n)
  return factors
def sum_of_factors_chain(N):
  ctr, cur = 0, N
  seen = set()
  while cur not in seen:
    factors = prime_factors(cur)
    seen.add(cur)
    cur = sum(factors)
    ctr += 1
  return ctr

Crossrefs

Cf. A008578.

Sequence in context: A031016 A261302 A284803 * A071691 A319332 A031017

Adjacent sequences: A385519 A385520 A385521 * A385523 A385524 A385525

Keyword

nonn

Author

Philip Weiss, Jul 01 2025

Status

approved