The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 Antti Karttunen, Table of n, a(n) for n = 1..20000 FORMULA a(p) = 1 + a(p-1) for all primes p. a(n) = n - A332810(n). a(n) = A334112(n) + A000005(n). - Antti Karttunen, May 09 2020 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); A332809(n) = v332809[n]; (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)) print([a(n) for n in range(1, 89)]) # Michael S. Branicky, Aug 13 2022 CROSSREFS Cf. A064097, A332810, A333123, A334230, A334231, A333786 (first occurrence of each n), A334112. Partial sums of A332902. See A332904 for the sum. Sequence in context: A350311 A331297 A322806 * A290801 A322815 A244041 Adjacent sequences: A332806 A332807 A332808 * A332810 A332811 A332812 KEYWORD nonn,look AUTHOR Antti Karttunen, Apr 04 2020 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified April 12 22:48 EDT 2024. Contains 371639 sequences. (Running on oeis4.)