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

 

Logo
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
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
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.

License Agreements, Terms of Use, Privacy Policy. .

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