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

A335882 Numbers k for which A331410(k) = 2.

Original entry on oeis.org

5, 9, 10, 11, 13, 18, 20, 21, 22, 23, 26, 36, 40, 42, 44, 46, 47, 49, 52, 61, 72, 80, 84, 88, 92, 93, 94, 98, 104, 122, 144, 160, 168, 176, 184, 186, 188, 191, 196, 208, 217, 223, 244, 288, 320, 336, 352, 368, 372, 376, 381, 382, 383, 392, 416, 434, 446, 488, 576, 640, 672, 704, 736, 744, 752, 762, 764, 766, 784, 832, 868, 889, 892, 961

Offset: 1

Antti Karttunen, Jun 28 2020

nonn

Numbers k such that A000265(k) is either in A144482 or in A335874.

Each term is either of the form A335874(n)*2^k, for some n >= 2, and k >= 0, or a product of two terms of A335431, whether distinct or not.

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

Row 2 of A335430.
Cf. A331410, A335431, A335874 (after its initial 2, gives the primes in this sequence), A144482 (odd semiprimes in this sequence).
Cf. also A334102.

A000265(n) = (n>>valuation(n,2));
isA000668(n) = (isprime(n)&&!bitand(n,1+n));
isA144482(n) = ((2==bigomega(n))&&isA000668(vecmin(factor(n)[,1]))&&isA000668(vecmax(factor(n)[,1])));
isA335874(n) = ((n>2)&&isprime(n)&&isA000668(A000265(1+n)));
isA335882(n) = (isA335874(A000265(n))||isA144482(A000265(n)));

A335912 Numbers k for which A335885(k) = 2.

Original entry on oeis.org

9, 11, 13, 15, 18, 19, 21, 22, 23, 25, 26, 29, 30, 35, 36, 38, 41, 42, 44, 46, 47, 49, 50, 51, 52, 58, 60, 61, 67, 70, 72, 76, 79, 82, 84, 85, 88, 92, 93, 94, 97, 98, 100, 102, 104, 113, 116, 119, 120, 122, 134, 137, 140, 144, 152, 155, 158, 164, 168, 170, 176, 184, 186, 188, 191, 193, 194, 196, 200, 204, 208, 217, 223

Offset: 1

Antti Karttunen, Jun 30 2020

nonn

Numbers n such that when we start from k = n, and apply in some combination the nondeterministic maps k -> k - k/p and k -> k + k/p, (where p can be any of the odd prime factors of k), then for some combination we can reach a power of 2 in exactly two steps (but with no combination allowing 0 or 1 steps).

			For n = 70 = 2*5*7, if we first take p = 7 and apply the map n -> n + (n/p), we obtain 80 = 2^4 * 5. We then take p = 5, and apply the map n -> n - (n/p), to obtain 80-16 = 64 = 2^16. Thus we reached a power of 2 in two steps (and there are no shorter paths), therefore 70 is present in this sequence.
For n = 769, which is a prime, 769 - (769/769) yields 768 = 3 * 256. For 768 we can then apply either map to obtain a power of 2, as 768 - (768/3) = 512 = 2^9 and 768 + (768/3) = 1024 = 2^10. On the other hand, 769 + (769/769) = 770 and A335885(770) = 4, so that route would not lead to any shorter paths, therefore 769 is a term of this sequence.

Row 2 of A335910.
Cf. A000265, A335911, A335885.
Subsequences of semiprimes (union gives all odd semiprimes present): A144482, A333788, A336115.
Cf. also A334092, A335874, A336116, A336117 and A334102, A335882, A336122.

A335885(n) = { my(f=factor(n)); sum(k=1,#f~,if(2==f[k,1],0,f[k,2]*(1+min(A335885(f[k,1]-1),A335885(f[k,1]+1))))); };
isA335912(n) = (2==A335885(n));

A336116 Primes of the form q*2^h - 1, where q is a Fermat prime.

Original entry on oeis.org

2, 5, 11, 19, 23, 47, 67, 79, 191, 271, 383, 1087, 1279, 4111, 5119, 6143, 16447, 20479, 81919, 262147, 263167, 786431, 1114111, 1310719, 16842751, 17825791, 1073758207, 4295032831, 4311744511, 17180131327, 21474836479, 51539607551, 824633720831, 1168231104511

Offset: 1

Antti Karttunen, Jul 09 2020

nonn

Cf. A000265, A019434, A334092, A335874, A335885, A336117.

NestList[NestWhile[NextPrime, #, ! (PrimeQ[#2] && With[{p = NestWhile[BitShiftRight, #2 + 1, EvenQ] - 1}, BitAnd[p, p - 1] == 0 && With[{b = BitLength[p]}, BitAnd[b - 1, b - 2] == 0]]) &, 2] &, 2, 25] (* Jan Mangaldan, Jul 14 2020 *)

A000265(n) = (n>>valuation(n,2));
isA019434(n) = ((n>2)&&isprime(n)&&!bitand(n-2,n-1));
isA336116(n) = (isprime(n)&&isA019434(A000265(1+n)));

For all n >= 1, A335885(a(n)) <= 2.

More terms from Jinyuan Wang, Jul 11 2020

A336117 Primes of the form q*2^h + 1, where q is a Mersenne prime.

Original entry on oeis.org

7, 13, 29, 97, 113, 193, 449, 509, 769, 7937, 12289, 114689, 520193, 786433, 7340033, 8388593, 33292289, 33550337, 469762049, 2130706433, 3221225473, 8588886017, 137438691329, 206158430209, 2199023254529, 6597069766657, 562948879679489, 7881299347898369, 9007182074871809

Offset: 1

Antti Karttunen, Jul 09 2020

nonn

Cf. A000265, A000668, A334092, A335874, A335885, A336116.

A000265(n) = (n>>valuation(n,2));
isA000668(n) = (isprime(n)&&!bitand(n,1+n));
isA336117(n) = (isprime(n)&&isA000668(A000265(n-1)));

For all n >= 1, A335885(a(n)) <= 2.

More terms from Jinyuan Wang, Jul 11 2020

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

A335882 Numbers k for which A331410(k) = 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A335912 Numbers k for which A335885(k) = 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A336116 Primes of the form q*2^h - 1, where q is a Fermat prime.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A336117 Primes of the form q*2^h + 1, where q is a Mersenne prime.

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

Extensions