A332904 Sum of distinct integers encountered on all possible paths from n to 1 when iterating with nondeterministic map k -> k - k/p, where p is any of the prime factors of k.

1, 3, 6, 7, 12, 16, 23, 15, 25, 30, 41, 36, 49, 57, 66, 31, 48, 63, 82, 66, 105, 99, 122, 76, 91, 115, 90, 125, 154, 156, 187, 63, 222, 114, 240, 139, 176, 196, 217, 138, 179, 251, 294, 215, 264, 284, 331, 156, 300, 213, 258, 247, 300, 220, 345, 261, 334, 348, 407, 336, 397, 429, 395, 127, 492, 512, 579, 246, 650, 546, 617, 291, 364

Offset

1,2

Links

Antti Karttunen, Table of n, a(n) for n = 1..20000

Formula

For all primes p, a(p) = a(p-1) + p.

For all n >= 1, A333000(n) >= a(n) >= A333794(n) >= A333790(n).

Example

a(12): we have three alternative paths: {12, 8, 4, 2, 1}, {12, 6, 4, 2, 1} or {12, 6, 3, 2, 1}, with numbers [1, 2, 3, 4, 6, 8, 12] present, therefore a(12) = 1+2+3+4+6+8+12 = 36.
For n=15 we have five alternative paths from 15 to 1: {15, 10, 5, 4, 2, 1}, {15, 10, 8, 4, 2, 1}, {15, 12, 8, 4, 2, 1},  {15, 12, 6, 4, 2, 1},  {15, 12, 6, 3, 2, 1}. These form a lattice illustrated below:
        15
       / \
      /   \
    10     12
    / \   / \
   /   \ /   \
  5     8     6
   \__  |  __/|
      \_|_/   |
        4     3
         \   /
          \ /
           2
           |
           1,
therefore a(15) = 1+2+3+4+5+6+8+10+12+15 = 66.

Mathematica

Total /@ Nest[Function[{a, n}, Append[a, Union@ Flatten@ Table[Append[a[[n - n/p]], n], {p, FactorInteger[n][[All, 1]]}]]] @@ {#, Length@ # + 1} &, {{1}}, 72] (* Michael De Vlieger, Apr 15 2020 *)

Prog

(PARI)
up_to = 20000;
A332904list(up_to) = { my(v=vector(up_to)); v[1] = Set([1]); for(n=2, up_to, my(f=factor(n)[, 1]~, s=Set([n])); for(i=1, #f, s = setunion(s, v[n-(n/f[i])])); v[n] = s); apply(vecsum, v); }
v332904 = A332904list(up_to);
A332904(n) = v332904[n];

Crossrefs

Cf. A064097, A073934, A332809, A332993, A332994, A333000, A333123.

Cf. A333790 (sum of the route with minimal sum), A333794.

Sequence in context: A047705 A309839 A169799 * A370900 A069891 A190118

Adjacent sequences: A332901 A332902 A332903 * A332905 A332906 A332907

Keyword

nonn

Author

Antti Karttunen, Apr 04 2020

Status

approved