A056539 -id:A056539 - cp's OEIS frontend

A235145 a(n) = Number of steps to reach a fixed point or 2-cycle, when iterating A235027 starting from value n.

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

Offset: 0

Antti Karttunen, Jan 03 2014

Equally, a(n) = minimum number of steps needed to repeat k = A235027(k)(starting from k = n) until A001222(A235027(k)) = A001222(k).

Or in other words, how many times are needed to repeatedly factorize the number, to reverse the bits of each odd prime factor (with A056539) and factorize and bit-reverse the reversed factors again, until the number of prime divisors no more grows, meaning that we have found either a fixed point or entered a cycle of two.

			19, '10011' in binary, when reversed, yields '11001' = 25, when factored, yields 5 * 5, ('101' * '101' in binary), which divisors stay same when reversed, thus it took one iteration step to reach a point where the number of prime divisors no more grows. Thus a(19)=1.

Antti Karttunen, Table of n, a(n) for n = 0..10001

A235146 gives the positions of records. Cf. A001222, A056539, A074832, A235027.

revbits(n) = fromdigits(Vecrev(binary(n)), 2);
a235027(n) = {f = factor(n); for (k=1, #f~, if (f[k,1] != 2, f[k,1] = revbits(f[k,1]););); factorback(f);}
find(v, newn) = {for (k=1, #v, if (v[#v -k + 1] == newn, return (k));); return (0);}
a(n) = {ok = 0; v = [n]; while (! ok, newn = a235027(n); ind = find(v, newn); if (ind, ok = 1, v = concat(v, newn); n = newn);); #v - ind;} \\ Michel Marcus, Aug 06 2017

If A235027(A235027(n)) = n, a(n)=0, otherwise 1+a(A235027(n)).
Equally, if A001222(A235027(n)) = A001222(n), a(n)=0, otherwise 1+a(A235027(n)).
a(2n) = a(n), and in general, for composite values a(u * v) = max(a(u),a(v)).
For composite n, a(n) = Max_{p|n} a(p). [The above reduces to this: select the maximal value from all values a(p) computed for primes p dividing n]
For prime p, a(p) = 0 if A056539(p) is also prime (p is 2 or in A074832), otherwise a(p) = 1+a(A056539(p)).

A071162 Simple rewriting of binary expansion of n resulting A014486-codes for rooted binary trees with height equal to number of internal vertices. (Binary trees where at each internal vertex at least the other child is leaf).

Original entry on oeis.org

0, 2, 10, 12, 42, 44, 52, 56, 170, 172, 180, 184, 212, 216, 232, 240, 682, 684, 692, 696, 724, 728, 744, 752, 852, 856, 872, 880, 936, 944, 976, 992, 2730, 2732, 2740, 2744, 2772, 2776, 2792, 2800, 2900, 2904, 2920, 2928, 2984, 2992, 3024, 3040, 3412, 3416

Offset: 0

Antti Karttunen, May 14 2002

Essentially rewrites in binary expansion of n each 0 -> 01, 1X -> 1(rewrite X)0, where X is the maximal suffix after the 1-bit, which will be rewritten recursively (see the given Scheme-function). Because of this, the terms of the binary length 2n are counted by 2's powers, A000079.
In rooted plane (general) tree context, these are those totally balanced binary sequences (terms of A014486) where non-leaf subtrees can occur only as the rightmost branch (at any level of a general tree), but nowhere else. (Cf. A209642).
Also, these are exactly those rooted plane trees whose Łukasiewicz words happen to be valid asynchronous siteswap juggling patterns. (This was the original, albeit quite frivolous definition of this sequence for almost ten years 2002-2012. Cf. A071160.)

Antti Karttunen, Table of n, a(n) for n = 0..65535
OEIS Wiki, Łukasiewicz words
Index entries for sequences related to Łukasiewicz

a(n) = A014486(A071163(n)) = A036044(A209642(n)) = A056539(A209642(n)).
A209859 provides an "inverse" function, i.e. A209859(a(n)) = n for all n.
Cf. A209636, A209637, A209862.

def a036044(n): return int(''.join('1' if i == '0' else '0' for i in bin(n)[2:][::-1]), 2)
def a209642(n):
    s=0
    i=1
    while n!=0:
        if n%2==0:
            n//=2
            s=4*s + 1
        else:
            n=(n - 1)//2
            s=(s + i)*2
        i*=4
    return s
def a(n): return 0 if n==0 else a036044(a209642(n))
print([a(n) for n in range(101)]) # Indranil Ghosh, May 25 2017

(define (A071162 n) (let loop ((n n) (s 0) (i 1)) (cond ((zero? n) s) ((even? n) (loop (/ n 2) (+ s i) (* i 4))) (else (loop (/ (- n 1) 2) (* 2 (+ s i)) (* i 4))))))

A209642 A014486-codes for rooted plane trees where non-leaf branching can occur only at the leftmost branch of any level, but nowhere else. Reflected from the corresponding rightward branching codes in A071162, thus not in ascending order.

Original entry on oeis.org

0, 2, 10, 12, 42, 50, 52, 56, 170, 202, 210, 226, 212, 228, 232, 240, 682, 810, 842, 906, 850, 914, 930, 962, 852, 916, 932, 964, 936, 968, 976, 992, 2730, 3242, 3370, 3626, 3402, 3658, 3722, 3850, 3410, 3666, 3730, 3858, 3746, 3874, 3906, 3970, 3412, 3668, 3732, 3860, 3748, 3876, 3908, 3972, 3752, 3880, 3912, 3976, 3920, 3984, 4000, 4032

Offset: 0

Antti Karttunen, Mar 11 2012

Like with A071162, a(n) can be computed directly from the binary expansion of n. (See the Scheme function given). However, the function is not monotone. A209641 gives the same terms in ascending order.

Antti Karttunen, Table of n, a(n) for n = 0..32767

a(n) = A209641(A209861(n)).

def a(n):
    s=0
    i=1
    while n!=0:
        if n%2==0:
            n//=2
            s=4*s + 1
        else:
            n=(n - 1)//2
            s=(s + i)*2
        i*=4
    return s
print([a(n) for n in range(101)]) # Indranil Ghosh, May 25 2017, translated from Antti Karttunen's SCHEME code

(define (A209642 n) (let loop ((n n) (s 0) (i 1)) (cond ((zero? n) s) ((even? n) (loop (/ n 2) (+ (* 4 s) 1) (* i 4))) (else (loop (/ (- n 1) 2) (* 2 (+ s i)) (* i 4))))))

a(n) = A056539(A071162(n)) = A036044(A071162(n)). (See also the given Scheme-function).

A235030 Numbers such that A235027(A235027(n)) <> n; Numbers which are divisible by any of the odd terms of A204219.

Original entry on oeis.org

19, 38, 57, 59, 76, 79, 89, 95, 103, 109, 114, 118, 133, 137, 139, 149, 152, 157, 158, 171, 177, 178, 179, 190, 191, 206, 209, 211, 218, 228, 236, 237, 239, 241, 247, 266, 267, 271, 274, 278, 281, 285, 293, 295, 298, 304, 309, 311, 314, 316, 317, 323, 327, 342

Offset: 1

Antti Karttunen, Jan 02 2014

Sequence consists of all the primes in A204219 (after 2), together with all of their multiples.
Note that this is not the same as the numbers that do not occur in A235027 ("Garden of Eden" numbers for A235027), a subsequence of this sequence, which begins as: 19, 38, 57, 59, 76, 79, 89, 95, 103, 109, 114, 118, 133, 137, 139, 149, 152, 157, 158, 171, 177, 178, 179, 190, 191, 206, 211, 218, 228, 236, 237, 239, 241, 266, 267, 271, 274, 278, 281, 285, 293, 298, 304, 309, 311, 314, 316, 317, 327, 342, 347, 354, 356, 358, ...
The first term that occurs in this sequence, but not in the "GoE"-sequence is a(27)=209, as a(139) = 209 = 11*19 and 139 = A235146(2), the least integer which requires two steps to reach a fixed point or 2-cycle.
Both the above "GoE"-sequence, and its differences from this will be submitted later.

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

Cf. A204219, A235027, A235145, A235146, A056539.

A235146 a(n) = Least integer k such that it takes n iterations of "factor and reverse bits of odd prime divisors" (A235027) before a fixed point or cycle of 2 is reached; records in A235145.

Original entry on oeis.org

0, 19, 139, 719, 4793, 23773, 260863, 2375231, 21793843

Offset: 0

Antti Karttunen, Jan 03 2014

Note, as for all composite values A235145(u * v) = max(A235145(u), A235145(v)) which can be further reduced as A235145(n) = Max_{p|n} A235145(p), and because for any odd prime p, lpf(A056539(p)) >= 3 (where lpf = A020639, the least prime dividing n) while 1/2 < A056539(n)/n < 2, it follows that this sequence gives also the positions of the records in A235145, as its new values must appear in order.
Also, because of that multiplicativity criterion, all terms (after zero) must be primes, and specifically, the terms are a subset of A235030 (i.e., of A204219).
Conjecture: additional property is that the primes here belong to that subset of p in A204219 for which A056539(p) > p. The list of such primes begins as: 19, 79, 103, 137, 139, 149, 157, 179, 191, 239, 271, 281, 293, 311, 317, 347, 367, 379, 439, 523, 541, 547, 557, 563, 569, 587, 607, 613, 647, 659, 719, 733, 743, 751, 787, ...

A subset of A235030 and A204219.

Cf. A235145, A235027, A056539.

revbits(n) = fromdigits(Vecrev(binary(n)), 2);
a235027(n) = {f = factor(n); for (k=1, #f~, if (f[k,1] != 2, f[k,1] = revbits(f[k,1]););); factorback(f);}
find(v, newn) = {for(k=1, #v, if (v[#v -k + 1] == newn, return (k));); return (0);}
a235145(n) = {ok = 0; v = [n]; while (! ok, newn = a235027(n); ind = find(v, newn); if (ind, ok = 1, v = concat(v, newn); n = newn);); #v - ind;}
a(n) = {k = 0; while (a235145(k) != n, k = nextprime(k+1)); k;}
lista(nn) = {kprec = 0; for (n=0, nn, k = kprec; while (a235145(k) != n, k = nextprime(k+1)); print1(k, ", "); kprec = k;);} \\ Michel Marcus, Aug 06 2017

a(5)-a(8) from Michel Marcus, Aug 06 2017

A280504 a(n) = A280500(n,A280503(n)).

Original entry on oeis.org

1, 1, 1, 2, 1, 3, 1, 4, 1, 1, 11, 1, 13, 7, 1, 8, 1, 9, 19, 10, 1, 11, 13, 6, 25, 13, 1, 7, 11, 15, 1, 16, 1, 15, 13, 2, 37, 1, 11, 12, 41, 1, 25, 22, 1, 13, 47, 4, 11, 25, 1, 1, 19, 3, 55, 1, 13, 11, 59, 5, 61, 31, 1, 32, 1, 33, 67, 34, 69, 35, 61, 36, 1, 37, 13, 38, 59, 39, 25, 40, 81, 41, 11, 42, 1, 43, 87, 44, 55, 45, 91, 46, 1, 47, 19, 24, 97, 49, 1, 25, 13

Offset: 1

Antti Karttunen, Jan 09 2017

Antti Karttunen, Table of n, a(n) for n = 1..8192
Index entries for sequences related to binary expansion of n

Cf. A048720, A056539, A280500, A280503, A280506.

Cf. A044918 (very likely gives the positions of all ones).

(define (A280504 n) (A280500bi n (A280503 n))) ;; Code for A280500bi given in A280500.

a(n) = A280500(n,A280503(n)).
Other identities. For all n >= 1:
A048720(a(n), A280503(n)) = n.

A166166 Write n in binary with each run (of either digit b) of the k-th longest distinct run-length replaced with a run of digit b of a length equal to that of the k-th shortest distinct run-length. Convert back to decimal for a(n). (See comment.)

Original entry on oeis.org

0, 1, 2, 3, 6, 5, 4, 7, 14, 27, 10, 25, 12, 19, 8, 15, 30, 119, 108, 13, 102, 21, 100, 113, 28, 11, 76, 9, 24, 71, 16, 31, 62, 495, 952, 59, 54, 435, 52, 57, 910, 411, 42, 409, 50, 403, 904, 481, 60, 55, 44, 51, 38, 307, 36, 49, 56, 39, 568, 35, 48, 271, 32, 63, 126

Offset: 0

Leroy Quet, Oct 08 2009

This sequence is a self-inverse permutation of the positive integers.
Clarification of definition: Let b(k) be the k-th largest distinct run-length (considering both runs of 0's and of 1's) in binary n. Let r be the number of distinct run-lengths in binary n. Rewrite binary n by replacing each run (of any given digit) of length b(k) with a run (of that same digit) of length b(r+1-k). Convert the resulting binary number to decimal to get a(n).
A binary number alternates between "runs" each completely of 1's and runs completely of 0's. No two runs of the same digit are consecutive.

			134 in binary is 10000110. So there is a run of length 1, followed by a run of length 4, followed by a run of length 2, followed finally by a run of length 1. The distinct run-lengths, written in order from smallest to largest, are therefore (1,2,4). So a(134) is the decimal equivalent of the binary number made by writing four 1's (since the first run in binary 134 is of the shortest length, and the longest run is of length 4), followed by one 0 (since the second run in binary 134 is of the longest length, and the shortest run is of length 1), followed by a run of two 1's (since the third run in binary 134 is of the second largest length, and the second shortest length is also 2), followed finally by a run of four 0's; getting a(134) is the decimal equivalent of binary 11110110000, which is 1968.

Cf. A056539, A166404.

Sequence extended by Ray Chandler, Oct 18 2009. Scheme-code added, as well as term a(0)=0 prepended (without affecting the offset of the following terms) by Antti Karttunen, Oct 20 2009

A377834 a(1) = 0, and for n > 0, if A055932(n) = 2^r(1) * 3^r(2) * ... * prime(k)^r(k) with r(k) > 0 (where prime(k) denotes the k-th prime number), then the run lengths of the binary expansion of a(n) are (r(1), r(2), ..., r(k)).

Original entry on oeis.org

0, 1, 3, 2, 7, 6, 15, 4, 14, 5, 31, 12, 30, 8, 13, 63, 28, 9, 62, 24, 29, 127, 60, 11, 16, 25, 126, 10, 56, 61, 255, 17, 124, 27, 48, 57, 254, 26, 120, 19, 125, 32, 511, 49, 252, 59, 18, 112, 121, 23, 510, 33, 58, 248, 51, 253, 96, 1023, 22, 113, 508, 123, 50

Offset: 1

Rémy Sigrist, Nov 09 2024

This sequence is a bijection from the positive integers to the nonnegative integers.

			For n = 15: A055932(15) = 60 = 2^2 * 3^1 * 5^1, so the run lengths of the binary expansion of a(15) are (2, 1, 1), the binary expansion of a(15) is "1101", and a(15) = 13.

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Rémy Sigrist, PARI program
Index entries for sequences that are permutations of the natural numbers

See A377836 for a similar sequence.

Cf. A005811, A055932, A124830, A377835 (inverse).

PARI
```
\\ See Links section.
```

A005811(a(n)) = A124830(n).

a(n) = A056539(A377836(n)).

A377836 a(1) = 0, and for n > 0, if A055932(n) = 2^r(1) * 3^r(2) * ... * prime(k)^r(k) with r(k) > 0 (where prime(k) denotes the k-th prime number), then the run lengths of the binary expansion of a(n) are (r(k), r(k-1), ..., r(1)).

Original entry on oeis.org

0, 1, 3, 2, 7, 4, 15, 6, 8, 5, 31, 12, 16, 14, 11, 63, 24, 9, 32, 28, 23, 127, 48, 13, 30, 19, 64, 10, 56, 47, 255, 17, 96, 27, 60, 39, 128, 20, 112, 25, 95, 62, 511, 35, 192, 55, 22, 120, 79, 29, 256, 33, 40, 224, 51, 191, 124, 1023, 18, 71, 384, 111, 44, 240

Offset: 1

Rémy Sigrist, Nov 09 2024

This sequence is a bijection from the positive integers to the nonnegative integers.

			For n = 15: A055932(15) = 60 = 2^2 * 3^1 * 5^1, so the run lengths of the binary expansion of a(15) are (1, 1, 2), the binary expansion of a(15) is "1011", and a(15) = 11.

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Rémy Sigrist, PARI program
Index entries for sequences that are permutations of the natural numbers

See A377834 for a similar sequence.

Cf. A005811, A055932, A124830, A377837 (inverse).

PARI
```
\\ See Links section.
```

A005811(a(n)) = A124830(n).

a(n) = A056539(A377834(n)).

A166404 Self-inverse permutation of natural numbers obtained by exchanging the run lengths of adjacent runs of ones and zeros in the binary expansion of n, starting from the most significant run of 1's. (See the example lines).

Original entry on oeis.org

0, 1, 2, 3, 6, 5, 4, 7, 14, 13, 10, 11, 12, 9, 8, 15, 30, 29, 26, 27, 22, 21, 20, 23, 28, 25, 18, 19, 24, 17, 16, 31, 62, 61, 58, 59, 54, 53, 52, 55, 46, 45, 42, 43, 44, 41, 40, 47, 60, 57, 50, 51, 38, 37, 36, 39, 56, 49, 34, 35, 48, 33, 32, 63, 126, 125, 122, 123, 118, 117

Offset: 0

Antti Karttunen, Oct 20 2009

			68 in binary is 1000100, so it consists of runs of 1, 3, 1 and 2 bits of the same value (alternatively 1 or 0) counted from the most significant end. Swapping these (the first with the second, the third with the fourth, etc.) gives the run lengths of [3,1,2,1], and the reconstructed binary string looks now as 1110110, which is 118 in binary. Thus a(68)=118.
Likewise, 67 in binary is 1000011, so it consists of runs of 1, 4 and 2 counted from the most significant end. Now we can swap just the first and second of these runs, with the remaining third run staying as it is, so we get run lengths of [4,1,2], and the reconstructed binary string looks now as 1111011, which is 123 in binary. Thus a(67)=123.

Cf. A056539, A166166.

def a(n):
    if n==0: return 0
    x=bin(n)[2:]
    r=[]
    s=1
    p=""
    for i in range(1, len(x)):
        if x[i - 1]==x[i]: s+=1
        else:
            r+=[s, ]
            s=1
    l=r+[s]
    L=[]
    if len(l)%2==0:
        for i in range(0, len(l), 2): L+=[l[i + 1], l[i]]
    else:
        b=l[-1]
        for i in range(0, len(l) - 1, 2): L+=[l[i + 1], l[i]]
        L+=[b, ]
    for i in range(len(L)):
        if i%2==0: p+='1'*L[i]
        else: p+='0'*L[i]
    return int(p, 2)
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 12 2017

cp's OEIS Frontend

A235145 a(n) = Number of steps to reach a fixed point or 2-cycle, when iterating A235027 starting from value n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A071162 Simple rewriting of binary expansion of n resulting A014486-codes for rooted binary trees with height equal to number of internal vertices. (Binary trees where at each internal vertex at least the other child is leaf).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Scheme

A209642 A014486-codes for rooted plane trees where non-leaf branching can occur only at the leftmost branch of any level, but nowhere else. Reflected from the corresponding rightward branching codes in A071162, thus not in ascending order.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Scheme

Formula

A235030 Numbers such that A235027(A235027(n)) <> n; Numbers which are divisible by any of the odd terms of A204219.

Views

Author

Keywords

Comments

Links

Crossrefs

A235146 a(n) = Least integer k such that it takes n iterations of "factor and reverse bits of odd prime divisors" (A235027) before a fixed point or cycle of 2 is reached; records in A235145.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Extensions

A280504 a(n) = A280500(n,A280503(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

Scheme

Formula

A166166 Write n in binary with each run (of either digit b) of the k-th longest distinct run-length replaced with a run of digit b of a length equal to that of the k-th shortest distinct run-length. Convert back to decimal for a(n). (See comment.)

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A377834 a(1) = 0, and for n > 0, if A055932(n) = 2^r(1) * 3^r(2) * ... * prime(k)^r(k) with r(k) > 0 (where prime(k) denotes the k-th prime number), then the run lengths of the binary expansion of a(n) are (r(1), r(2), ..., r(k)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A377836 a(1) = 0, and for n > 0, if A055932(n) = 2^r(1) * 3^r(2) * ... * prime(k)^r(k) with r(k) > 0 (where prime(k) denotes the k-th prime number), then the run lengths of the binary expansion of a(n) are (r(k), r(k-1), ..., r(1)).

Views