A334108 -id:A334108 - 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.

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

Offset: 1

Ali Sada, Jan 16 2020

nonn

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

			The trajectory of 15 is [15,18,24,32], taking 3 iterations to reach 32. So, a(15) = 3.

Antti Karttunen, Table of n, a(n) for n = 1..65537
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.

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. array A335430, and its rows A335431, A335882, and also A335874.
Cf. also A329697 (analogous sequence when using the map k -> k - k/p), A335878.
Cf. also A330437, A335884, A335885, A336362, A336363 for other similar iterations.

f:=func; g:=func; 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

a[n_] := -1 + Length @ NestWhileList[# + #/FactorInteger[#][[-1, 1]] &, n, # / 2^IntegerExponent[#, 2] != 1 &]; Array[a, 100] (* Amiram Eldar, Jan 16 2020 *)

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

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

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

From Antti Karttunen, Apr 29 2020: (Start)
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.
a(2n) = a(A000265(n)) = a(n).
If A209229(n) == 1, a(n) = 0, otherwise a(n) = 1 + a(n+A052126(n)), or equally, 1 + a(n+(n/A078701(n))).
a(n) = A334097(n) - A334098(n).
a(A122111(n)) = A334108(n).
(End)
a(n) = A334861(n) - A329697(n). - Antti Karttunen, May 14 2020
a(n) = a(A336467(n)) + A087436(n) = A336921(n) + A087436(n). - Antti Karttunen, Mar 16 2021

Data section extended up to a(105) by Antti Karttunen, Apr 29 2020

A334107 a(n) = A329697(A122111(n)).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Apr 29 2020

nonn

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

Cf. A001248, A008578 (positions of zeros), A064989, A105560, A122111, A322865, A329697, A334108, A334109, A334201.

Map[Length@ NestWhileList[# - #/FactorInteger[#][[-1, 1]] &, #, # != 2^IntegerExponent[#, 2] &] - 1 &, Array[Times @@ Table[Prime[LengthWhile[#1, # >= j &] /. 0 -> 1], {j, #2}] & @@ {#, Max[#]} &@ PrimePi@ Flatten[ConstantArray[#1, {#2}] & @@@ FactorInteger@ #] &, 105] ] (* Michael De Vlieger, May 14 2020, after Robert G. Wilson v at A329697 *)

A064989(n) = {my(f); f = factor(n); if((n>1 && f[1,1]==2), f[1,2] = 0); for (i=1, #f~, f[i,1] = precprime(f[i,1]-1)); factorback(f)};
A122111(n) = if(1==n,n,prime(bigomega(n))*A122111(A064989(n)));
A329697(n) = if(!bitand(n,n-1),0,1+A329697(n-(n/vecmax(factor(n)[, 1]))));
A334107(n) = A329697(A122111(n));

a(n) = A329697(A122111(n)) = A329697(A322865(n)).
a(n) = A329697(A105560(n)) + a(A064989(n)).
For n >= 1, a(A001248(n)) = n, and these seem to be also the first occurrences of each n.

A334109 a(n) = A329697(A225546(n)).

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 0, 1, 2, 0, 0, 1, 0, 0, 0, 1, 0, 2, 0, 1, 0, 0, 0, 1, 4, 0, 2, 1, 0, 0, 0, 1, 0, 0, 0, 3, 0, 0, 0, 1, 0, 0, 0, 1, 2, 0, 0, 1, 8, 4, 0, 1, 0, 2, 0, 1, 0, 0, 0, 1, 0, 0, 2, 2, 0, 0, 0, 1, 0, 0, 0, 3, 0, 0, 4, 1, 0, 0, 0, 1, 2, 0, 0, 1, 0, 0, 0, 1, 0, 2, 0, 1, 0, 0, 0, 1, 0, 8, 2, 5, 0, 0, 0, 1, 0

Offset: 1

Antti Karttunen, Apr 29 2020

nonn

Conjecture: Each k >= 0 occurs for the first time at A334110(k) = A019565(k)^2. Note that each k must occur first time on square n, because of the identity a(n) = a(A008833(n)). However, is there any reason to exclude squares with prime exponents > 2 from the candidates? See also comments in A334204.

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

Cf. A001248, A005117 (positions of zeros), A334110.
Cf. A003961, A008833, A019565, A059895, A225546, A329697, A331590, A331736, A334204, A334860.
Cf. also A334107, A334108.

Map[-1 + Length@ NestWhileList[# - #/FactorInteger[#][[-1, 1]] &, #, # != 2^IntegerExponent[#, 2] &] &, Array[If[# == 1, 1, Times @@ Flatten@ Map[Function[{p, e}, Map[Prime[Log2@ # + 1]^(2^(PrimePi@ p - 1)) &, DeleteCases[NumberExpand[e, 2], 0]]] @@ # &, FactorInteger[#]]] &, 105] ] (* Michael De Vlieger, May 26 2020 *)

A019565(n) = factorback(vecextract(primes(logint(n+!n, 2)+1), n));
A329697(n) = if(!bitand(n,n-1),0,1+A329697(n-(n/vecmax(factor(n)[, 1]))));
A334109(n) = { my(f=factor(n),pis=apply(primepi,f[,1]),es=f[,2]); sum(k=1,#f~,(2^(pis[k]-1))*A329697(A019565(es[k]))); };

Additive with a(prime(i)^j) = A000079(i-1) * A329697(A019565(j)), a(m*n) = a(m)+a(n) if gcd(m,n) = 1.
Alternatively, additive with a(prime(i)^(2^k)) = 2^(i-1) * A329697(prime(k+1)), a(m*n) = a(m)+a(n) if A059895(m,n) = 1. - Peter Munn, May 04 2020
a(n) = A329697(A225546(n)) = A329697(A331736(n)).
a(n) = a(A008833(n)).
For all n >= 0, a(A334110(n)) = n, a(A334860(n)) = A334204(n).
a(A331590(m,k)) = a(m) + a(k); a(A003961(n)) = 2*a(n). - Peter Munn, Apr 30 2020

A339877 a(n) = A336467(A122111(n)).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 1, 1, 1, 1, 1, 3, 1, 3, 1, 1, 1, 1, 1, 1, 9, 3, 1, 3, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 3, 9, 1, 1, 3, 1, 3, 1, 3, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 9, 7, 1, 3, 1, 3, 1, 3, 1, 3, 1, 1, 9, 3, 1, 3, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 3, 1, 1, 1, 7, 1, 3, 9, 1, 1, 3, 1, 1, 9

Offset: 1

Antti Karttunen, Dec 25 2020

nonn

Antti Karttunen, Table of n, a(n) for n = 1..12166
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537
Index entries for sequences computed from indices in prime factorization

Cf. A000265, A064989, A105560, A122111, A336467.

Cf. also A339876, A334108.

A000265(n) = (n>>valuation(n,2));
A122111(n) = if(1==n,n,my(f=factor(n), es=Vecrev(f[,2]),is=concat(apply(primepi,Vecrev(f[,1])),[0]),pri=0,m=1); for(i=1, #es, pri += es[i]; m *= prime(pri)^(is[i]-is[1+i])); (m));
A336467(n) = { my(f=factor(n)); prod(k=1,#f~,if(2==f[k,1],1,(A000265(f[k,1]+1))^f[k,2])); };
A339877(n) = A336467(A122111(n));

A064989(n) = {my(f); f = factor(n); if((n>1 && f[1,1]==2), f[1,2] = 0); for (i=1, #f~, f[i,1] = precprime(f[i,1]-1)); factorback(f)};
A105560(n) = if(1==n,n,prime(bigomega(n)));
A339877(n) = if(1==n||isprime(n),1,A000265(A105560(n)+1) * A339877(A064989(n)));

For noncomposite n, a(n) = 1, for composite n, a(n) = A000265(A105560(n)+1) * a(A064989(n)).

a(n) = A336467(A122111(n)).

A339874 Lexicographically earliest infinite sequence such that a(i) = a(j) => f(i) = f(j), where f(n) = A052126(n) for n > 1, and f(1) = 0.

Original entry on oeis.org

1, 2, 2, 3, 2, 3, 2, 4, 5, 3, 2, 4, 2, 3, 5, 6, 2, 7, 2, 4, 5, 3, 2, 6, 8, 3, 9, 4, 2, 7, 2, 10, 5, 3, 8, 11, 2, 3, 5, 6, 2, 7, 2, 4, 9, 3, 2, 10, 12, 13, 5, 4, 2, 14, 8, 6, 5, 3, 2, 11, 2, 3, 9, 15, 8, 7, 2, 4, 5, 13, 2, 16, 2, 3, 17, 4, 12, 7, 2, 10, 18, 3, 2, 11, 8, 3, 5, 6, 2, 14, 12, 4, 5, 3, 8, 15, 2, 19, 9, 20, 2, 7, 2, 6, 17

Offset: 1

Antti Karttunen, Dec 25 2020

nonn

For all i, j:
  A305800(i) = A305800(j) => a(i) = a(j),
  a(i) = a(j) => A001222(i) = A001222(j),
  a(i) = a(j) => A322826(i) = A322826(j).

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

Cf. A052126, A322826.

Cf. also A305800, A300226, A334107, A334108.

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; };
A052126(n) = if(1==n,n,(n/vecmax(factor(n)[, 1])));
Aux339874(n) = if(1==n,0,A052126(n));
v339874 = rgs_transform(vector(up_to, n, Aux339874(n)));
A339874(n) = v339874[n];

a(1) = 1; for n > 1, a(n) = 1 + A322826(n).

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

PARI

Formula

Extensions

A334107 a(n) = A329697(A122111(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A334109 a(n) = A329697(A225546(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A339877 a(n) = A336467(A122111(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

Formula

A339874 Lexicographically earliest infinite sequence such that a(i) = a(j) => f(i) = f(j), where f(n) = A052126(n) for n > 1, and f(1) = 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula