A245471 -id:A245471 - cp's OEIS frontend

A340873 a(n) is the number of iterations of A245471 needed to reach 1 starting from n.

0, 1, 3, 2, 6, 4, 4, 3, 11, 7, 7, 5, 9, 5, 5, 4, 12, 12, 12, 8, 8, 8, 8, 6, 10, 10, 10, 6, 14, 6, 6, 5, 21, 13, 13, 13, 13, 13, 13, 9, 17, 9, 9, 9, 17, 9, 9, 7, 19, 11, 11, 11, 11, 11, 11, 7, 15, 15, 15, 7, 15, 7, 7, 6, 22, 22, 22, 14, 14, 14, 14, 14, 22, 14

Offset: 1

Rémy Sigrist, Jan 31 2021

This sequence is well defined.
Sketch of proof:
- we focus on odd numbers n > 1,
- if the binary representation of n ends with k 0's and one 1:
       in two steps we obtain a number with the same binary length as n
       and ending with k-1 0's and one 1,
       iterating again will eventually give a number ending with two or more 1's,
- if the binary representation of n ends with k 1's (k > 1):
       in k+1 steps we obtain a number with a binary length strictly smaller
       than that of n,
- so any odd number > 1 will eventually reach the number 1.

			For n = 10:
- the trajectory of 10 is 10 -> 5 -> 14 -> 7 -> 8 -> 4 -> 2 -> 1,
- so a(10) = 7.

Cf. A006577, A245471, A341194, A341218, A341220, A341231, A341235.

a(n) = for (k=0, oo, if (n==1, return (k), n%2, n=bitxor(n, 2*n+1), n=n/2))

a(2*n) = a(n) + 1.

A341231 Irregular triangle read by rows giving trajectory from n to reach 1 under the map A245471.

Original entry on oeis.org

1, 2, 1, 3, 4, 2, 1, 4, 2, 1, 5, 14, 7, 8, 4, 2, 1, 6, 3, 4, 2, 1, 7, 8, 4, 2, 1, 8, 4, 2, 1, 9, 26, 13, 22, 11, 28, 14, 7, 8, 4, 2, 1, 10, 5, 14, 7, 8, 4, 2, 1, 11, 28, 14, 7, 8, 4, 2, 1, 12, 6, 3, 4, 2, 1, 13, 22, 11, 28, 14, 7, 8, 4, 2, 1, 14, 7, 8, 4, 2, 1

Offset: 1

Rémy Sigrist, Feb 07 2021

A340873 gives row lengths.

A341235 gives greatest terms.

			Table begins:
    1;
    2, 1;
    3, 4, 2, 1;
    4, 2, 1;
    5, 14, 7, 8, 4, 2, 1;
    6, 3, 4, 2, 1;
    7, 8, 4, 2, 1;
    8, 4, 2, 1;
    9, 26, 13, 22, 11, 28, 14, 7, 8, 4, 2, 1;
    10, 5, 14, 7, 8, 4, 2, 1;
    11, 28, 14, 7, 8, 4, 2, 1;
    12, 6, 3, 4, 2, 1;
    13, 22, 11, 28, 14, 7, 8, 4, 2, 1;
    14, 7, 8, 4, 2, 1;
    15, 16, 8, 4, 2, 1;
    16, 8, 4, 2, 1;
    ...

Rémy Sigrist, Table of n, a(n) for n = 1..9098 (rows 1..500)

Cf. A070165, A245471, A340873, A341235.

row(n) = { my (r=[n]); while (n>1, r=concat(r, n=if (n%2, bitxor(n, 2*n+1), n/2))); r }

T(n, 1) = n.

T(n, A340873(n)) = 1.

A065621 Reversing binary representation of n. Converting sum of powers of 2 in binary representation of a(n) to alternating sum gives n.

Original entry on oeis.org

1, 2, 7, 4, 13, 14, 11, 8, 25, 26, 31, 28, 21, 22, 19, 16, 49, 50, 55, 52, 61, 62, 59, 56, 41, 42, 47, 44, 37, 38, 35, 32, 97, 98, 103, 100, 109, 110, 107, 104, 121, 122, 127, 124, 117, 118, 115, 112, 81, 82, 87, 84, 93, 94, 91, 88, 73, 74, 79, 76, 69, 70, 67, 64, 193

Offset: 1

Marc LeBrun, Nov 07 2001

a(0)=0. The alternation is applied only to the nonzero bits and does not depend on the exponent of two. All integers have a unique reversing binary representation (see cited exercise for proof). Complement of A048724.
A permutation of the "odious" numbers A000069.
Write n-1 and 2n-1 in binary and add them mod 2; example: n = 6, n-1 = 5 = 101 in binary, 2n-1 = 11 = 1011 in binary and their sum is 1110 = 14, so a(6) = 14. - Philippe Deléham, Apr 29 2005
As already pointed out, this is a permutation of the odious numbers A000069 and A010060(A000069(n)) = 1, so A010060(a(n)) = 1; and A010060(A048724(n)) = 0. - Philippe Deléham, Apr 29 2005. Also a(n) = A000069(A003188(n - 1)).

			a(5) = 13 = 8 + 4 + 1 -> 8 - 4 + 1 = 5.

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1969, Vol. 2, p. 178, (exercise 4.1. Nr. 27)

Reinhard Zumkeller, Table of n, a(n) for n = 1..8192

Cf. A003188, A065620, A048724, A072219, A073122.
Differs from A115857 for the first time at n=19, where a(19)=55, while A115857(19)=23. Cf. A104895, A115872, A114389, A114390, A105081.
Cf. A245471.

import Data.Bits (xor, (.&.))
a065621 n = n `xor` 2 * (n - n .&. negate n) :: Integer
-- Reinhard Zumkeller, Mar 26 2014

f[n_] := BitXor[n, 2 n + 1]; Array[f, 60, 0] (* Robert G. Wilson v, Jun 09 2010 *)

a(n)=if(n<2,1,if(n%2==0,2*a(n/2),2*a((n+1)/2)-2*(-1)^((n-1)/2)+1))

def a(n): return n^(2*(n - (n & -n))) # Indranil Ghosh, Jun 04 2017

def A065621(n): return n^ (n&~-n)<<1 # Chai Wah Wu, Jun 29 2022

a(n) = if n=0 or n=1 then n else b+2*a(b+(1-2*b)*n)/2) where b is the least significant bit in n.
a(n) = n XOR 2 (n - (n AND -n)).
a(1) = 1, a(2n) = 2*a(n), a(2n+1) = 2*a(n+1) - 2(-1)^n + 1. - Ralf Stephan, Aug 20 2003
a(n) = A048724(n-1) - (-1)^n. - Ralf Stephan, Sep 10 2003
a(n) = Sum_{k=0..n} (1-(-1)^round(-n/2^k))/2*2^k. - Benoit Cloitre, Apr 27 2005
Closely related to Gray codes in another way: a(n) = 2 * A003188(n-1) + (n mod 2); a(n) = 4 * A003188((n-1) div 2) + (n mod 4). - Matt Erbst (matt(AT)erbst.org), Jul 18 2006 [corrected by Peter Munn, Jan 30 2021]
a(n) = n XOR 2(n AND NOT -n). - Chai Wah Wu, Jun 29 2022
a(n) = A003188(2n-1). - Friedjof Tellkamp, Jan 18 2024

More terms from Ralf Stephan, Sep 08 2003

A341235 a(n) is the greatest term in n-th row of A341231.

Original entry on oeis.org

1, 2, 4, 4, 14, 6, 8, 8, 28, 14, 28, 12, 28, 14, 16, 16, 62, 28, 52, 20, 62, 28, 56, 24, 62, 28, 44, 28, 52, 30, 32, 32, 122, 62, 100, 36, 110, 52, 104, 40, 122, 62, 124, 44, 118, 56, 112, 48, 122, 62, 84, 52, 112, 54, 88, 56, 110, 58, 76, 60, 100, 62, 64, 64

Offset: 1

Rémy Sigrist, Feb 07 2021

Records of a(n)/n appear to happen for n in A083318.

			For n = 10:
- the trajectory of 10 under A245471 is 10 -> 5 -> 14 -> 7 -> 8 -> 4 -> 2 -> 1,
- so a(10) = 14.

Cf. A025586, A083318, A245471, A340873, A341231.

a(n) = { my (m=n); while (n>1, m=max(m, n=if (n%2, bitxor(n, 2*n+1), n/2))); m }

a(n) >= n, equality implies that n equals 1 or is even.

a(n) < 4*n.

cp's OEIS Frontend

A340873 a(n) is the number of iterations of A245471 needed to reach 1 starting from n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A341231 Irregular triangle read by rows giving trajectory from n to reach 1 under the map A245471.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A065621 Reversing binary representation of n. Converting sum of powers of 2 in binary representation of a(n) to alternating sum gives n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Python

Formula

Extensions

A341235 a(n) is the greatest term in n-th row of A341231.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula