A333000 Sum of integers (with multiplicity) encountered on all possible paths from n to 1 when iterating with nondeterministic map k -> k- k/p, where p is any prime factor of k.

1, 3, 6, 7, 12, 25, 39, 15, 43, 47, 69, 76, 115, 185, 198, 31, 48, 209, 304, 138, 604, 317, 432, 203, 213, 500, 344, 640, 901, 899, 1271, 63, 1777, 179, 2274, 736, 1069, 1572, 1860, 361, 525, 3156, 4360, 1074, 2580, 2150, 2808, 506, 4528, 924, 1042, 1630, 2266, 1836, 2878, 1930, 5004, 4165, 5522, 3026, 4307, 6343, 7638, 127, 6801

Offset: 1

Author

Antti Karttunen, Apr 06 2020

Keywords

• nonn

Examples

			a(12): we have three alternative paths: {12, 8, 4, 2, 1}, {12, 6, 4, 2, 1} or {12, 6, 3, 2, 1}, therefore a(12) = (12+8+4+2+1) + (12+6+4+2+1) + (12+6+3+2+1) = 27+25+24 = 76
For n=15 we have five alternative paths from 15 to 1 (illustrated below): therefore a(15) = (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) = 37+40+42+40+39 = 198.
        15
       / \
      /   \
    10     12
    / \   / \
   /   \ /   \
  5     8     6
   \__  |  __/|
      \_|_/   |
        4     3
         \   /
          \ /
           2
           |
           1.
		

Links

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

Crossrefs

Cf. A332904, A333001, A333123.

Programs

PARI

up_to = 20000;
A333000list(up_to) = { my(u=vector(up_to), v=vector(up_to)); u[1] = v[1] = 1; for(n=2,up_to, u[n] = vecsum(apply(p -> u[n-n/p], factor(n)[, 1]~)); v[n] = (u[n]*n)+vecsum(apply(p -> v[n-n/p], factor(n)[, 1]~))); (v); };
v333000 = A333000list(up_to);
A333000(n) = v333000[n];

Formula

a(n) = n*A333123(n) + Sum_{p prime and dividing n} a(n - n/p).

For all n, a(n) >= A332904(n).