A336921 -id:A336921 - 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

A336467 Fully multiplicative with a(2) = 1 and a(p) = A000265(p+1) for odd primes p, with A000265(k) giving the odd part of k.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 3, 1, 7, 1, 3, 1, 9, 1, 5, 3, 1, 3, 3, 1, 9, 7, 1, 1, 15, 3, 1, 1, 3, 9, 3, 1, 19, 5, 7, 3, 21, 1, 11, 3, 3, 3, 3, 1, 1, 9, 9, 7, 27, 1, 9, 1, 5, 15, 15, 3, 31, 1, 1, 1, 21, 3, 17, 9, 3, 3, 9, 1, 37, 19, 9, 5, 3, 7, 5, 3, 1, 21, 21, 1, 27, 11, 15, 3, 45, 3, 7, 3, 1, 3, 15, 1, 49, 1, 3, 9, 51, 9, 13, 7, 3

Offset: 1

Antti Karttunen, Jul 22 2020

For the comment here, we extend the definition of the first 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 of the same Cunningham 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 Sophie Germain primes (in A005384), then replacing any of them with 2p+1 ("safe primes", i.e., the corresponding terms of A005385), gives a new number m, for which a(m) = a(n). And vice versa, the same is true for any safe prime factors > 5 of n (that are in A005385), then replacing any one of them with (p-1)/2 will not affect the result. For example, a(5*11*23*47) = a(11*11*23*23) = a(5^4) = a(11^4) = a(23^4) = 81, as 5, 11, 23 and 47 are in the same Cunningham chain of the first kind.

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, A003959, A206787, A336390, A336392, A336651, A336921, A336922, A351461.

Cf. also A335915, A336466 (similar sequences).

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

For all n >= 1, A331410(a(n)) = A336921(n).
From Antti Karttunen, Nov 21 2023: (Start)
a(n) = A335915(n) / A336466(n).
a(1) = 1, and for n > 1, a(n) = A000265(A206787(n)) * a(A336651(n)).
(End)

A336922 a(n) = A331410(n) - A005087(n).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Aug 09 2020

nonn

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

Cf. A000265, A005087, A054784 (positions of zeros), A331410, A336467, A336921, A336923.

Cf. also A336469.

A005087(n) = omega(n>>valuation(n,2));
A331410(n) = if(!bitand(n,n-1),0,1+A331410(n+(n/vecmax(factor(n)[, 1]))));
A336922(n) = (A331410(n) - A005087(n));

a(n) = A331410(n) - A005087(n).

a(n) = A336921(n) + A046660(A000265(n)).

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

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Aug 10 2020

nonn

Restricted growth sequence transform of the ordered pair [A331410(n), A336158(n)].
For all i, j:
  A336390(i) = A336390(j) => a(i) = a(j)
  a(i) = a(j) => A336921(i) = A336921(j),
  a(i) = a(j) => A336922(i) = A336922(j) => A336923(i) = A336923(j).

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

Cf. A331410, A336467, A336390, A336921, A336922, A336923.

Cf. also A336471.

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));
A331410(n) = if(!bitand(n,n-1),0,1+A331410(n+(n/vecmax(factor(n)[, 1]))));
Aux336391(n) = [A331410(n), A336158(n)];
v336391 = rgs_transform(vector(up_to, n, Aux336391(n)));
A336391(n) = v336391[n];

A341622 Numbers that are either already perfect, or a perfect number is eventually reached if we start doubling them.

Original entry on oeis.org

3, 6, 7, 14, 28, 31, 62, 124, 127, 248, 254, 496, 508, 1016, 2032, 4064, 8128, 8191, 16382, 32764, 65528, 131056, 131071, 262112, 262142, 524224, 524284, 524287, 1048448, 1048568, 1048574, 2096896, 2097136, 2097148, 4193792, 4194272, 4194296, 8387584, 8388544, 8388592, 16775168, 16777088, 16777184, 33550336, 33554176, 33554368

Offset: 1

Antti Karttunen, Feb 19 2021

nonn

Numbers whose closure under map x -> 2x contains a perfect number (one of the terms of A000396).
Numbers k such that A341621(k) > A336915(k). No powers of 2 are included because they stay deficient forever.
Sequence is the union of odd perfect numbers (whose existence is contested, see e.g., A326051), and the numbers of the form (2^p - 1) * 2^e, where p is one of the primes in A000043, and e < p.

Cf. A000043, A000396, A005101, A326051, A336915, A336921.

Subsequence of A335431 provided there are no odd perfect numbers.

m = MersennePrimeExponent[Range[8]]; f[p_] := 2^Range[0, p - 1]*(2^p - 1); Select[Sort @ Flatten[f /@ m], # <= 2^m[[-1]] - 1 &] (* Amiram Eldar, Feb 20 2021, for calculating terms below 10^1500, the current lower bound for odd perfect numbers *)

isA341622(n) = if(!bitand(n,n-1), 0, for(i=0,oo,my(n2 = n+n); if(sigma(n) >= n2, return(sigma(n)==n2)); n = n2));

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

A336467 Fully multiplicative with a(2) = 1 and a(p) = A000265(p+1) for odd primes p, with A000265(k) giving the odd part of k.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A336922 a(n) = A331410(n) - A005087(n).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A341622 Numbers that are either already perfect, or a perfect number is eventually reached if we start doubling them.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI