%I #79 Dec 01 2023 03:12:42
%S 0,0,1,0,2,1,1,0,2,2,2,1,2,1,3,0,3,2,3,2,2,2,2,1,4,2,3,1,4,3,1,0,3,3,
%T 3,2,4,3,3,2,3,2,3,2,4,2,2,1,2,4,4,2,4,3,4,1,4,4,4,3,2,1,3,0,4,3,4,3,
%U 3,3,3,2,5,4,5,3,3,3,3,2,4,3,3,2,5,3,5,2,5,4,3,2,2,2,5,1,3,2,4,4,5,4,3,2,4
%N a(n) is the number of iterations needed to reach a power of 2 starting at n and using the map k -> k + k/p, where p is the largest prime factor of k.
%C Let f(n) = A000265(n) be the odd part of n. Let p be the largest prime factor of k, and say k = p * m. Suppose that k is not a power of 2, i.e., p > 2, then f(k) = p * f(m). The iteration is k -> k + k/p = p*m + m = (p+1) * m. So, p * f(m) -> f(p+1) * f(m). Since for p > 2, f(p+1) < p, the odd part in each iteration decreases, until it becomes 1, i.e., until we reach a power of 2. - _Amiram Eldar_, Feb 19 2020
%C Any odd prime factor of k can be used at any step of the iteration, and the result will be same. Thus, like A329697, this is also fully additive sequence. - _Antti Karttunen_, Apr 29 2020
%C If and only if a(n) is equal to A005087(n), then sigma(2n) - sigma(n) is a power of 2. (See A336923, A046528). - _Antti Karttunen_, Mar 16 2021
%H Antti Karttunen, <a href="/A331410/b331410.txt">Table of n, a(n) for n = 1..65537</a>
%H Michael De Vlieger, <a href="/A331410/a331410.png">Annotated fan style binary tree of a(n)</a> labeling the index n and applying a color code where black represents a(n) = 0, red a(n) = 1, and magenta the largest value of a(n) for n = 1..16383.
%F From _Antti Karttunen_, Apr 29 2020: (Start)
%F This is a completely additive sequence: a(2) = 0, a(p) = 1+a(p+1) for odd primes p, a(m*n) = a(m)+a(n), if m,n > 1.
%F a(2n) = a(A000265(n)) = a(n).
%F If A209229(n) == 1, a(n) = 0, otherwise a(n) = 1 + a(n+A052126(n)), or equally, 1 + a(n+(n/A078701(n))).
%F a(n) = A334097(n) - A334098(n).
%F a(A122111(n)) = A334108(n).
%F (End)
%F a(n) = A334861(n) - A329697(n). - _Antti Karttunen_, May 14 2020
%F a(n) = a(A336467(n)) + A087436(n) = A336921(n) + A087436(n). - _Antti Karttunen_, Mar 16 2021
%e The trajectory of 15 is [15,18,24,32], taking 3 iterations to reach 32. So, a(15) = 3.
%t a[n_] := -1 + Length @ NestWhileList[# + #/FactorInteger[#][[-1, 1]] &, n, # / 2^IntegerExponent[#, 2] != 1 &]; Array[a, 100] (* _Amiram Eldar_, Jan 16 2020 *)
%o (Magma) f:=func<n|n+n div p where p is Max(PrimeDivisors(n))>; g:=func<n| n eq 1 or Max(PrimeDivisors(n)) eq 2>; a:=[]; for n in [1..1000] do k:=n; s:=0; while not g(k) do s:=s+1; k:=f(k); end while; Append(~a,s); end for; a; // _Marius A. Burtea_, Jan 19 2020
%o (PARI) A331410(n) = if(!bitand(n,n-1),0,1+A331410(n+(n/vecmax(factor(n)[, 1])))); \\ _Antti Karttunen_, Apr 29 2020
%o (PARI) A331410(n) = { my(k=0); while(bitand(n,n-1), k++; my(f=factor(n)[, 1]); n += (n/f[2-(n%2)])); (k); }; \\ _Antti Karttunen_, Apr 29 2020
%o (PARI) A331410(n) = { my(f=factor(n)); sum(k=1,#f~,if(2==f[k,1],0,f[k,2]*(1+A331410(1+f[k,1])))); }; \\ _Antti Karttunen_, Apr 30 2020
%Y Cf. A000265, A005087, A006530 (greatest prime factor), A052126, A078701, A087436, A329662 (positions of records and the first occurrences of each n), A334097, A334098, A334108, A334861, A336467, A336921, A336922, A336923 (A046528).
%Y Cf. array A335430, and its rows A335431, A335882, and also A335874.
%Y Cf. also A329697 (analogous sequence when using the map k -> k - k/p), A335878.
%Y Cf. also A330437, A335884, A335885, A336362, A336363 for other similar iterations.
%K nonn
%O 1,5
%A _Ali Sada_, Jan 16 2020
%E Data section extended up to a(105) by _Antti Karttunen_, Apr 29 2020