|
|
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.
|
|
53
|
|
|
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, 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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,5
|
|
COMMENTS
|
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
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
|
|
LINKS
|
Michael De Vlieger, Annotated fan style binary tree of a(n) 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.
|
|
FORMULA
|
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.
(End)
|
|
EXAMPLE
|
The trajectory of 15 is [15,18,24,32], taking 3 iterations to reach 32. So, a(15) = 3.
|
|
MATHEMATICA
|
a[n_] := -1 + Length @ NestWhileList[# + #/FactorInteger[#][[-1, 1]] &, n, # / 2^IntegerExponent[#, 2] != 1 &]; Array[a, 100] (* Amiram Eldar, Jan 16 2020 *)
|
|
PROG
|
(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
(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
|
|
CROSSREFS
|
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).
Cf. also A329697 (analogous sequence when using the map k -> k - k/p), A335878.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|