login
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

%I #30 Aug 13 2022 09:38:01

%S 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,

%T 14,15,6,17,8,18,12,13,14,15,10,11,17,18,13,18,15,16,11,18,12,14,14,

%U 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

%N 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.

%C The count includes also n itself, and the final 1 when it is distinct from n.

%C a(n) >= A000005(n) because all divisors of n can be found in the union of those paths. - _Antti Karttunen_, Apr 19 2020

%H Antti Karttunen, <a href="/A332809/b332809.txt">Table of n, a(n) for n = 1..20000</a>

%F a(p) = 1 + a(p-1) for all primes p.

%F a(n) = n - A332810(n).

%F a(n) = A334112(n) + A000005(n). - _Antti Karttunen_, May 09 2020

%e a(1): {1}, therefore a(1) = 1;

%e 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;

%e 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;

%e 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.

%t 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 *)

%o (PARI)

%o up_to = 105;

%o 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); }

%o v332809 = A332809list(up_to);

%o A332809(n) = v332809[n];

%o (Python)

%o from sympy import factorint

%o from functools import cache

%o @cache

%o def b(n): return {n}.union(*(b(n - n//p) for p in factorint(n)))

%o def a(n): return len(b(n))

%o print([a(n) for n in range(1, 89)]) # _Michael S. Branicky_, Aug 13 2022

%Y Cf. A064097, A332810, A333123, A334230, A334231, A333786 (first occurrence of each n), A334112.

%Y Partial sums of A332902.

%Y See A332904 for the sum.

%K nonn,look

%O 1,2

%A _Antti Karttunen_, Apr 04 2020