cp's OEIS Frontend

A331410 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.

%I A331410 #79 Dec 01 2023 03:12:42
%S A331410 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 A331410 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 A331410 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 A331410 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 A331410 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 A331410 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 A331410 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 A331410 Antti Karttunen, <a href="/A331410/b331410.txt">Table of n, a(n) for n = 1..65537</a>
%H A331410 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 A331410 From _Antti Karttunen_, Apr 29 2020: (Start)
%F A331410 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 A331410 a(2n) = a(A000265(n)) = a(n).
%F A331410 If A209229(n) == 1, a(n) = 0, otherwise a(n) = 1 + a(n+A052126(n)), or equally, 1 + a(n+(n/A078701(n))).
%F A331410 a(n) = A334097(n) - A334098(n).
%F A331410 a(A122111(n)) = A334108(n).
%F A331410 (End)
%F A331410 a(n) = A334861(n) - A329697(n). - _Antti Karttunen_, May 14 2020
%F A331410 a(n) = a(A336467(n)) + A087436(n) = A336921(n) + A087436(n). - _Antti Karttunen_, Mar 16 2021
%e A331410 The trajectory of 15 is [15,18,24,32], taking 3 iterations to reach 32. So, a(15) = 3.
%t A331410 a[n_] := -1 + Length @ NestWhileList[# + #/FactorInteger[#][[-1, 1]] &, n, # / 2^IntegerExponent[#, 2] != 1 &]; Array[a, 100] (* _Amiram Eldar_, Jan 16 2020 *)
%o A331410 (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 A331410 (PARI) A331410(n) = if(!bitand(n,n-1),0,1+A331410(n+(n/vecmax(factor(n)[, 1])))); \\ _Antti Karttunen_, Apr 29 2020
%o A331410 (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 A331410 (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 A331410 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 A331410 Cf. array A335430, and its rows A335431, A335882, and also A335874.
%Y A331410 Cf. also A329697 (analogous sequence when using the map k -> k - k/p), A335878.
%Y A331410 Cf. also A330437, A335884, A335885, A336362, A336363 for other similar iterations.
%K A331410 nonn
%O A331410 1,5
%A A331410 _Ali Sada_, Jan 16 2020
%E A331410 Data section extended up to a(105) by _Antti Karttunen_, Apr 29 2020