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.

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

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