

A332809


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


13



1, 2, 3, 3, 4, 5, 6, 4, 6, 6, 7, 7, 8, 9, 10, 5, 6, 9, 10, 8, 12, 10, 11, 9, 9, 11, 10, 12, 13, 14, 15, 6, 17, 8, 18, 12, 13, 14, 15, 10, 11, 17, 18, 13, 18, 15, 16, 11, 18, 12, 14, 14, 15, 14, 16, 15, 17, 17, 18, 18, 19, 20, 20, 7, 22, 23, 24, 10, 26, 24, 25, 15, 16, 17, 21, 18, 30, 20, 21, 12, 15, 14, 15, 22, 16, 24, 25, 16
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

The count includes also n itself, and the final 1 when it is distinct from n.
a(n) >= A000005(n) because all divisors of n can be found in the union of those paths.  Antti Karttunen, Apr 19 2020


LINKS



FORMULA

a(p) = 1 + a(p1) for all primes p.


EXAMPLE

a(1): {1}, therefore a(1) = 1;
a(6): we have two alternative paths: {6, 4, 2, 1} or {6, 3, 2, 1}, with numbers [1, 2, 3, 4, 6] present, therefore a(6) = 5;
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) = 7;
a(14): we have five alternative paths: {14, 12, 8, 4, 2, 1}, {14, 12, 6, 4, 2, 1}, {14, 12, 6, 3, 2, 1}, {14, 7, 6, 4, 2, 1} or {14, 7, 6, 3, 2, 1}, with numbers [1, 2, 3, 4, 6, 7, 8, 12, 14] present in at least one of the paths, therefore a(14) = 9.


MATHEMATICA

a[n_] := Block[{lst = {{n}}}, While[lst[[1]] != {1}, lst = Join[ lst, {Union[ Flatten[#  #/(First@# & /@ FactorInteger@#) & /@ lst[[1]]]]}]]; Length@ Union@ Flatten@ lst]; Array[a, 75] (* Robert G. Wilson v, Apr 06 2020 *)


PROG

(PARI)
up_to = 105;
A332809list(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(length, v); }
v332809 = A332809list(up_to);
(Python)
from sympy import factorint
from functools import cache
@cache
def b(n): return {n}.union(*(b(n  n//p) for p in factorint(n)))
def a(n): return len(b(n))


CROSSREFS



KEYWORD



AUTHOR



STATUS

approved



