A335906 Number of distinct integers encountered on all possible paths from n to any first encountered powers of 2 (that are included in 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.

1, 1, 3, 1, 4, 3, 4, 1, 6, 4, 5, 3, 5, 4, 7, 1, 7, 6, 8, 4, 7, 5, 6, 3, 9, 5, 10, 4, 9, 7, 8, 1, 8, 7, 9, 6, 9, 8, 8, 4, 9, 7, 10, 5, 11, 6, 7, 3, 9, 9, 11, 5, 13, 10, 10, 4, 12, 9, 10, 7, 9, 8, 11, 1, 10, 8, 10, 7, 9, 9, 10, 6, 10, 9, 13, 8, 11, 8, 10, 4, 15, 9, 10, 7, 13, 10, 13, 5, 14, 11, 10, 6, 12, 7, 15, 3, 10, 9, 12, 9, 15, 11, 14, 5, 13

Offset

1,3

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 six numbers, when one doesn't expand any power of 2 further:
       9
      / \
     6   12
    / \ / \
   4   8   16
thus a(9) = 6.
From 10 one can reach with the transitions x -> A171462(x) and x -> A335876(x) the following for numbers, when one doesn't expand any power of 2 further:
  10
   |\
   | \
   | 12
   | /\
   |/  \
   8   16
thus a(10) = 4.
From 15 one can reach with the transitions x -> A171462(x) and x -> A335876(x) the following seven numbers, when one doesn't expand any power of 2 further:
        15
       /  \
      /    \
    12<----18
    / \      \
   /   \      \
  8     16<----24
                \
                 \
                  32
thus a(15) = 7.

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));
A335906(n) = { 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]; if(!A209229(u), newxs = setunion([A171462(u)], newxs); newxs = setunion([A335876(u)], newxs))); xs = newxs); };

Crossrefs

Cf. A006530, A171462, A335876, A335905.

Sequence in context: A209704 A339106 A082909 * A029151 A102595 A113415

Adjacent sequences: A335903 A335904 A335905 * A335907 A335908 A335909

Keyword

nonn

Author

Antti Karttunen, Jun 30 2020

Status

approved