cp's OEIS Frontend

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.

%I A335905 #16 Jul 22 2020 13:25:37
%S A335905 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,
%T A335905 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,
%U A335905 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
%N 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.
%H A335905 Antti Karttunen, <a href="/A335905/b335905.txt">Table of n, a(n) for n = 1..65537</a>
%e A335905 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:
%e A335905        9
%e A335905       / \
%e A335905      6   12
%e A335905     / \ / \
%e A335905   (4) (8) (16)
%e A335905 thus a(9) = 3.
%e A335905 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:
%e A335905   10
%e A335905    |\
%e A335905    | \
%e A335905    | 12
%e A335905    | /\
%e A335905    |/  \
%e A335905   (8)  (16)
%e A335905 thus a(10) = 2.
%e A335905 For n = 9, the numbers encountered are 6, 9, 12, thus a(9) = 3.
%e A335905 For n = 67, the numbers encountered are 48, 60, 66, 67, 68, 72, 96, thus a(67) = 7.
%e A335905 For n = 105, the numbers encountered are 48, 72, 90, 96, 105, 108, 120, 144, 192, thus a(105) = 9.
%o A335905 (PARI)
%o A335905 A171462(n) = if(1==n,0,(n-(n/vecmax(factor(n)[, 1]))));
%o A335905 A335876(n) = if(1==n,2,(n+(n/vecmax(factor(n)[, 1]))));
%o A335905 A209229(n) = (n && !bitand(n,n-1));
%o A335905 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));
%Y A335905 Cf. A006530, A171462, A335876, A335906.
%Y A335905 Cf. also A332809, A335884, A335885, A335904.
%K A335905 nonn
%O A335905 1,5
%A A335905 _Antti Karttunen_, Jun 30 2020