A335905 Number of distinct integers encountered on all possible paths from n to any first encountered powers of 2 (that are excluded from the count), when using the transitions x -> x - (x/p) and x -> x + (x/p) in any order, where p is the largest prime dividing x.

0, 0, 1, 0, 2, 1, 2, 0, 3, 2, 3, 1, 3, 2, 4, 0, 4, 3, 5, 2, 4, 3, 4, 1, 6, 3, 6, 2, 6, 4, 5, 0, 5, 4, 6, 3, 6, 5, 5, 2, 6, 4, 7, 3, 7, 4, 5, 1, 6, 6, 7, 3, 9, 6, 7, 2, 8, 6, 7, 4, 6, 5, 7, 0, 7, 5, 7, 4, 6, 6, 7, 3, 7, 6, 9, 5, 8, 5, 7, 2, 10, 6, 7, 4, 9, 7, 9, 3, 10, 7, 7, 4, 8, 5, 11, 1, 7, 6, 8, 6, 11, 7, 10, 3, 9

Offset

1,5

Links

Antti Karttunen, Table of n, a(n) for n = 1..65537

Example

From 9 one can reach with the transitions x -> A171462(x) (leftward arrow) and x -> A335876(x) (rightward arrow) the following three numbers, when one doesn't expand any power of 2 (in this case, 4, 8 and 16, that are not included in the count) further:
       9
      / \
     6   12
    / \ / \
  (4) (8) (16)
thus a(9) = 3.
From 10 one can reach with the transitions x -> A171462(x) and x -> A335876(x) the following two numbers (10 & 12), when one doesn't expand any powers of 2 (8 and 16 in this case, not counted) further:
  10
   |\
   | \
   | 12
   | /\
   |/  \
  (8)  (16)
thus a(10) = 2.
For n = 9, the numbers encountered are 6, 9, 12, thus a(9) = 3.
For n = 67, the numbers encountered are 48, 60, 66, 67, 68, 72, 96, thus a(67) = 7.
For n = 105, the numbers encountered are 48, 72, 90, 96, 105, 108, 120, 144, 192, thus a(105) = 9.

Prog

(PARI)
A171462(n) = if(1==n, 0, (n-(n/vecmax(factor(n)[, 1]))));
A335876(n) = if(1==n, 2, (n+(n/vecmax(factor(n)[, 1]))));
A209229(n) = (n && !bitand(n, n-1));
A335905(n) = if(A209229(n), 0, my(xs=Set([n]), allxs=xs, newxs, a, b, u); for(k=1, oo, newxs=Set([]); if(!#xs, return(#allxs)); allxs = setunion(allxs, xs); for(i=1, #xs, u = xs[i]; a = A171462(u); if(!A209229(a), newxs = setunion([a], newxs)); b = A335876(u); if(!A209229(b), newxs = setunion([b], newxs))); xs = newxs));

Crossrefs

Cf. A006530, A171462, A335876, A335906.

Cf. also A332809, A335884, A335885, A335904.

Sequence in context: A275019 A337835 A119387 * A055941 A347696 A365385

Adjacent sequences: A335902 A335903 A335904 * A335906 A335907 A335908

Keyword

nonn

Author

Antti Karttunen, Jun 30 2020

Status

approved