cp's OEIS Frontend

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.

%I A332809 #30 Aug 13 2022 09:38:01
%S A332809 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 A332809 14,15,6,17,8,18,12,13,14,15,10,11,17,18,13,18,15,16,11,18,12,14,14,
%U A332809 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 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.
%C A332809 The count includes also n itself, and the final 1 when it is distinct from n.
%C A332809 a(n) >= A000005(n) because all divisors of n can be found in the union of those paths. - _Antti Karttunen_, Apr 19 2020
%H A332809 Antti Karttunen, <a href="/A332809/b332809.txt">Table of n, a(n) for n = 1..20000</a>
%F A332809 a(p) = 1 + a(p-1) for all primes p.
%F A332809 a(n) = n - A332810(n).
%F A332809 a(n) = A334112(n) + A000005(n). - _Antti Karttunen_, May 09 2020
%e A332809 a(1): {1}, therefore a(1) = 1;
%e A332809 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 A332809 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 A332809 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 A332809 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 A332809 (PARI)
%o A332809 up_to = 105;
%o A332809 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 A332809 v332809 = A332809list(up_to);
%o A332809 A332809(n) = v332809[n];
%o A332809 (Python)
%o A332809 from sympy import factorint
%o A332809 from functools import cache
%o A332809 @cache
%o A332809 def b(n): return {n}.union(*(b(n - n//p) for p in factorint(n)))
%o A332809 def a(n): return len(b(n))
%o A332809 print([a(n) for n in range(1, 89)]) # _Michael S. Branicky_, Aug 13 2022
%Y A332809 Cf. A064097, A332810, A333123, A334230, A334231, A333786 (first occurrence of each n), A334112.
%Y A332809 Partial sums of A332902.
%Y A332809 See A332904 for the sum.
%K A332809 nonn,look
%O A332809 1,2
%A A332809 _Antti Karttunen_, Apr 04 2020