# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a329697
Showing 1-1 of 1

%I A329697 #98 Aug 06 2022 07:26:54
%S A329697 0,0,1,0,1,1,2,0,2,1,2,1,2,2,2,0,1,2,3,1,3,2,3,1,2,2,3,2,3,2,3,0,3,1,
%T A329697 3,2,3,3,3,1,2,3,4,2,3,3,4,1,4,2,2,2,3,3,3,2,4,3,4,2,3,3,4,0,3,3,4,1,
%U A329697 4,3,4,2,3,3,3,3,4,3,4,1,4,2,3,3,2,4,4,2,3,3,4,3,4,4,4,1,2,4,4,2
%N A329697 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 A329697 From _Antti Karttunen_, Apr 07 2020: (Start)
%C A329697 Also the least number of iterations of nondeterministic map k -> k-(k/p) needed to reach a power of 2, when any prime factor p of k can be used. The minimal length path to the nearest power of 2 (= 2^A064415(n)) is realized whenever one uses any of the A005087(k) distinct odd prime factors of the current k, at any step of the process. For example, this could be done by iterating with the map k -> k-(k/A078701(k)), i.e., by using the least odd prime factor of k (instead of the largest prime).
%C A329697 Proof: Viewing the prime factorization of changing k as a multiset ("bag") of primes, we see that liquefying any odd prime p with step p -> (p-1) brings at least one more 2 to the bag, while applying p -> (p-1) to any 2 just removes it from the bag, but gives nothing back. Thus the largest (and thus also the nearest) power of 2 is reached by eliminating - step by step - all odd primes from the bag, but none of 2's, and it doesn't matter in which order this is done.
%C A329697 The above implies also that the sequence is totally additive, which also follows because both A064097 and A064415 are. That A064097(n) = A329697(n) + A054725(n) for all n > 1 can be also seen by comparing the initial conditions and the recursion formulas of these three sequences.
%C A329697 For any n, A333787(n) is either the nearest power of 2 reached (= 2^A064415(n)), or occurs on some of the paths from n to there.
%C A329697 (End)
%C A329697 A003401 gives the numbers k where a(k) = A005087(k). See also A336477. - _Antti Karttunen_, Mar 16 2021
%H A329697 Antti Karttunen, <a href="/A329697/b329697.txt">Table of n, a(n) for n = 1..65537</a>
%H A329697 Michael De Vlieger, <a href="/A329697/a329697.png">Annotated fan style binary tree</a> labeling the index n, with a color code where black represents a(n) = 0, red a(n) = 1, and magenta the largest value in a(n) for n = 1..16383.
%F A329697 From _Antti Karttunen_, Apr 07-19 2020: (Start)
%F A329697 a(1) = a(2) = 0; and for n > 2, a(p) = 1 + a(p-1) if p is an odd prime and a(n*m) = a(n) + a(m) if m,n > 1. [This is otherwise equal to the definition of A064097, except here we have a different initial condition, with a(2) = 0].
%F A329697 a(2n) = a(A000265(n)) = a(n).
%F A329697 a(p) = 1+a(p-1), for all odd primes p.
%F A329697 If A209229(n) == 1 [when n is a power of 2], a(n) = 0,
%F A329697   otherwise a(n) = 1 + a(n-A052126(n)) = 1 + a(A171462(n)).
%F A329697 Equivalently, for non-powers of 2, a(n) = 1 + a(n-(n/A078701(n))),
%F A329697 or equivalently, for non-powers of 2, a(n) = 1 + Min a(n - n/p), for p prime and dividing n.
%F A329697 a(n) = A064097(n) - A064415(n), or equally, a(n) = A064097(n) - A054725(n), for n > 1.
%F A329697 a(A019434(n)) = 1, a(A334092(n)) = 2, a(A334093(n)) = 3, etc. for all applicable n.
%F A329697 For all n >= 0, a(A334099(n)) = a(A000244(n)) = a(A000351(n)) = a(A001026(n)) = a(257^n) = a(65537^n) = n.
%F A329697 a(A122111(n)) = A334107(n), a(A225546(n)) = A334109(n).
%F A329697 (End)
%F A329697 From _Antti Karttunen_, Mar 16 2021: (Start)
%F A329697 a(n) = a(A336466(n)) + A087436(n) = A336396(n) + A087436(n).
%F A329697 a(A053575(n)) = A336469(n) = a(n) - A005087(n).
%F A329697 a(A147545(n)) = A000120(A147545(n)) - 1.
%F A329697 (End)
%e A329697 The trajectory of 15 is {12, 8}, taking 2 iterations to reach 8 = 2^3. So a(15) is 2.
%e A329697 From _Antti Karttunen_, Apr 07 2020: (Start)
%e A329697 Considering all possible paths from 15 to 1 nondeterministic map k -> k-(k/p), where p can be any prime factor of k, we obtain the following graph:
%e A329697         15
%e A329697        / \
%e A329697       /   \
%e A329697     10     12
%e A329697     / \   / \
%e A329697    /   \ /   \
%e A329697   5     8     6
%e A329697    \__  |  __/|
%e A329697       \_|_/   |
%e A329697         4     3
%e A329697          \   /
%e A329697           \ /
%e A329697            2
%e A329697            |
%e A329697            1.
%e A329697 It can be seen that there's also alternative route to 8 via 10 (with 10 = 15-(15/3), where 3 is not the largest prime factor of 15), but it's not any shorter than the route via 12.
%e A329697 (End)
%t A329697 a[n_] := Length@ NestWhileList[# - #/FactorInteger[#][[-1, 1]] &, n, # != 2^IntegerExponent[#, 2] &] -1; Array[a, 100]
%o A329697 (PARI) A329697(n) = if(!bitand(n,n-1),0,1+A329697(n-(n/vecmax(factor(n)[, 1])))); \\ _Antti Karttunen_, Apr 07 2020
%o A329697 (PARI)
%o A329697 up_to = 2^24;
%o A329697 A329697list(up_to) = { my(v=vector(up_to)); v[1] = 0; for(n=2, up_to, v[n] = if(!bitand(n,n-1),0,1+vecmin(apply(p -> v[n-n/p], factor(n)[, 1]~)))); (v); };
%o A329697 v329697 = A329697list(up_to);
%o A329697 A329697(n) = v329697[n]; \\ _Antti Karttunen_, Apr 07 2020
%o A329697 (PARI) A329697(n) = if(n<=2,0, if(isprime(n), A329697(n-1)+1, my(f=factor(n)); (apply(A329697, f[, 1])~ * f[, 2]))); \\ _Antti Karttunen_, Apr 19 2020
%Y A329697 Cf. A000265, A003401, A005087, A052126, A053575, A054725, A064097, A064415, A078701, A087436, A147545, A171462, A209229, A333123, A333787, A333790, A334107, A334109, A335875, A334204, A335880, A335881, A336396, A336466, A336469 [= a(phi(n))], A336928 [= a(sigma(n))], A336470, A336477, A339970.
%Y A329697 Cf. A000079, A334101, A334102, A334103, A334104, A334105, A334106 for positions of 0 .. 6 in this sequence, and also array A334100.
%Y A329697 Cf. A334099 (a right inverse, positions of the first occurrence of each n).
%Y A329697 Cf. A334091 (first differences), A335429 (partial sums).
%Y A329697 Cf. also A331410 (analogous sequence when using the map k -> k + k/p), A334861, A335877 (their sums and differences), see also A335878 and A335884, A335885.
%K A329697 easy,nonn
%O A329697 1,7
%A A329697 _Ali Sada_ and _Robert G. Wilson v_, Feb 28 2020

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE