A336396 -id:A336396 - cp's OEIS frontend

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.

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, 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, 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

Offset: 1

Ali Sada and Robert G. Wilson v, Feb 28 2020

From Antti Karttunen, Apr 07 2020: (Start)
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).
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.
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.
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.
(End)
A003401 gives the numbers k where a(k) = A005087(k). See also A336477. - Antti Karttunen, Mar 16 2021

			The trajectory of 15 is {12, 8}, taking 2 iterations to reach 8 = 2^3. So a(15) is 2.
From _Antti Karttunen_, Apr 07 2020: (Start)
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:
        15
       / \
      /   \
    10     12
    / \   / \
   /   \ /   \
  5     8     6
   \__  |  __/|
      \_|_/   |
        4     3
         \   /
          \ /
           2
           |
           1.
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.
(End)

Antti Karttunen, Table of n, a(n) for n = 1..65537
Michael De Vlieger, Annotated fan style binary tree 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.

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.
Cf. A000079, A334101, A334102, A334103, A334104, A334105, A334106 for positions of 0 .. 6 in this sequence, and also array A334100.
Cf. A334099 (a right inverse, positions of the first occurrence of each n).
Cf. A334091 (first differences), A335429 (partial sums).
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.

a[n_] := Length@ NestWhileList[# - #/FactorInteger[#][[-1, 1]] &, n, # != 2^IntegerExponent[#, 2] &] -1; Array[a, 100]

A329697(n) = if(!bitand(n,n-1),0,1+A329697(n-(n/vecmax(factor(n)[, 1])))); \\ Antti Karttunen, Apr 07 2020

up_to = 2^24;
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); };
v329697 = A329697list(up_to);
A329697(n) = v329697[n]; \\ Antti Karttunen, Apr 07 2020

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

From Antti Karttunen, Apr 07-19 2020: (Start)
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].
a(2n) = a(A000265(n)) = a(n).
a(p) = 1+a(p-1), for all odd primes p.
If A209229(n) == 1 [when n is a power of 2], a(n) = 0,
  otherwise a(n) = 1 + a(n-A052126(n)) = 1 + a(A171462(n)).
Equivalently, for non-powers of 2, a(n) = 1 + a(n-(n/A078701(n))),
or equivalently, for non-powers of 2, a(n) = 1 + Min a(n - n/p), for p prime and dividing n.
a(n) = A064097(n) - A064415(n), or equally, a(n) = A064097(n) - A054725(n), for n > 1.
a(A019434(n)) = 1, a(A334092(n)) = 2, a(A334093(n)) = 3, etc. for all applicable n.
For all n >= 0, a(A334099(n)) = a(A000244(n)) = a(A000351(n)) = a(A001026(n)) = a(257^n) = a(65537^n) = n.
a(A122111(n)) = A334107(n), a(A225546(n)) = A334109(n).
(End)
From Antti Karttunen, Mar 16 2021: (Start)
a(n) = a(A336466(n)) + A087436(n) = A336396(n) + A087436(n).
a(A053575(n)) = A336469(n) = a(n) - A005087(n).
a(A147545(n)) = A000120(A147545(n)) - 1.
(End)

A336466 Fully multiplicative with a(p) = A000265(p-1) for any prime p, where A000265(k) gives the odd part of k.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 5, 1, 3, 3, 1, 1, 1, 1, 9, 1, 3, 5, 11, 1, 1, 3, 1, 3, 7, 1, 15, 1, 5, 1, 3, 1, 9, 9, 3, 1, 5, 3, 21, 5, 1, 11, 23, 1, 9, 1, 1, 3, 13, 1, 5, 3, 9, 7, 29, 1, 15, 15, 3, 1, 3, 5, 33, 1, 11, 3, 35, 1, 9, 9, 1, 9, 15, 3, 39, 1, 1, 5, 41, 3, 1, 21, 7, 5, 11, 1, 9, 11, 15, 23, 9, 1, 3, 9, 5, 1, 25, 1, 51, 3, 3

Offset: 1

Antti Karttunen, Jul 22 2020

For the comment here, we extend the definition of the second kind of Cunningham chain (see Wikipedia-article) so that also isolated primes for which neither (p+1)/2 nor 2p-1 is a prime are considered to be in singular chains, that is, in chains of the length one. If we replace one or more instances of any particular odd prime factor p in n with any odd prime q in such a chain, so that m = (q^k)*n / p^(e-k), where e is the exponent of p of n, and k <= e is the number of instances of p replaced with q, then it holds that a(m) = a(n), and by induction, the value stays invariant for any number of such replacements. Note also that A001222, but not necessarily A001221 will stay invariant in such changes.
For example, if some of the odd prime divisors p of n are in A005382, then replacing it with 2p-1 (i.e., the corresponding terms of A005383), gives a new number m, for which a(m) = a(n). And vice versa, the same is true for any of the prime divisors > 3 of n that are in A005383, then replacing any one of them with (p+1)/2 will not affect the result. For example, a(37*37*37) = a(19*37*73) = 729 as 37 is both in A005382 and in A005383.
a(n) = A053575(n) for squarefree n (A005117). - Antti Karttunen, Mar 16 2021

Antti Karttunen, Table of n, a(n) for n = 1..16384
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537
Wikipedia, Cunningham chain

Cf. A000265, A003958, A005117, A005382, A005383, A053575, A329697, A333787, A335915, A336396, A336467, A336468, A339870, A339876 [= a(A122111(n))], A339903 [= a(A003961(n))], A340084 [= gcd(n-1, a(n))], A340085, A340086.

Cf. also A336460, A336470, A339974.

Array[Times @@ Map[If[# <= 2, 1, (# - 1)/2^IntegerExponent[# - 1, 2]] &, Flatten[ConstantArray[#1, #2] & @@@ FactorInteger[#]]] &, 105] (* Michael De Vlieger, Jul 24 2020 *)

A000265(n) = (n>>valuation(n,2));
A336466(n) = { my(f=factor(n)); prod(k=1,#f~,A000265(f[k,1]-1)^f[k,2]); };

a(n) = A000265(A003958(n)) = A000265(A333787(n)).
a(A000010(n)) = A336468(n) = a(A053575(n)).
A329697(a(n)) = A336396(n) = A329697(n) - A087436(n).
a(n) = A335915(n) / A336467(n). - Antti Karttunen, Mar 16 2021

A336469 a(n) = A329697(phi(n)), where A329697 is totally additive with a(2) = 0 and a(p) = 1 + a(p-1) for odd primes.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 0, 2, 0, 1, 0, 1, 1, 2, 2, 1, 0, 1, 1, 3, 1, 1, 2, 3, 0, 3, 1, 0, 1, 2, 2, 1, 1, 2, 2, 3, 0, 2, 2, 2, 0, 1, 1, 3, 0, 2, 1, 3, 1, 2, 2, 1, 2, 2, 1, 3, 0, 3, 1, 2, 1, 0, 3, 2, 1, 2, 1, 2, 2, 2, 3, 2, 0, 1, 3, 2, 1, 2, 0, 2, 1, 1

Offset: 1

Antti Karttunen, Jul 22 2020

nonn

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A000010, A000265, A003434, A005087, A046660, A064097, A064415, A329697, A336396, A336477.

Cf. A003401 (positions of zeros).

Array[Length@ NestWhileList[# - #/FactorInteger[#][[-1, 1]] &, EulerPhi[#], # != 2^IntegerExponent[#, 2] &] - 1 &, 105] (* Michael De Vlieger, Jul 24 2020 *)

A329697(n) = if(!bitand(n,n-1),0,1+A329697(n-(n/vecmax(factor(n)[, 1]))));
A336469(n) = A329697(eulerphi(n));
\\ Or alternatively as:
A336469(n) = { my(f = factor(n)); sum(k=1, #f~, if(2==f[k,1],0,-1 + (f[k, 2]*A329697(f[k, 1])))); };

Additive with a(2^e) = 0, and for odd primes p, a(p^e) = A329697((p - 1)*p^(e-1)) = e*A329697(p) - 1.

a(n) = A329697(n) - A005087(n) = A336396(n) + A046660(A000265(n)).

A336471 Lexicographically earliest infinite sequence such that a(i) = a(j) => A329697(i) = A329697(j) and A336158(i) = A336158(j), for all i, j >= 1.

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 3, 1, 4, 2, 3, 2, 3, 3, 5, 1, 2, 4, 6, 2, 7, 3, 6, 2, 4, 3, 8, 3, 6, 5, 6, 1, 7, 2, 7, 4, 6, 6, 7, 2, 3, 7, 9, 3, 10, 6, 9, 2, 11, 4, 5, 3, 6, 8, 7, 3, 12, 6, 9, 5, 6, 6, 13, 1, 7, 7, 9, 2, 12, 7, 9, 4, 6, 6, 10, 6, 12, 7, 9, 2, 14, 3, 6, 7, 5, 9, 12, 3, 6, 10, 12, 6, 12, 9, 12, 2, 3, 11, 13, 4, 6, 5, 6, 3, 15

Offset: 1

Antti Karttunen, Jul 22 2020

nonn

Restricted growth sequence transform of the ordered pair [A329697(n), A336158(n)].
For all i, j:
  A336470(i) = A336470(j) => a(i) = a(j)
  a(i) = a(j) => A336396(i) = A336396(j),
  a(i) = a(j) => A336469(i) = A336469(j) => A336477(i) = A336477(j).
This sequence has an ability to see where the terms of A003401 are, as they are the indices of zeros in A336469. Specifically, they are numbers k that satisfy the condition A329697(k) = A001221(A336158(k)), i.e., numbers for which A329697(k) is equal to the number of distinct prime divisors of the odd part of k. See also comments in array A334100.

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A000265, A003401, A046523, A329697, A334100, A336158.

Cf. also A003602, A324400, A336159, A336160, A336396, A336469, A336470, A336472, A336473, A336477.

up_to = 65537;
rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om,invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om,invec[i],i); outvec[i] = u; u++ )); outvec; };
A000265(n) = (n>>valuation(n,2));
A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); };  \\ From A046523
A336158(n) = A046523(A000265(n));
A329697(n) = if(!bitand(n,n-1),0,1+A329697(n-(n/vecmax(factor(n)[, 1]))));
Aux336471(n) = [A329697(n), A336158(n)];
v336471 = rgs_transform(vector(up_to, n, Aux336471(n)));
A336471(n) = v336471[n];

A336921 a(n) = A331410(n) - A087436(n).

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 2, 0, 2, 1, 0, 1, 1, 0, 2, 1, 0, 0, 3, 1, 0, 0, 1, 2, 1, 0, 3, 2, 1, 1, 2, 0, 2, 1, 1, 1, 1, 0, 0, 2, 2, 1, 3, 0, 2, 0, 2, 3, 3, 1, 1, 0, 0, 0, 2, 1, 3, 2, 1, 1, 2, 0, 4, 3, 2, 2, 1, 1, 2, 1, 0, 2, 2, 0, 3, 2, 3, 1, 4, 1, 1, 1, 0, 1, 3, 0, 2, 0, 1, 2, 4, 2, 2, 1, 1

Offset: 1

Antti Karttunen, Aug 09 2020

nonn

Totally additive because both A087436 and A331410 are.

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A000265, A046660, A087436, A331410, A336467, A336922.

Cf. also A336118, A336396.

A000265(n) = (n>>valuation(n,2));
A331410(n) = if(!bitand(n,n-1),0,1+A331410(n+(n/vecmax(factor(n)[, 1]))));
A336467(n) = { my(f=factor(n)); prod(k=1,#f~,if(2==f[k,1],1,(A000265(f[k,1]+1))^f[k,2])); };
A336921(n) = A331410(A336467(n));

a(n) = A331410(A336467(n)).
a(n) = A331410(n) - A087436(n).
a(n) = A336922(n) - A046660(A000265(n)).
For all n >= 1, a(n) <= A336118(n).

A359587 Fully multiplicative with a(p) = A008578(1+A329697(p)).

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 3, 1, 4, 2, 3, 2, 3, 3, 4, 1, 2, 4, 5, 2, 6, 3, 5, 2, 4, 3, 8, 3, 5, 4, 5, 1, 6, 2, 6, 4, 5, 5, 6, 2, 3, 6, 7, 3, 8, 5, 7, 2, 9, 4, 4, 3, 5, 8, 6, 3, 10, 5, 7, 4, 5, 5, 12, 1, 6, 6, 7, 2, 10, 6, 7, 4, 5, 5, 8, 5, 9, 6, 7, 2, 16, 3, 5, 6, 4, 7, 10, 3, 5, 8, 9, 5, 10, 7, 10, 2, 3, 9, 12, 4, 5, 4, 5, 3, 12

Offset: 1

Antti Karttunen, Jan 08 2023

Antti Karttunen, Table of n, a(n) for n = 1..16384
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537

Cf. A000265, A001222, A008578, A056239, A087436, A318995, A329697, A336396, A336466.

A008578(n) = if(1==n,1,prime(n-1));
A329697(n) = if(!bitand(n, n-1), 0, 1+A329697(n-(n/vecmax(factor(n)[, 1]))));
A359587(n) = { my(f=factor(n)); for(i=1, #f~, f[i, 1] = A008578(1+A329697(f[i, 1]))); factorback(f); };

For n >= 1: (Start)
a(A000265(n)) = a(2*n) = a(n).
A001222(a(n)) = A087436(n),
A056239(a(n)) = A329697(n),
A318995(a(n)) = A336396(n) = A329697(A336466(n)).
(End)

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

A336466 Fully multiplicative with a(p) = A000265(p-1) for any prime p, where A000265(k) gives the odd part of k.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A336469 a(n) = A329697(phi(n)), where A329697 is totally additive with a(2) = 0 and a(p) = 1 + a(p-1) for odd primes.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A336471 Lexicographically earliest infinite sequence such that a(i) = a(j) => A329697(i) = A329697(j) and A336158(i) = A336158(j), for all i, j >= 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A336921 a(n) = A331410(n) - A087436(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A359587 Fully multiplicative with a(p) = A008578(1+A329697(p)).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula