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

Author

Antti Karttunen, Jun 30 2020

Keywords

• nonn

Examples

			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.
		

Links

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

Crossrefs

Cf. A006530, A171462, A335876, A335905.

Programs

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); };