A333000 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

LINKS

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

FORMULA

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

For all n, a(n) >= A332904(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}, 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.

/ \

10 12

/ \ / \

5 8 6

\__ | __/|

\_|_/ |

4 3

\ /

PROG

(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];

CROSSREFS

Cf. A332904, A333001, A333123.

Sequence in context: A249714 A250177 A333002 * A175048 A294231 A280873

Adjacent sequences: A332997 A332998 A332999 * A333001 A333002 A333003

KEYWORD

nonn

AUTHOR

Antti Karttunen, Apr 06 2020

STATUS

approved